{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,12]],"date-time":"2026-08-12T10:36:31Z","timestamp":1786530991719,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":62,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032354273","type":"print"},{"value":"9783032354280","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-35428-0_17","type":"book-chapter","created":{"date-parts":[[2026,8,12]],"date-time":"2026-08-12T10:08:23Z","timestamp":1786529303000},"page":"514-543","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Arithmetic Private Information Retrieval: Why Code-Based PIR (Usually) Fails"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4792-369X","authenticated-orcid":false,"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4096-6305","authenticated-orcid":false,"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7643-6348","authenticated-orcid":false,"given":"Shahar","family":"Shechter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,13]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","unstructured":"Abram, D., Malavolta, G., Roy, L.: Slightly sublinear trapdoor hash functions and PIR from low-noise LPN. In: Applebaum, B., Lin, H.R. (eds.) Theory of Cryptography - 23rd International Conference, TCC 2025, Aarhus, Denmark, 1\u20135 December 2025, Proceedings, Part I. Lecture Notes in Computer Science, vol. 16268, pp. 280\u2013300. Springer (2025). https:\/\/doi.org\/10.1007\/978-3-032-12287-2_10","DOI":"10.1007\/978-3-032-12287-2_10"},{"key":"17_CR2","unstructured":"Ahmad, I., Yang, Y., Agrawal, D., Abbadi, A.E., Gupta, T.: Addra: metadata-private voice communication over fully untrusted infrastructure. In: Brown, A.D., Lorch, J.R. (eds.) 15th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2021, 14\u201316 July 2021. USENIX Association (2021). https:\/\/www.usenix.org\/conference\/osdi21\/presentation\/ahmad"},{"key":"17_CR3","doi-asserted-by":"publisher","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: 44th Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, MA, USA, 11\u201314 October 2003, Proceedings, pp. 298\u2013307. IEEE Comput. Soc. (2003). https:\/\/doi.org\/10.1109\/SFCS.2003.1238204","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"17_CR4","unstructured":"Ali, A., Lepoint, T., Patel, S., Raykova, M., Schoppmann, P., Seth, K., Yeo, K.: Communication-computation trade-offs in PIR. In: Bailey, M.D., Greenstadt, R. (eds.) 30th USENIX Security Symposium, USENIX Security 2021, 11\u201313 August 2021, pp. 1811\u20131828. USENIX Association (2021). https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/ali"},{"key":"17_CR5","doi-asserted-by":"publisher","unstructured":"Alon, B., Beimel, A., Lasri, O.: Simplified PIR and CDS protocols and improved linear secret-sharing schemes. In: Applebaum, B., Lin, H.R. (eds.) Theory of Cryptography - 23rd International Conference, TCC 2025, Aarhus, Denmark, 1\u20135 December 2025, Proceedings, Part II. Lecture Notes in Computer Science, vol. 16269, pp. 365\u2013398. Springer (2025). https:\/\/doi.org\/10.1007\/978-3-032-12293-3_12","DOI":"10.1007\/978-3-032-12293-3_12"},{"key":"17_CR6","doi-asserted-by":"publisher","unstructured":"Angel, S., Chen, H., Laine, K., Setty, S.T.V.: PIR with compressed queries and amortized query processing. In: 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21\u201323 May 2018, San Francisco, California, USA, pp. 962\u2013979. IEEE Comput. Soc. (2018). https:\/\/doi.org\/10.1109\/SP.2018.00062","DOI":"10.1109\/SP.2018.00062"},{"key":"17_CR7","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Avron, J., Brzuska, C.: Arithmetic cryptography. J. ACM 64(2), 10:1\u201310:74 (2017). https:\/\/doi.org\/10.1145\/3046675","DOI":"10.1145\/3046675"},{"key":"17_CR8","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, 16\u201320 August 2009. Proceedings. Lecture Notes in Computer Science, vol.\u00a05677, pp. 595\u2013618. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_35","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"17_CR9","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Damg\u00e5rd, I., Ishai, Y., Nielsen, M., Zichron, L.: Secure arithmetic computation with constant computational overhead. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, 20\u201324 August 2017, Proceedings, Part I. Lecture Notes in Computer Science, vol. 10401, pp. 223\u2013254. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_8","DOI":"10.1007\/978-3-319-63688-7_8"},{"key":"17_CR10","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Haramaty, N., Ishai, Y., Kushilevitz, E., Vaikuntanathan, V.: Low-complexity cryptographic hash functions. In: Papadimitriou, C.H. (ed.) 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, Berkeley, CA, USA, 9\u201311 January 2017. LIPIcs, vol.\u00a067, pp. 7:1\u20137:31. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPICS.ITCS.2017.7","DOI":"10.4230\/LIPICS.ITCS.2017.7"},{"key":"17_CR11","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: How to garble arithmetic circuits. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, 22\u201325 October 2011, pp. 120\u2013129. IEEE Comput. Soc. (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.40","DOI":"10.1109\/FOCS.2011.40"},{"key":"17_CR12","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Konstantini, N.: Actively secure arithmetic computation and VOLE with constant computational overhead. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23\u201327 April 2023, Proceedings, Part II. Lecture Notes in Computer Science, vol. 14005, pp. 190\u2013219. Springer (2023).https:\/\/doi.org\/10.1007\/978-3-031-30617-4_7","DOI":"10.1007\/978-3-031-30617-4_7"},{"key":"17_CR13","unstructured":"Beimel, A.: Secure Schemes for Secret Sharing and Key Distribution. Ph.D. thesis, Technion (1996)"},{"issue":"2","key":"17_CR14","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/J.JCSS.2005.03.002","volume":"71","author":"A Beimel","year":"2005","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E.: General constructions for information-theoretic private information retrieval. J. Comput. Syst. Sci. 71(2), 213\u2013247 (2005). https:\/\/doi.org\/10.1016\/J.JCSS.2005.03.002","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR15","doi-asserted-by":"publisher","unstructured":"Benhamouda, F., et al.: Encrypted matrix-vector products from secret dual codes. In: Huang, C., Chen, J., Shieh, S., Lie, D., Cortier, V. (eds.) Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, CCS 2025, Taipei, Taiwan, 13\u201317 October 2025, pp. 394\u2013408. ACM (2025). https:\/\/doi.org\/10.1145\/3719027.3765194","DOI":"10.1145\/3719027.3765194"},{"key":"17_CR16","unstructured":"Bitzer, S., Egger, M., Liu, M., Wachter-Zeh, A.: Post-quantum secure aggregation via code-based homomorphic encryption (2026). https:\/\/arxiv.org\/abs\/2601.13031"},{"key":"17_CR17","doi-asserted-by":"publisher","unstructured":"Blum, A., Furst, M.L., Kearns, M.J., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) Advances in Cryptology - CRYPTO \u20191993, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, 22\u201326 August 1993, Proceedings. Lecture Notes in Computer Science, vol.\u00a0773, pp. 278\u2013291. Springer (1993). https:\/\/doi.org\/10.1007\/3-540-48329-2_24","DOI":"10.1007\/3-540-48329-2_24"},{"key":"17_CR18","doi-asserted-by":"publisher","unstructured":"Bodur, c., Mart\u00ednez-Moro, E., Ruano, D.: Single server private information retrieval protocols with codes over rings. J. Algebra Appl. 24(13n14), 2541012 (2025). https:\/\/doi.org\/10.1142\/S0219498825410129","DOI":"10.1142\/S0219498825410129"},{"issue":"4","key":"17_CR19","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s12095-021-00477-z","volume":"13","author":"S Bordage","year":"2021","unstructured":"Bordage, S., Lavauzelle, J.: On the privacy of a code-based single-server computational PIR scheme. Cryptogr. Commun. 13(4), 519\u2013526 (2021)","journal-title":"Cryptogr. Commun."},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1292\u20131303 (2016)","DOI":"10.1145\/2976749.2978429"},{"key":"17_CR21","doi-asserted-by":"publisher","unstructured":"Boyle, E., Ishai, Y., Pass, R., Wootters, M.: Can we access a database both locally and privately? In: Kalai, Y., Reyzin, L. (eds.) Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, 12\u201315 November 2017, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10678, pp. 662\u2013693. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_22","DOI":"10.1007\/978-3-319-70503-3_22"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Canetti, R., Holmgren, J., Richelson, S.: Towards doubly efficient private information retrieval. IACR Cryptol. ePrint Arch, p.\u00a0568 (2017). http:\/\/eprint.iacr.org\/2017\/568","DOI":"10.1007\/978-3-319-70503-3_23"},{"key":"17_CR23","doi-asserted-by":"publisher","unstructured":"Canetti, R., Ishai, Y., Kumar, R., Reiter, M.K., Rubinfeld, R., Wright, R.N.: Selective private function evaluation with applications to private statistics. In: Kshemkalyani, A.D., Shavit, N. (eds.) Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, PODC 2001, Newport, Rhode Island, USA, 26\u201329 August 2001, pp. 293\u2013304. ACM (2001). https:\/\/doi.org\/10.1145\/383962.384047","DOI":"10.1145\/383962.384047"},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"Chen, C., Ishai, Y., Mour, T., Rosen, A.: Secret-key PIR from random linear codes. Cryptology ePrint Archive (2025). To appear in STOC 2026","DOI":"10.1145\/3798129.3800906"},{"key":"17_CR25","doi-asserted-by":"publisher","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. J. ACM 45(6), 965\u2013981 (1998). https:\/\/doi.org\/10.1145\/293347.293350. conference version in FOCS 1995","DOI":"10.1145\/293347.293350"},{"key":"17_CR26","doi-asserted-by":"publisher","unstructured":"Cohen, G., et al.: Efficient multiparty protocols via log-depth threshold formulae - (extended abstract). In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, 18\u201322 August 2013. Proceedings, Part II. Lecture Notes in Computer Science, vol.\u00a08043, pp. 185\u2013202. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-40084-1_11","DOI":"10.1007\/978-3-642-40084-1_11"},{"key":"17_CR27","doi-asserted-by":"crossref","unstructured":"Cramer, R., Fehr, S.: Optimal black-box secret sharing over arbitrary abelian groups. IACR Cryptol. ePrint Arch, p.\u00a036 (2002). http:\/\/eprint.iacr.org\/2002\/036","DOI":"10.7146\/brics.v9i8.21726"},{"key":"17_CR28","doi-asserted-by":"publisher","unstructured":"Cramer, R., Fehr, S., Ishai, Y., Kushilevitz, E.: Efficient multi-party computation over rings. In: Biham, E. (ed.) Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, 4\u20138 May 2003, Proceedings. Lecture Notes in Computer Science, vol.\u00a02656, pp. 596\u2013613. Springer (2003). https:\/\/doi.org\/10.1007\/3-540-39200-9_37","DOI":"10.1007\/3-540-39200-9_37"},{"key":"17_CR29","doi-asserted-by":"publisher","unstructured":"Crescenzo, G.D., Malkin, T., Ostrovsky, R.: Single database private information retrieval implies oblivious transfer. In: Preneel, B. (ed.) Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, 14\u201318 May 2000, Proceeding. Lecture Notes in Computer Science, vol.\u00a01807, pp. 122\u2013138. Springer (2000). https:\/\/doi.org\/10.1007\/3-540-45539-6_10","DOI":"10.1007\/3-540-45539-6_10"},{"key":"17_CR30","doi-asserted-by":"publisher","unstructured":"Davidson, A., Pestana, G., Celi, S.: FrodoPIR: Simple, scalable, single-server private information retrieval. Proc. Priv. Enhancing Technol. 2023(1), 365\u2013383 (2023). https:\/\/doi.org\/10.56553\/POPETS-2023-0022","DOI":"10.56553\/POPETS-2023-0022"},{"key":"17_CR31","doi-asserted-by":"publisher","unstructured":"Desmedt, Y., Frankel, Y.: Shared generation of authenticators and signatures (extended abstract). In: Feigenbaum, J. (ed.) Advances in Cryptology - CRYPTO \u20191991, 11th Annual International Cryptology Conference, Santa Barbara, California, USA, 11\u201315 August 1991, Proceedings. Lecture Notes in Computer Science, vol.\u00a0576, pp. 457\u2013469. Springer (1991). https:\/\/doi.org\/10.1007\/3-540-46766-1_37","DOI":"10.1007\/3-540-46766-1_37"},{"key":"17_CR32","doi-asserted-by":"publisher","unstructured":"Desmedt, Y., Pieprzyk, J., Steinfeld, R., Wang, H.: On secure multi-party computation in black-box groups. In: Menezes, A. (ed.) Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, 19\u201323 August 2007, Proceedings. Lecture Notes in Computer Science, vol.\u00a04622, pp. 591\u2013612. Springer (2007). https:\/\/doi.org\/10.1007\/978-3-540-74143-5_33","DOI":"10.1007\/978-3-540-74143-5_33"},{"issue":"6","key":"17_CR33","doi-asserted-by":"publisher","first-page":"2144","DOI":"10.1137\/080715372","volume":"38","author":"Z Dvir","year":"2009","unstructured":"Dvir, Z., Gabizon, A., Wigderson, A.: Extractors and rank extractors for polynomial sources. SIAM J. Comput. 38(6), 2144\u20132155 (2009). https:\/\/doi.org\/10.1137\/080715372","journal-title":"SIAM J. Comput."},{"key":"17_CR34","doi-asserted-by":"publisher","unstructured":"Dvir, Z., Gopi, S.: 2-server PIR with sub-polynomial communication. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, 14\u201317 June 2015, pp. 577\u2013584. ACM (2015). https:\/\/doi.org\/10.1145\/2746539.2746546","DOI":"10.1145\/2746539.2746546"},{"issue":"5","key":"17_CR35","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1137\/05063605X","volume":"36","author":"Z Dvir","year":"2007","unstructured":"Dvir, Z., Shpilka, A.: Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput. 36(5), 1404\u20131434 (2007). https:\/\/doi.org\/10.1137\/05063605X","journal-title":"SIAM J. Comput."},{"key":"17_CR36","doi-asserted-by":"publisher","unstructured":"Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology: Proceedings of CRYPTO \u20191982, Santa Barbara, California, USA, 23\u201325 August 1982, pp. 205\u2013210. Plenum Press, New York (1982). https:\/\/doi.org\/10.1007\/978-1-4757-0602-4_19","DOI":"10.1007\/978-1-4757-0602-4_19"},{"key":"17_CR37","doi-asserted-by":"publisher","unstructured":"Gilboa, N., Ishai, Y.: Distributed point functions and their applications. In: Nguyen, P.Q., Oswald, E. (eds.) Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, 11\u201315 May 2014. Proceedings. Lecture Notes in Computer Science, vol.\u00a08441, pp. 640\u2013658. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_35","DOI":"10.1007\/978-3-642-55220-5_35"},{"issue":"3","key":"17_CR38","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/S00037-006-0216-3","volume":"15","author":"O Goldreich","year":"2006","unstructured":"Goldreich, O., Karloff, H.J., Schulman, L.J., Trevisan, L.: Lower bounds for linear locally decodable codes and private information retrieval. Comput. Complex. 15(3), 263\u2013296 (2006). https:\/\/doi.org\/10.1007\/S00037-006-0216-3","journal-title":"Comput. Complex."},{"issue":"6","key":"17_CR39","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1137\/0222069","volume":"22","author":"O Goldreich","year":"1993","unstructured":"Goldreich, O., Krawczyk, H., Luby, M.: On the existence of pseudorandom generators. SIAM J. Comput. 22(6), 1163\u20131175 (1993). https:\/\/doi.org\/10.1137\/0222069","journal-title":"SIAM J. Comput."},{"issue":"1","key":"17_CR40","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/130938438","volume":"44","author":"I Haitner","year":"2015","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193\u2013242 (2015). https:\/\/doi.org\/10.1137\/130938438","journal-title":"SIAM J. Comput."},{"key":"17_CR41","unstructured":"Henzinger, A., Hong, M.M., Corrigan-Gibbs, H., Meiklejohn, S., Vaikuntanathan, V.: One server for the price of two: Simple and fast single-server private information retrieval. In: Calandrino, J.A., Troncoso, C. (eds.) 32nd USENIX Security Symposium, USENIX Security 2023, Anaheim, CA, USA, 9\u201311 August 2023, pp. 3889\u20133905. USENIX Association (2023)"},{"key":"17_CR42","unstructured":"Hollanti, C., Verma, N.: CB-cPIR: Code-based computational private information retrieval. arXiv preprint arXiv:2505.03407 (2025), full version of [60]. Available at https:\/\/arxiv.org\/pdf\/2505.03407. Accessed 19 January 2026"},{"key":"17_CR43","doi-asserted-by":"crossref","unstructured":"Holzbaur, L., Hollanti, C., Wachter-Zeh, A.: Computational code-based singleserver private information retrieval. In: 2020 IEEE International Symposium on Information Theory (ISIT), pp. 1065\u20131070. IEEE (2020)","DOI":"10.1109\/ISIT44484.2020.9174138"},{"key":"17_CR44","unstructured":"Ishai, Y., Prabhakaran, M., Sahai, A.: Secure arithmetic computation with no honest majority. IACR Cryptol. ePrint Arch, p.\u00a0465 (2008). http:\/\/eprint.iacr.org\/2008\/465"},{"key":"17_CR45","doi-asserted-by":"publisher","unstructured":"Kayal, N.: The complexity of the annihilating polynomial. In: 24th Annual IEEE Conference on Computational Complexity (CCC), pp. 184\u2013193. IEEE (2009). https:\/\/doi.org\/10.1109\/CCC.2009.37","DOI":"10.1109\/CCC.2009.37"},{"key":"17_CR46","doi-asserted-by":"publisher","unstructured":"Kerenidis, I., de\u00a0Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. In: Larmore, L.L., Goemans, M.X. (eds.) Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 9\u201311 June 2003, San Diego, CA, USA, pp. 106\u2013115. ACM (2003). https:\/\/doi.org\/10.1145\/780542.780560","DOI":"10.1145\/780542.780560"},{"key":"17_CR47","unstructured":"Kurmann, L., Lage, S., Weger, V.: Cryptanalysis of a pir scheme based on linear codes over rings (2026). https:\/\/arxiv.org\/abs\/2603.26409"},{"key":"17_CR48","doi-asserted-by":"publisher","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, 19\u201322 October 1997, pp. 364\u2013373. IEEE Computer Society (1997). https:\/\/doi.org\/10.1109\/SFCS.1997.646125","DOI":"10.1109\/SFCS.1997.646125"},{"key":"17_CR49","unstructured":"Lage, S., Bartz, H.: On the security of a code-based PIR scheme. arXiv preprint arXiv:2507.19295 (2025). https:\/\/www.arxiv.org\/pdf\/2507.19295 (accessed January 19, 2026)"},{"key":"17_CR50","doi-asserted-by":"publisher","unstructured":"Maurer, U.: Abstract models of computation in cryptography. In: Smart, N. (ed.) Cryptography and Coding 2005. Lecture Notes in Computer Science, vol. 3796, pp. 1\u201312. Springer (2005). https:\/\/doi.org\/10.1007\/11586821_1","DOI":"10.1007\/11586821_1"},{"key":"17_CR51","unstructured":"McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Progress Report 42\u201344, Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA (1978)"},{"key":"17_CR52","doi-asserted-by":"publisher","unstructured":"Melchor, C.A., Barrier, J., Fousse, L., Killijian, M.: XPIR: Private information retrieval for everyone. Proc. Priv. Enhancing Technol. 2016(2), 155\u2013174 (2016). https:\/\/doi.org\/10.1515\/POPETS-2016-0010","DOI":"10.1515\/POPETS-2016-0010"},{"key":"17_CR53","doi-asserted-by":"publisher","unstructured":"Menon, S.J., Wu, D.J.: SPIRAL: fast, high-rate single-server PIR via FHE composition. In: 43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, 22\u201326 May 2022, pp. 930\u2013947. IEEE (2022). https:\/\/doi.org\/10.1109\/SP46214.2022.9833700","DOI":"10.1109\/SP46214.2022.9833700"},{"key":"17_CR54","unstructured":"Menon, S.J., Wu, D.J.: YPIR: high-throughput single-server PIR with silent preprocessing. In: Balzarotti, D., Xu, W. (eds.) 33rd USENIX Security Symposium, USENIX Security 2024, Philadelphia, PA, USA, 14\u201316 August 2024. USENIX Association (2024). https:\/\/www.usenix.org\/conference\/usenixsecurity24\/presentation\/menon"},{"key":"17_CR55","doi-asserted-by":"crossref","unstructured":"Mughees, M.H., Chen, H., Ren, L.: OnionPIR: Response efficient single-server PIR. IACR Cryptol. ePrint Arch, p.\u00a01081 (2021). https:\/\/eprint.iacr.org\/2021\/1081","DOI":"10.1145\/3460120.3485381"},{"key":"17_CR56","doi-asserted-by":"publisher","unstructured":"Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: Vitter, J.S., Larmore, L.L., Leighton, F.T. (eds.) Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1\u20134 May 1999, Atlanta, Georgia, USA, pp. 245\u2013254. ACM (1999). https:\/\/doi.org\/10.1145\/301250.301312","DOI":"10.1145\/301250.301312"},{"issue":"1","key":"17_CR57","doi-asserted-by":"publisher","first-page":"221","DOI":"10.4086\/TOC.2007.V003A012","volume":"3","author":"AA Razborov","year":"2007","unstructured":"Razborov, A.A., Yekhanin, S.: An omega(n$$ ^{\\text{1\/3 }}$$) lower bound for bilinear group based private information retrieval. Theory Comput. 3(1), 221\u2013238 (2007). https:\/\/doi.org\/10.4086\/TOC.2007.V003A012","journal-title":"Theory Comput."},{"key":"17_CR58","doi-asserted-by":"publisher","unstructured":"Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) Advances in Cryptology\u2014EUROCRYPT \u20191997. Lecture Notes in Computer Science, vol.\u00a01233, pp. 256\u2013266. Springer (1997). https:\/\/doi.org\/10.1007\/3-540-69053-0_18","DOI":"10.1007\/3-540-69053-0_18"},{"key":"17_CR59","doi-asserted-by":"publisher","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3-4), 207\u2013388 (2010). https:\/\/doi.org\/10.1561\/0400000039","DOI":"10.1561\/0400000039"},{"key":"17_CR60","doi-asserted-by":"crossref","unstructured":"Verma, N., Hollanti, C.: Code-based single-server private information retrieval: Circumventing the sub-query attack. In: IEEE International Symposium on Information Theory, ISIT 2024, Athens, Greece, 7\u201312 July 2024, pp. 2880\u20132885. IEEE (2024), conference version of [42]","DOI":"10.1109\/ISIT57864.2024.10619469"},{"key":"17_CR61","doi-asserted-by":"crossref","unstructured":"Woodruff, D., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. In: 20th Annual IEEE Conference on Computational Complexity (CCC\u20192005), pp. 275\u2013284. IEEE (2005)","DOI":"10.1109\/CCC.2005.2"},{"key":"17_CR62","doi-asserted-by":"publisher","unstructured":"Zhou, M., Park, A., Zheng, W., Shi, E.: Piano: Extremely simple, single-server PIR with sublinear server computation. In: IEEE Symposium on Security and Privacy, SP 2024, San Francisco, CA, USA, 19\u201323 May 2024, pp. 4296\u20134314. IEEE (2024). https:\/\/doi.org\/10.1109\/SP54263.2024.00055","DOI":"10.1109\/SP54263.2024.00055"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2026"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-35428-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,12]],"date-time":"2026-08-12T10:08:31Z","timestamp":1786529311000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-35428-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032354273","9783032354280"],"references-count":62,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-35428-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 August 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","label":"Disclosure of Interests","group":{"name":"EthicsHeading","label":"Ethics"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"46","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}