{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:45:29Z","timestamp":1760240729134,"version":"build-2065373602"},"reference-count":15,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T00:00:00Z","timestamp":1566518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Beimel et al. in CCC 12\u2019 put forward a paradigm for constructing Private Information Retrieval (PIR) schemes, capturing several previous constructions for     k \u2265 3     servers. A key component in the paradigm, applicable to three-server PIR, is a share conversion scheme from corresponding linear three-party secret sharing schemes with respect to a certain type of \u201cmodified universal\u201d relation. In a useful particular instantiation of the paradigm, they used a share conversion from     ( 2 , 3 )    -CNF over     Z m     to three-additive sharing over     Z p \u03b2     for primes      p 1  ,  p 2  , p     where      p 1  \u2260  p 2      and     m  =   p 1  \u00b7  p 2     . The share conversion is with respect to the modified universal relation     C  S m     . They reduced the question of whether a suitable share conversion exists for a triple     (  p 1  ,  p 2  , p )     to the (in)solvability of a certain linear system over     Z p    . Assuming a solution exists, they also provided a efficient (in     m , log p    ) construction of such a sharing scheme. They proved a suitable conversion exists for several triples of small numbers using a computer program; in particular,     p  =   p 1   =  2 ,  p 2   =  3     yielded the three-server PIR with the best communication complexity at the time. This approach quickly becomes infeasible as the resulting matrix is of size     \u0398 (  m 4  )    . In this work, we prove that the solvability condition holds for an infinite family of     (  p 1  ,  p 2  , p )    \u2019s, answering an open question of Beimel et al. Concretely, we prove that if      p 1  ,  p 2  &gt; 2     and     p  =   p 1     , then a conversion of the required form exists. We leave the full characterization of such triples, with potential applications to PIR complexity, to future work. Although larger (particularly with     m a x (  p 1  ,  p 2  ) &gt; 3    ) triples do not yield improved three-server PIR communication complexity via BIKO\u2019s construction, a richer family of PIR protocols we obtain by plugging in our share conversions might have useful properties for other applications. Moreover, we hope that the analytic techniques for understanding the relevant matrices we developed would help to understand whether share conversion as above for     C  S m     , where m is a product of more than two (say three) distinct primes, exists. The general BIKO paradigm generalizes to work for such     Z m    \u2019s. Furthermore, the linear condition in Beimel et al. generalizes to m\u2019s, which are products of more than two primes, so our hope is somewhat justified. In case such a conversion does exist, plugging it into BIKO\u2019s construction would lead to major improvement to the state of the art of three-server PIR communication complexity (reducing Communication Complexity (CC) in correspondence with certain matching vector families).<\/jats:p>","DOI":"10.3390\/e21090826","type":"journal-article","created":{"date-parts":[[2019,8,26]],"date-time":"2019-08-26T04:38:23Z","timestamp":1566794303000},"page":"826","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Share Conversions for Private Information Retrieval"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6566-2644","authenticated-orcid":false,"given":"Anat","family":"Paskin-Cherniavsky","sequence":"first","affiliation":[{"name":"Computer Science Department, Ariel University, Ariel 40700, Israel"}]},{"given":"Leora","family":"Schmerler","sequence":"additional","affiliation":[{"name":"Computer Science Department, Ariel University, Ariel 40700, Israel"}]}],"member":"1968","published-online":{"date-parts":[[2019,8,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/293347.293350","article-title":"Private Information Retrieval","volume":"45","author":"Chor","year":"1998","journal-title":"J. ACM"},{"key":"ref_2","unstructured":"Kushilevitz, E., and Ostrovsky, R. (1997, January 19\u201322). Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS \u201997, Miami Beach, FL, USA."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Gentry, C., and Ramzan, Z. (2005, January 11\u201315). Single-Database Private Information Retrieval with Constant Communication Rate. Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal.","DOI":"10.1007\/11523468_65"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., and Orlov, I. (2012, January 26\u201329). Share Conversion and Private Information Retrieval. Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal.","DOI":"10.1109\/CCC.2012.23"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., and Wigderson, A. (1988, January 2\u20134). Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA.","DOI":"10.1145\/62212.62213"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., and Wigderson, A. (1987, January 25\u201327). How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/28395.28420"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Cramer, R., Damg\u00e5rd, I., and Ishai, Y. (2005). Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. Theory of Cryptography Conference, Springer.","DOI":"10.1007\/978-3-540-30576-7_19"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/S0196-6774(02)00204-3","article-title":"Constructing set systems with prescribed intersection sizes","volume":"44","author":"Grolmusz","year":"2002","journal-title":"J. Algorithms"},{"key":"ref_9","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., and Raymond, J. (2002, January 16\u201319). Breaking the O(n1\/(2k\u22121)) Barrier for Information-Theoretic Private Information Retrieval. Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), Vancouver, BC, Canada."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1694","DOI":"10.1137\/090772721","article-title":"3-Query Locally Decodable Codes of Subexponential Length","volume":"41","author":"Efremenko","year":"2012","journal-title":"SIAM J. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Yekhanin, S. (2008). Towards 3-query locally decodable codes of subexponential length. J. ACM, 55.","DOI":"10.1145\/1250790.1250830"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1154","DOI":"10.1137\/100804322","article-title":"Matching Vector Codes","volume":"40","author":"Dvir","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/2968443","article-title":"2-Server PIR with Subpolynomial Communication","volume":"63","author":"Dvir","year":"2016","journal-title":"J. ACM"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Beimel, A. (2011). Secret-Sharing Schemes: A Survey. International Conference on Coding and Cryptology, Springer.","DOI":"10.1007\/978-3-642-20901-7_2"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Wehner, S., and de Wolf, R. (2005). Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval. International Colloquium on Automata, Languages, and Programming, Springer.","DOI":"10.1007\/11523468_115"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/9\/826\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:13:29Z","timestamp":1760188409000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/9\/826"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,23]]},"references-count":15,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,9]]}},"alternative-id":["e21090826"],"URL":"https:\/\/doi.org\/10.3390\/e21090826","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2019,8,23]]}}}