New Bounds and a Generalization for Share Conversion for 3-Server PIR
Private Information Retrieval (PIR) protocols, which allow the client to obtain data from servers without revealing its request, have many applications such as anonymous communication, media streaming, blockchain security, advertisement, etc. Multi-server PIR protocols, where the database is replica...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-04-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/24/4/497 |
| _version_ | 1827619768030461952 |
|---|---|
| author | Anat Paskin-Cherniavsky Olga Nissenbaum |
| author_facet | Anat Paskin-Cherniavsky Olga Nissenbaum |
| author_sort | Anat Paskin-Cherniavsky |
| collection | DOAJ |
| description | Private Information Retrieval (PIR) protocols, which allow the client to obtain data from servers without revealing its request, have many applications such as anonymous communication, media streaming, blockchain security, advertisement, etc. Multi-server PIR protocols, where the database is replicated among the non-colluding servers, provide high efficiency in the information-theoretic setting. Beimel et al. in CCC 12’ (further referred to as BIKO) put forward a paradigm for constructing multi-server PIR, capturing several previous constructions for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> servers, as well as improving the best-known share complexity for 3-server PIR. A key component there is a share conversion scheme from corresponding linear three-party secret sharing schemes with respect to a certain type of “modified universal” relation. In a useful particular instantiation of the paradigm, they used a share conversion from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>)</mo></mrow></semantics></math></inline-formula>-CNF over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="double-struck">Z</mi><mi>m</mi></msub></semantics></math></inline-formula> to three-additive sharing over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msubsup><mi mathvariant="double-struck">Z</mi><mi>p</mi><mi>β</mi></msubsup></semantics></math></inline-formula> for primes <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>p</mi><mn>1</mn></msub><mo>,</mo><msub><mi>p</mi><mn>2</mn></msub><mo>,</mo><mi>p</mi></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>p</mi><mn>1</mn></msub><mo>≠</mo><msub><mi>p</mi><mn>2</mn></msub></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>m</mi><mo>=</mo><msub><mi>p</mi><mn>1</mn></msub><mo>·</mo><msub><mi>p</mi><mn>2</mn></msub></mrow></semantics></math></inline-formula>, and the relation is modified universal relation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>C</mi><msub><mi>S</mi><mi>m</mi></msub></msub></semantics></math></inline-formula>. They reduced the question of the existence of the share conversion for a triple <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>p</mi><mn>1</mn></msub><mo>,</mo><msub><mi>p</mi><mn>2</mn></msub><mo>,</mo><mi>p</mi><mo>)</mo></mrow></semantics></math></inline-formula> to the (in)solvability of a certain linear system over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="double-struck">Z</mi><mi>p</mi></msub></semantics></math></inline-formula>, and provided an efficient (in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>m</mi><mo>,</mo><mo form="prefix">log</mo><mi>p</mi></mrow></semantics></math></inline-formula>) construction of such a sharing scheme. Unfortunately, the size of the system is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Θ</mi><mo>(</mo><msup><mi>m</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> which entails the infeasibility of a direct solution for big <i>m</i>’s in practice. Paskin-Cherniavsky and Schmerler in 2019 proved the existence of the conversion for the case of odd <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>p</mi><mn>1</mn></msub></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>p</mi><mn>2</mn></msub></semantics></math></inline-formula> when <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>=</mo><msub><mi>p</mi><mn>1</mn></msub></mrow></semantics></math></inline-formula>, obtaining in this way infinitely many parameters for which the conversion exists, but also for infinitely many of them it remained open. In this work, using some algebraic techniques from the work of Paskin-Cherniavsky and Schmerler, we prove the existence of the conversion for even <i>m</i>’s in case <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>=</mo><mn>2</mn></mrow></semantics></math></inline-formula> (we computed <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>β</mi></semantics></math></inline-formula> in this case) and the absence of the conversion for even <i>m</i>’s in case <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>></mo><mn>2</mn></mrow></semantics></math></inline-formula>. This does not improve the concrete efficiency of 3-server PIR; however, our result is promising in a broader context of constructing PIR through composition techniques with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> servers, using the relation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>C</mi><msub><mi>S</mi><mi>m</mi></msub></msub></semantics></math></inline-formula> where <i>m</i> has more than two prime divisors. Another our suggestion about 3-server PIR is that it’s possible to achieve a shorter server’s response using the relation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>C</mi><msubsup><mi>S</mi><mi>m</mi><mo>′</mo></msubsup></msub></semantics></math></inline-formula> for extended <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi>S</mi><mi>m</mi><mo>′</mo></msubsup><mo>⊃</mo><msub><mi>S</mi><mi>m</mi></msub></mrow></semantics></math></inline-formula>. By computer search, in BIKO framework we found several such sets for small <i>m</i>’s which result in share conversion from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>)</mo></mrow></semantics></math></inline-formula>-CNF over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="double-struck">Z</mi><mi>m</mi></msub></semantics></math></inline-formula> to 3-additive secret sharing over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msubsup><mi mathvariant="double-struck">Z</mi><mi>p</mi><msup><mi>β</mi><mo>′</mo></msup></msubsup></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>β</mi><mo>′</mo></msup><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula> is several times less than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>β</mi></semantics></math></inline-formula>, which implies several times shorter server’s response. We also suggest that such extended sets <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msubsup><mi>S</mi><mi>m</mi><mo>′</mo></msubsup></semantics></math></inline-formula> can result in better PIR due to the potential existence of matching vector families with the higher Vapnik-Chervonenkis dimension. |
| first_indexed | 2024-03-09T10:36:54Z |
| format | Article |
| id | doaj.art-0b6c00e454da4086a157edc83c14050e |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-09T10:36:54Z |
| publishDate | 2022-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-0b6c00e454da4086a157edc83c14050e2023-12-01T20:50:15ZengMDPI AGEntropy1099-43002022-04-0124449710.3390/e24040497New Bounds and a Generalization for Share Conversion for 3-Server PIRAnat Paskin-Cherniavsky0Olga Nissenbaum1Computer Science Department, Ariel University, Ariel 40700, IsraelComputer Science Department, Ariel University, Ariel 40700, IsraelPrivate Information Retrieval (PIR) protocols, which allow the client to obtain data from servers without revealing its request, have many applications such as anonymous communication, media streaming, blockchain security, advertisement, etc. Multi-server PIR protocols, where the database is replicated among the non-colluding servers, provide high efficiency in the information-theoretic setting. Beimel et al. in CCC 12’ (further referred to as BIKO) put forward a paradigm for constructing multi-server PIR, capturing several previous constructions for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> servers, as well as improving the best-known share complexity for 3-server PIR. A key component there is a share conversion scheme from corresponding linear three-party secret sharing schemes with respect to a certain type of “modified universal” relation. In a useful particular instantiation of the paradigm, they used a share conversion from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>)</mo></mrow></semantics></math></inline-formula>-CNF over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="double-struck">Z</mi><mi>m</mi></msub></semantics></math></inline-formula> to three-additive sharing over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msubsup><mi mathvariant="double-struck">Z</mi><mi>p</mi><mi>β</mi></msubsup></semantics></math></inline-formula> for primes <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>p</mi><mn>1</mn></msub><mo>,</mo><msub><mi>p</mi><mn>2</mn></msub><mo>,</mo><mi>p</mi></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>p</mi><mn>1</mn></msub><mo>≠</mo><msub><mi>p</mi><mn>2</mn></msub></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>m</mi><mo>=</mo><msub><mi>p</mi><mn>1</mn></msub><mo>·</mo><msub><mi>p</mi><mn>2</mn></msub></mrow></semantics></math></inline-formula>, and the relation is modified universal relation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>C</mi><msub><mi>S</mi><mi>m</mi></msub></msub></semantics></math></inline-formula>. They reduced the question of the existence of the share conversion for a triple <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>p</mi><mn>1</mn></msub><mo>,</mo><msub><mi>p</mi><mn>2</mn></msub><mo>,</mo><mi>p</mi><mo>)</mo></mrow></semantics></math></inline-formula> to the (in)solvability of a certain linear system over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="double-struck">Z</mi><mi>p</mi></msub></semantics></math></inline-formula>, and provided an efficient (in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>m</mi><mo>,</mo><mo form="prefix">log</mo><mi>p</mi></mrow></semantics></math></inline-formula>) construction of such a sharing scheme. Unfortunately, the size of the system is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Θ</mi><mo>(</mo><msup><mi>m</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> which entails the infeasibility of a direct solution for big <i>m</i>’s in practice. Paskin-Cherniavsky and Schmerler in 2019 proved the existence of the conversion for the case of odd <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>p</mi><mn>1</mn></msub></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>p</mi><mn>2</mn></msub></semantics></math></inline-formula> when <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>=</mo><msub><mi>p</mi><mn>1</mn></msub></mrow></semantics></math></inline-formula>, obtaining in this way infinitely many parameters for which the conversion exists, but also for infinitely many of them it remained open. In this work, using some algebraic techniques from the work of Paskin-Cherniavsky and Schmerler, we prove the existence of the conversion for even <i>m</i>’s in case <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>=</mo><mn>2</mn></mrow></semantics></math></inline-formula> (we computed <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>β</mi></semantics></math></inline-formula> in this case) and the absence of the conversion for even <i>m</i>’s in case <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>></mo><mn>2</mn></mrow></semantics></math></inline-formula>. This does not improve the concrete efficiency of 3-server PIR; however, our result is promising in a broader context of constructing PIR through composition techniques with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> servers, using the relation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>C</mi><msub><mi>S</mi><mi>m</mi></msub></msub></semantics></math></inline-formula> where <i>m</i> has more than two prime divisors. Another our suggestion about 3-server PIR is that it’s possible to achieve a shorter server’s response using the relation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>C</mi><msubsup><mi>S</mi><mi>m</mi><mo>′</mo></msubsup></msub></semantics></math></inline-formula> for extended <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi>S</mi><mi>m</mi><mo>′</mo></msubsup><mo>⊃</mo><msub><mi>S</mi><mi>m</mi></msub></mrow></semantics></math></inline-formula>. By computer search, in BIKO framework we found several such sets for small <i>m</i>’s which result in share conversion from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>)</mo></mrow></semantics></math></inline-formula>-CNF over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="double-struck">Z</mi><mi>m</mi></msub></semantics></math></inline-formula> to 3-additive secret sharing over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msubsup><mi mathvariant="double-struck">Z</mi><mi>p</mi><msup><mi>β</mi><mo>′</mo></msup></msubsup></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>β</mi><mo>′</mo></msup><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula> is several times less than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>β</mi></semantics></math></inline-formula>, which implies several times shorter server’s response. We also suggest that such extended sets <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msubsup><mi>S</mi><mi>m</mi><mo>′</mo></msubsup></semantics></math></inline-formula> can result in better PIR due to the potential existence of matching vector families with the higher Vapnik-Chervonenkis dimension.https://www.mdpi.com/1099-4300/24/4/497PIRshare conversionCNF secret sharingcommunication complexity |
| spellingShingle | Anat Paskin-Cherniavsky Olga Nissenbaum New Bounds and a Generalization for Share Conversion for 3-Server PIR Entropy PIR share conversion CNF secret sharing communication complexity |
| title | New Bounds and a Generalization for Share Conversion for 3-Server PIR |
| title_full | New Bounds and a Generalization for Share Conversion for 3-Server PIR |
| title_fullStr | New Bounds and a Generalization for Share Conversion for 3-Server PIR |
| title_full_unstemmed | New Bounds and a Generalization for Share Conversion for 3-Server PIR |
| title_short | New Bounds and a Generalization for Share Conversion for 3-Server PIR |
| title_sort | new bounds and a generalization for share conversion for 3 server pir |
| topic | PIR share conversion CNF secret sharing communication complexity |
| url | https://www.mdpi.com/1099-4300/24/4/497 |
| work_keys_str_mv | AT anatpaskincherniavsky newboundsandageneralizationforshareconversionfor3serverpir AT olganissenbaum newboundsandageneralizationforshareconversionfor3serverpir |