{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:29:01Z","timestamp":1778128141061,"version":"3.51.4"},"publisher-location":"Cham","reference-count":84,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032122896","type":"print"},{"value":"9783032122902","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"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-12290-2_20","type":"book-chapter","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T22:07:10Z","timestamp":1764886030000},"page":"611-641","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Multi-server Doubly Efficient PIR in\u00a0the\u00a0Classical Model and\u00a0Beyond"],"prefix":"10.1007","author":[{"given":"Arthur","family":"Lazzaretti","sequence":"first","affiliation":[]},{"given":"Zeyu","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Ben","family":"Fisch","sequence":"additional","affiliation":[]},{"given":"Peihan","family":"Miao","sequence":"additional","affiliation":[]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"20_CR1","unstructured":"Ahmad, I., Yang, Y., Agrawal, D., Abbadi, A.E., Gupta, T.: Addra: metadata-private voice communication over fully untrusted infrastructure (2021)"},{"key":"20_CR2","unstructured":"Ali, A., et al.: Communication\u2013computation trade-offs in PIR, pp. 1811\u20131828 (2021)"},{"key":"20_CR3","unstructured":"Angel, S., Setty, S.: Unobservable communication over fully untrusted infrastructure. In: Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI 2016, pp. 551\u2013569. USENIX Association, USA (2016)"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Backes, M., ate, A., Maffei, M., Pecina, K.: ObliviAd: provably secure and practical online behavioral advertising. In: 2012 IEEE Symposium on Security and Privacy, pp. 257\u2013271 (2012). ISSN 2375-1207","DOI":"10.1109\/SP.2012.25"},{"key":"20_CR5","doi-asserted-by":"publisher","unstructured":"Beimel, A., Ishai, Y.: Information-theoretic private information retrieval: a unified construction. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 912\u2013926. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-48224-5_74","DOI":"10.1007\/3-540-48224-5_74"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., Raymond, J.-F.: Breaking the O(n1(2k-1)\/) barrier for information-theoretic private information retrieval, pp. 261\u2013270 (2002)","DOI":"10.1109\/SFCS.2002.1181949"},{"key":"20_CR7","doi-asserted-by":"publisher","unstructured":"Beimel, A., Ishai, Y., Malkin, T.: Reducing the servers computation in private information retrieval: PIR with preprocessing. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 55\u201373. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44598-6_4","DOI":"10.1007\/3-540-44598-6_4"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00145-004-0134-y","volume":"17","author":"A Beimel","year":"2004","unstructured":"Beimel, A., Ishai, Y., Malkin, T.: Reducing the servers\u2019 computation in private information retrieval: PIR with preprocessing. J. Cryptol. 17, 125\u2013151 (2004)","journal-title":"J. Cryptol."},{"issue":"3","key":"20_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00145-007-0424-2","volume":"20","author":"A Beimel","year":"2007","unstructured":"Beimel, A., Stahl, Y.: Robust information-theoretic private information retrieval. J. Cryptol. 20(3), 295\u2013321 (2007)","journal-title":"J. Cryptol."},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Bhargava, V., Ghosh, S., Guo, Z., Kumar, M., Umans, C.: Fast multivariate multipoint evaluation over all finite fields. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 221\u2013232 (2022). ISSN 2575-8454","DOI":"10.1109\/FOCS54457.2022.00028"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Bhargava, V., Ghosh, S., Kumar, M., Mohapatra, C.K.: Fast, algebraic multivariate multipoint evaluation in small characteristic and applications. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pp. 403\u2013415. Association for Computing Machinery, New York (2022)","DOI":"10.1145\/3519935.3519968"},{"key":"20_CR12","doi-asserted-by":"publisher","unstructured":"Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 337\u2013367. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46803-6_12","DOI":"10.1007\/978-3-662-46803-6_12"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Boyle, E., Ishai, Y., Pass, R., Wootters, M.: Can we access a database both locally and privately? (2017)","DOI":"10.1007\/978-3-319-70503-3_22"},{"key":"20_CR14","unstructured":"Chor, B., Gilboa, N., Naor, M.: Private information retrieval by keywords (1998). Report Number: 003"},{"key":"20_CR15","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval (1995)"},{"key":"20_CR16","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: 36th FOCS, pp. 41\u201350. IEEE Computer Society Press (1995)"},{"key":"20_CR17","unstructured":"Chu, H., Wang, X., Jia, Y.: Private signaling secure against actively corrupted servers. Cryptology ePrint Archive, Paper 2025\/1056 (2025)"},{"key":"20_CR18","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF02124750","volume":"5","author":"R Corless","year":"1996","unstructured":"Corless, R., Gonnet, G., Hare, D., Jeffrey, D., Knuth, D.: On the lambert W function. Adv. Comput. Math. 5, 329\u2013359 (1996)","journal-title":"Adv. Comput. Math."},{"key":"20_CR19","doi-asserted-by":"publisher","unstructured":"Corrigan-Gibbs, H., Henzinger, A., Kogan, D.: Single-server private information retrieval with sublinear amortized Time. In: Dunkelman, O., Dziembowski, S. (eds) EUROCRYPT 2022. LNCS, vol. 13276, pp. 3\u201333. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-07085-3_1","DOI":"10.1007\/978-3-031-07085-3_1"},{"key":"20_CR20","doi-asserted-by":"publisher","unstructured":"Corrigan-Gibbs, H., Kogan, D.: Private information retrieval with sublinear online time. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 44\u201375. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45721-1_3","DOI":"10.1007\/978-3-030-45721-1_3"},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 523\u2013535. ACM Press (2017)","DOI":"10.1145\/3133956.3133967"},{"key":"20_CR22","doi-asserted-by":"publisher","unstructured":"Faber, S., Jarecki, S., Kentros, S., Wei, B.: Three-party ORAM for secure computation. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015, Part I. LNCS, vol. 9452, pp. 360\u2013385. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48797-6_16","DOI":"10.1007\/978-3-662-48797-6_16"},{"key":"20_CR23","doi-asserted-by":"publisher","unstructured":"Falk, B.H., Noble, D., Ostrovsky, R.: 3-party distributed ORAM from oblivious set membership. In: Galdi, C., Jarecki, S. (eds.) SCN 2022. LNCS, vol. 13409, pp. 437\u2013461. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-14791-3_19","DOI":"10.1007\/978-3-031-14791-3_19"},{"key":"20_CR24","unstructured":"Falk, B.H., Noble, D., Ostrovsky, R.: MetaDORAM: info-theoretic distributed ORAM with less communication. Cryptology ePrint Archive, Report 2024\/011 (2024)"},{"key":"20_CR25","unstructured":"Falk, B.H., Ostrovsky, R., Shtepel, M., Zhang, J.: GigaDORAM: breaking the billion address barrier. In: Calandrino, J.A., Troncoso, C. (eds.) USENIX Security 2023, pp. 3871\u20133888. USENIX Association (2023)"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Fisch, B., Lazzaretti, A., Liu, Z., Papamanthou, C.: Single server PIR via homomorphic thorp shuffles. Cryptology ePrint Archive, Paper 2024\/482 (2024). https:\/\/eprint.iacr.org\/2024\/482","DOI":"10.1145\/3658644.3690326"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Fisch, B., Lazzaretti, A., Liu, Z., Papamanthou, C.: ThorPIR: single server PIR via homomorphic thorp shuffles. In: Luo, B., Liao, X., Xu, J., Kirda, E., Lie, D. (eds.) ACM CCS 2024, pp. 1448\u20131462. ACM Press (2024)","DOI":"10.1145\/3658644.3690326"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Fisch, B., Lazzaretti, A., Liu, Z., Papamanthou, C.: ThorPIR: single server PIR via homomorphic thorp shuffles. In: Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS 2024, pp. 1448\u20131462. Association for Computing Machinery, New York (2024)","DOI":"10.1145\/3658644.3690326"},{"key":"20_CR29","unstructured":"Gathen, J.V.Z., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, USA (2003)"},{"key":"20_CR30","unstructured":"Ghoshal, A., Li, B., Ma, Y., Dai, C., Shi, E.: Information-theoretic multi-server PIR with global preprocessing. Cryptology ePrint Archive, Paper 2024\/765 (2024). Version: 20240519:202013"},{"key":"20_CR31","unstructured":"Ghoshal, A., Li, B., Ma, Y., Dai, C., Shi, E.: Scalable multi-server private information retrieval. Cryptology ePrint Archive, Paper 2024\/765 (2024)"},{"key":"20_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1007\/978-3-642-55220-5_35","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"N Gilboa","year":"2014","unstructured":"Gilboa, N., Ishai, Y.: Distributed point functions and their applications. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 640\u2013658. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_35"},{"key":"20_CR33","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, a.: How to play ANY mental game. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 218\u2013229. Association for Computing Machinery, New York ( 1987)","DOI":"10.1145\/28395.28420"},{"issue":"3","key":"20_CR34","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/233551.233553","volume":"43","author":"O Goldreich","year":"1996","unstructured":"Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431\u2013473 (1996)","journal-title":"J. ACM"},{"key":"20_CR35","doi-asserted-by":"crossref","unstructured":"Gong, T., Henry, R., Psomas, A., Kate, A.: Relax the non-collusion assumption for multi-server PIR. In: S &P 2024 (2024)","DOI":"10.1109\/SP54263.2024.00095"},{"key":"20_CR36","unstructured":"Gupta, T., Crooks, N., Mulhern, W., Setty, S., Alvisi, L., Walfish, M.: Scalable and private media consumption with Popcorn. In: Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation, NSDI 2016, pp. 91\u2013107. USENIX Association, USA (2016)"},{"key":"20_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-030-75248-4_18","volume-title":"Public-Key Cryptography \u2013 PKC 2021","author":"A Hamlin","year":"2021","unstructured":"Hamlin, A., Varia, M.: Two-server distributed ORAM with sublinear computation and constant rounds. In: Garay, J.A. (ed.) PKC 2021, Part II. LNCS, vol. 12711, pp. 499\u2013527. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-75248-4_18"},{"key":"20_CR38","doi-asserted-by":"publisher","unstructured":"Hemenway, B., Noble, D., Ostrovsky, R., Shtepel, M., Zhang, J.: DORAM revisited: Maliciously secure RAM-MPC with logarithmic overhead. In: Rothblum, G.N., Wee, H. (eds.) TCC 2023, Part I. LNCS, vol. 14369, pp. 441\u2013470. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-48615-9_16","DOI":"10.1007\/978-3-031-48615-9_16"},{"key":"20_CR39","doi-asserted-by":"crossref","unstructured":"Henzinger, A., Dauterman, E., Corrigan-Gibbs, H., Zeldovich, N.: Private Web Search with Tiptoe. In: Proceedings of the 29th Symposium on Operating Systems Principles, SOSP 2023, pp. 396\u2013416. Association for Computing Machinery, New York (2023)","DOI":"10.1145\/3600006.3613134"},{"key":"20_CR40","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, p. 27 (2022)"},{"key":"20_CR41","doi-asserted-by":"crossref","unstructured":"Hetz, L., Schneider, T., Weinert, C.: Scaling mobile private contact discovery to billions of users (2023). Publication info: Published elsewhere. Minor revision. ESORICS 2023","DOI":"10.1007\/978-3-031-50594-2_23"},{"key":"20_CR42","doi-asserted-by":"crossref","unstructured":"Holmgren, J., Canetti, R., Richelson, S.: Towards doubly efficient private information retrieval. Technical report 568 (2017)","DOI":"10.1007\/978-3-319-70503-3_23"},{"key":"20_CR43","doi-asserted-by":"publisher","unstructured":"Hoover, A., Patel, S., Persiano, G., Yeo, K.: Plinko: Single-server PIR with efficient updates via invertible PRFs. In: Fehr, S., Fouque, PA. (eds) EUROCRYPT 2025. LNCS, vol. 15606, pp. 3\u201333. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-91095-1_1","DOI":"10.1007\/978-3-031-91095-1_1"},{"key":"20_CR44","doi-asserted-by":"crossref","unstructured":"Jakkamsetti, S., Liu, Z., Madathil, V.: Scalable private signaling. CSF 2025 (2025)","DOI":"10.1109\/CSF64896.2025.00035"},{"key":"20_CR45","doi-asserted-by":"publisher","unstructured":"Jarecki, S., Wei, B.: 3PC ORAM with low latency, low bandwidth, and fast batch retrieval. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 360\u2013378. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-93387-0_19","DOI":"10.1007\/978-3-319-93387-0_19"},{"key":"20_CR46","doi-asserted-by":"crossref","unstructured":"Jia, Y., Madathil, V., Kate, A.: HomeRun: high-efficiency oblivious message retrieval, unrestricted. In: CCS 2024 (2024)","DOI":"10.1145\/3658644.3670381"},{"issue":"6","key":"20_CR47","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1137\/08073408X","volume":"40","author":"KS Kedlaya","year":"2011","unstructured":"Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767\u20131802 (2011)","journal-title":"SIAM J. Comput."},{"key":"20_CR48","unstructured":"Kogan, D., Corrigan-Gibbs, H.: Private blocklist lookups with checklist. In: 30th USENIX Security Symposium (USENIX Security 2021). USENIX Association (2021)"},{"key":"20_CR49","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: FOCS 1997 (1997)"},{"key":"20_CR50","doi-asserted-by":"publisher","unstructured":"Lazzaretti, A., Papamanthou, C.: Near-optimal private information retrieval with preprocessing. In: Rothblum, G.N., Wee, H. (eds.) TCC 2023, Part II. LNCS, vol. 14370, pp. 406\u2013435. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-48618-0_14","DOI":"10.1007\/978-3-031-48618-0_14"},{"key":"20_CR51","doi-asserted-by":"publisher","unstructured":"Lazzaretti, A., Papamanthou, C.: TreePIR: Sublinear-time and polylog-bandwidth private information retrieval from DDH. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. Part II. LNCS, vol. 14082, pp. 284\u2013314. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38545-2_10","DOI":"10.1007\/978-3-031-38545-2_10"},{"key":"20_CR52","unstructured":"Lazzaretti, A., Papamanthou, C.: Single pass client preprocessing private information retrieval. In: USENIX Security 2024 (2024)"},{"key":"20_CR53","unstructured":"Lazzaretti, A., Papamanthou, C.: Single pass client-preprocessing private information retrieval. In: Balzarotti, D. Xu, W. (eds.) USENIX Security 2024. USENIX Association (2024)"},{"key":"20_CR54","unstructured":"Lee, K., Yeo, Y.: SophOMR: improved oblivious message retrieval from SIMD-aware homomorphic compression. Cryptology ePrint Archive, Report 2024\/1814 (2024)"},{"key":"20_CR55","doi-asserted-by":"crossref","unstructured":"Lin, W.-K., Mook, E., Wichs, D.: Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE (2022). Report Number: 1703","DOI":"10.1145\/3564246.3585175"},{"key":"20_CR56","doi-asserted-by":"publisher","unstructured":"Liu, Z., Sotiraki, K., Tromer, E., Wang, Y.: Snake-eye resistant PKE from LWE for oblivious message retrieval and robust encryption. In: Fehr, S., Fouque, P.-A. (eds.) EUROCRYPT 2025, Part III. LNCS, vol. 15603, pp. 126\u2013156. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-031-91131-6_5","DOI":"10.1007\/978-3-031-91131-6_5"},{"key":"20_CR57","doi-asserted-by":"publisher","unstructured":"Liu, Z., Tromer, E.: Oblivious message retrieval. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology \u2013 CRYPTO 2022. LNCS, vol. 13507, pp. 753\u2013783. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15802-5_26. Cryptology ePrint Archive 2021; internal citations follow the latter\u2019s numbering","DOI":"10.1007\/978-3-031-15802-5_26"},{"key":"20_CR58","doi-asserted-by":"crossref","unstructured":"Liu, Z., Tromer, E., Wang, Y.: Group oblivious message retrieval. In: 2024 IEEE Symposium on Security and Privacy, pp. 4367\u20134385. IEEE Computer Society Press (2024)","DOI":"10.1109\/SP54263.2024.00115"},{"key":"20_CR59","doi-asserted-by":"crossref","unstructured":"Liu, Z., Tromer, E., Wang, Y.: PerfOMR: oblivious message retrieval with reduced communication and computation. In: Balzarotti, D., Xu, W. (eds.) USENIX Security 2024. USENIX Association (2024)","DOI":"10.1109\/SP54263.2024.00115"},{"key":"20_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/978-3-642-36594-2_22","volume-title":"Theory of Cryptography","author":"S Lu","year":"2013","unstructured":"Lu, S., Ostrovsky, R.: Distributed oblivious RAM for secure two-party computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 377\u2013396. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36594-2_22"},{"key":"20_CR61","unstructured":"Ma, Y., Ke, Z., Rabin, T., Angel, S.: Incremental offline\/online PIR (extended version). In: USENIX Security 2022 (2022)"},{"key":"20_CR62","doi-asserted-by":"crossref","unstructured":"Menon, S.J., Wu, D.J.: Spiral: fast, high-rate single-server PIR via FHE composition. In: IEEE Symposium on Security and Privacy 2022 (2022)","DOI":"10.1109\/SP46214.2022.9833700"},{"key":"20_CR63","unstructured":"Mittal, P., Olumofin, F., Troncoso, C., Borisov, N., Goldberg, I.: PIR-Tor: scalable anonymous communication using private information retrieval (2011)"},{"key":"20_CR64","doi-asserted-by":"crossref","unstructured":"Mughees, M.H., Chen, H., Ren, L.: OnionPIR: response efficient single-server PIR. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, CCS 2021, pp. 2292\u20132306. Association for Computing Machinery, New York (2021)","DOI":"10.1145\/3460120.3485381"},{"key":"20_CR65","unstructured":"Nagell, T.: Introduction to Number Theory. American Mathematical Society (1964). Google-Books-ID: Znc5EAAAQBAJ"},{"key":"20_CR66","doi-asserted-by":"publisher","unstructured":"Okada, H., Player, R., Pohmann, S., Weinert, C.: Towards practical doubly-efficient private information retrieval. In: Clark, J., Shi, E. (eds.) FC 2024. LNCS, vol. 14745, pp. 264\u2013282. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-031-78679-2_14","DOI":"10.1007\/978-3-031-78679-2_14"},{"key":"20_CR67","doi-asserted-by":"publisher","unstructured":"Okada, H., Player, R., Pohmann, S., Weinert, C.: On algebraic homomorphic encryption and its applications to doubly-efficient PIR. In: Fehr, S., Fouque, PA. (eds.) EUROCRYPT 2025. LNCS, vol. 15606. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-031-91095-1_2. ISSN 1611-3349","DOI":"10.1007\/978-3-031-91095-1_2"},{"key":"20_CR68","doi-asserted-by":"crossref","unstructured":"Patel, S., Persiano, G., Yeo, K.: Private stateful information retrieval. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, pp. 1002\u20131019. Association for Computing Machinery, New York (2018)","DOI":"10.1145\/3243734.3243821"},{"key":"20_CR69","doi-asserted-by":"crossref","unstructured":"Persiano, G., Yeo, K.: Limits of preprocessing for single-server PIR. Technical Report 235 (2022)","DOI":"10.1137\/1.9781611977073.99"},{"key":"20_CR70","doi-asserted-by":"crossref","unstructured":"Ren, L., Mughees, M.H., Sun, I.: Simple and practical amortized sublinear private information retrieval using dummy subsets. In: Luo, B., Liao, X., Xu, J., Kirda, E., Lie, D. (eds.) ACM CCS 2024, pp. 1420\u20131433. ACM Press (2024)","DOI":"10.1145\/3658644.3690266"},{"issue":"11","key":"20_CR71","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Commun. ACM 22(11), 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"key":"20_CR72","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/978-3-030-84259-8_22","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"E Shi","year":"2021","unstructured":"Shi, E., Aqeel, W., Chandrasekaran, B., Maggs, B.: Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 641\u2013669. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84259-8_22"},{"key":"20_CR73","doi-asserted-by":"crossref","unstructured":"Stefanov, E., et al.: Path ORAM: an extremely simple oblivious RAM protocol. J. ACM 65(4), 18:1\u201318:26 (2018)","DOI":"10.1145\/3177872"},{"key":"20_CR74","unstructured":"Vadapalli, A., Henry, R., Goldberg, I.: Duoram: a bandwidth-efficient distributed ORAM for 2- and 3-party computation. In: Calandrino, J.A., Troncoso, C. (eds.) USENIX Security 2023, pp. 3907\u20133924. USENIX Association (2023)"},{"key":"20_CR75","doi-asserted-by":"publisher","unstructured":"Wang, Z., Ren, L.: Single-server client preprocessing PIR with tight space-time trade-off. In: Fehr, S., Fouque, P.-A. (eds.) EUROCRYPT 2025, Part VI. LNCS, vol. 15606, pp. 94\u2013122. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-031-91095-1_4","DOI":"10.1007\/978-3-031-91095-1_4"},{"key":"20_CR76","unstructured":"Woodruff, D., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval (2005)"},{"key":"20_CR77","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Protocols for secure computations. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, SFCS 1982, pp. 160\u2013164. IEEE Computer Society, USA (1982)","DOI":"10.1109\/SFCS.1982.38"},{"issue":"1","key":"20_CR78","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1326554.1326555","volume":"55","author":"S Yekhanin","year":"2008","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. J. ACM 55(1), 1\u201316 (2008)","journal-title":"J. ACM"},{"key":"20_CR79","doi-asserted-by":"publisher","unstructured":"Yekhanin, S.: Locally Decodable Codes and Private Information Retrieval Schemes. Information Security and Cryptography. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14358-8","DOI":"10.1007\/978-3-642-14358-8"},{"key":"20_CR80","doi-asserted-by":"crossref","unstructured":"Zahur, S., et al.: Revisiting square-root ORAM: efficient random access in multi-party computation. In: 2016 IEEE Symposium on Security and Privacy, pp. 218\u2013234. IEEE Computer Society Press (2016)","DOI":"10.1109\/SP.2016.21"},{"key":"20_CR81","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1016\/j.ins.2020.08.071","volume":"546","author":"L Zhao","year":"2021","unstructured":"Zhao, L., Wang, X., Huang, X.: Verifiable single-server private information retrieval from LWE with binary errors. Inf. Sci. 546, 897\u2013923 (2021)","journal-title":"Inf. Sci."},{"key":"20_CR82","doi-asserted-by":"crossref","unstructured":"Zhou, M., Lin, W.-K., Tselekounis, Y., Shi, E.: Optimal single-server private information retrieval. ePrint IACR (2022)","DOI":"10.1007\/978-3-031-30545-0_14"},{"key":"20_CR83","doi-asserted-by":"publisher","unstructured":"Zhou, M., Lin, W.-K., Tselekounis, Y., Shi, E.: Optimal single-server private information retrieval. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part I. LNCS, vol. 14004, pp. 395\u2013425. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30545-0_14","DOI":"10.1007\/978-3-031-30545-0_14"},{"key":"20_CR84","doi-asserted-by":"crossref","unstructured":"Zhou, M., Park, A., Shi, E., Zheng, W.: Piano: extremely simple, single-server PIR with sublinear server computation. In: 2023 IEEE S &P (2024)","DOI":"10.1109\/SP54263.2024.00055"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-12290-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T22:07:14Z","timestamp":1764886034000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-12290-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,5]]},"ISBN":["9783032122896","9783032122902"],"references-count":84,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-12290-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,5]]},"assertion":[{"value":"5 December 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Aarhus","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Denmark","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 December 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 December 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}