{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:59:57Z","timestamp":1760151597540,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:00:00Z","timestamp":1648771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Ariel Cyber Innovation Center in conjunction with the Israel National Cyber directorate in the Prime Minister's Office.","award":["ISF 152\/17"],"award-info":[{"award-number":["ISF 152\/17"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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\u2019 (further referred to as BIKO) put forward a paradigm for constructing multi-server PIR, capturing several previous constructions for k\u22653 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 \u201cmodified universal\u201d relation. In a useful particular instantiation of the paradigm, they used a share conversion from (2,3)-CNF over Zm to three-additive sharing over Zp\u03b2 for primes p1,p2,p where p1\u2260p2 and m=p1\u00b7p2, and the relation is modified universal relation CSm. They reduced the question of the existence of the share conversion for a triple (p1,p2,p) to the (in)solvability of a certain linear system over Zp, and provided an efficient (in m,logp) construction of such a sharing scheme. Unfortunately, the size of the system is \u0398(m2) which entails the infeasibility of a direct solution for big m\u2019s in practice. Paskin-Cherniavsky and Schmerler in 2019 proved the existence of the conversion for the case of odd p1, p2 when p=p1, 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 m\u2019s in case p=2 (we computed \u03b2 in this case) and the absence of the conversion for even m\u2019s in case p&gt;2. 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 k\u22653 servers, using the relation CSm where m has more than two prime divisors. Another our suggestion about 3-server PIR is that it\u2019s possible to achieve a shorter server\u2019s response using the relation CSm\u2032 for extended Sm\u2032\u2283Sm. By computer search, in BIKO framework we found several such sets for small m\u2019s which result in share conversion from (2,3)-CNF over Zm to 3-additive secret sharing over Zp\u03b2\u2032, where \u03b2\u2032&gt;0 is several times less than \u03b2, which implies several times shorter server\u2019s response. We also suggest that such extended sets Sm\u2032 can result in better PIR due to the potential existence of matching vector families with the higher Vapnik-Chervonenkis dimension.<\/jats:p>","DOI":"10.3390\/e24040497","type":"journal-article","created":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T21:22:39Z","timestamp":1648848159000},"page":"497","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["New Bounds and a Generalization for Share Conversion for 3-Server PIR"],"prefix":"10.3390","volume":"24","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9819-5560","authenticated-orcid":false,"given":"Olga","family":"Nissenbaum","sequence":"additional","affiliation":[{"name":"Computer Science Department, Ariel University, Ariel 40700, Israel"}]}],"member":"1968","published-online":{"date-parts":[[2022,4,1]]},"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":"Angel, S., and Setty, S. (2016, January 2\u20134). Unobservable communication over fully untrusted infrastructure. Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), Savannah, GA, USA."},{"key":"ref_3","unstructured":"Mittal, P., Olumofin, F.G., Troncoso, C., Borisov, N., and Goldberg, I. (2011, January 8\u201312). PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval. Proceedings of the 20th USENIX Security Symposium, San Francisco, CA, USA."},{"key":"ref_4","unstructured":"Gupta, T., Crooks, N., Mulhern, W., Setty, S., Alvisi, L., and Walfish, M. (2016, January 16\u201318). Scalable and private media consumption with Popcorn. Proceedings of the 13th (USENIX) Symposium on Networked Systems Design and Implementation (NSDI 16), Santa Clara, CA, USA."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1109\/MSP.2018.3111245","article-title":"Blockchain access privacy: Challenges and directions","volume":"16","author":"Henry","year":"2018","journal-title":"IEEE Secur. Priv."},{"key":"ref_6","unstructured":"Gentry, C., Halevi, S., Magri, B., Nielsen, J.B., and Yakoubov, S. (2021, December 19). Random-Index PIR and Applications. Technical Report, Cryptology ePrint Archive, Report 2020\/1248. Available online: https:\/\/eprint.iacr.org."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Green, M., Ladd, W., and Miers, I. (2016, January 24\u201328). A protocol for privately reporting ad impressions at scale. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.","DOI":"10.1145\/2976749.2978407"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1109\/MCOM.2018.1701341","article-title":"Unleashing the power of multi-server pir for enabling private access to spectrum databases","volume":"56","author":"Grissa","year":"2018","journal-title":"IEEE Commun. Mag."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"6435","DOI":"10.1109\/TITS.2020.2992232","article-title":"Protecting privacy of location-based services in road networks","volume":"22","author":"Tan","year":"2020","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_10","unstructured":"G\u00fcnther, D., Holz, M., Judkewitz, B., M\u00f6llering, H., Pinkas, B., and Schneider, T. (2020). PEM: Privacy-preserving Epidemiological Modeling. Cryptol. ePrint Arch., Available online: https:\/\/eprint.iacr.org\/2020\/1546."},{"key":"ref_11","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_12","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/1326554.1326555","article-title":"Towards 3-query locally decodable codes of subexponential length","volume":"55","author":"Yekhanin","year":"2008","journal-title":"J. ACM"},{"key":"ref_13","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_14","doi-asserted-by":"crossref","first-page":"39:1","DOI":"10.1145\/2968443","article-title":"2-Server PIR with Subpolynomial Communication","volume":"63","author":"Dvir","year":"2016","journal-title":"J. ACM"},{"key":"ref_15","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_16","doi-asserted-by":"crossref","unstructured":"Mughees, M.H., Chen, H., and Ren, L. (2021, January 15\u201319). OnionPIR: Response Efficient Single-Server PIR. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual, Korea.","DOI":"10.1145\/3460120.3485381"},{"key":"ref_17","unstructured":"Ali, A., Lepoint, T., Patel, S., Raykova, M., Schoppmann, P., Seth, K., and Yeo, K. (2021, January 11\u201313). Communication\u2013Computation Trade-offs in PIR. Proceedings of the 30th USENIX Security Symposium (USENIX Security 21), Virtual."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Park, J., and Tibouchi, M. (2020). SHECS-PIR: Somewhat Homomorphic Encryption-Based Compact and Scalable Private Information Retrieval. European Symposium on Research in Computer Security, Springer.","DOI":"10.1007\/978-3-030-59013-0_5"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Corrigan-Gibbs, H., and Kogan, D. (2020). Private information retrieval with sublinear online time. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-030-45721-1_3"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Gilboa, N., and Ishai, Y. (2014). Distributed point functions and their applications. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-642-55220-5_35"},{"key":"ref_21","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., and Raymond, J. (2002, January 16\u201319). Breaking the O(n1\/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval. Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), Vancouver, BC, Canada."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Ben-Aroya, A., Efremenko, K., and Ta-Shma, A. (2010, January 23\u201326). Local list decoding with a constant number of queries. Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas, NV, USA.","DOI":"10.1109\/FOCS.2010.88"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s00037-011-0017-1","article-title":"Query-efficient locally decodable codes of subexponential length","volume":"22","author":"Chee","year":"2013","journal-title":"Comput. Complex."},{"key":"ref_24","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_25","doi-asserted-by":"crossref","unstructured":"Efremenko, K. (2012, January 20\u201322). From irreducible representations to locally decodable codes. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/2213977.2214008"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1587\/transinf.E93.D.263","article-title":"Improved constructions for query-efficient locally decodable codes of subexponential length","volume":"93","author":"Itoh","year":"2010","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_27","first-page":"342","article-title":"Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation","volume":"Volume 3378","author":"Kilian","year":"2005","journal-title":"Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","article-title":"On the uniform convergence of relative frequencies of events to their probabilities","volume":"16","author":"Vapnik","year":"1971","journal-title":"Theory Probab. Appl."},{"key":"ref_29","unstructured":"Simon, J. (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."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s004930070032","article-title":"Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs","volume":"20","author":"Grolmusz","year":"2000","journal-title":"Combinatorica"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Ito, M., Saito, A., and Nishizeki, T. (1993). Multiple Assignment Scheme for Sharing Secret, Springer.","DOI":"10.1007\/BF02620229"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Paskin-Cherniavsky, A., and Schmerler, L. (2019). On Share Conversions for Private Information Retrieval. Entropy, 21.","DOI":"10.3390\/e21090826"},{"key":"ref_33","first-page":"11","article-title":"Secret-Sharing Schemes: A Survey","volume":"Volume 6639","author":"Chee","year":"2011","journal-title":"Coding and Cryptology\u2014Proceedings of the Third International Workshop, IWCC 2011, Qingdao, China, 30 May\u20133 June 2011"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/4\/497\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:48:27Z","timestamp":1760136507000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/4\/497"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,1]]},"references-count":33,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,4]]}},"alternative-id":["e24040497"],"URL":"https:\/\/doi.org\/10.3390\/e24040497","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,4,1]]}}}