{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:53:14Z","timestamp":1787323994304,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":65,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101019547"],"award-info":[{"award-number":["101019547"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002803","name":"Fondazione Cariplo","doi-asserted-by":"publisher","award":["2021-3641"],"award-info":[{"award-number":["2021-3641"]}],"id":[{"id":"10.13039\/501100002803","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800906","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2019-2029","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Secret-Key PIR from Random Linear Codes"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0955-1883","authenticated-orcid":false,"given":"Caicai","family":"Chen","sequence":"first","affiliation":[{"name":"Bocconi University, Milan, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4096-6305","authenticated-orcid":false,"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"},{"name":"AWS, New York City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5164-0315","authenticated-orcid":false,"given":"Tamer","family":"Mour","sequence":"additional","affiliation":[{"name":"AI4I, Turin, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3021-7150","authenticated-orcid":false,"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[{"name":"Bocconi University, Milan, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Theory of Cryptography Conference (TCC) 2025","author":"Abram Damiano","year":"2025","unstructured":"Damiano Abram, Giulio Malavolta, and Lawrence Roy. 2025. Slightly Sublinear Trapdoor Hash Functions and PIR from Low-Noise LPN. In Theory of Cryptography Conference (TCC) 2025. https:\/\/eprint.iacr.org\/2025\/416"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806716"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74143-5_6"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00145-"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_29"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22006-7_34"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3566049"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.98"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44598-6_4"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3719027.3765194"},{"key":"e_1_3_2_1_14_1","volume-title":"A note on the permuted puzzles toy conjecture. arXiv preprint arXiv:2108.07885","author":"Blackwell Keller","year":"2021","unstructured":"Keller Blackwell and Mary Wootters. 2021. A note on the permuted puzzles toy conjecture. arXiv preprint arXiv:2108.07885 (2021)."},{"key":"e_1_3_2_1_15_1","volume-title":"Lipton","author":"Blum Avrim","year":"1994","unstructured":"Avrim Blum, Merrick Furst, Michael Kearns, and Richard J. Lipton. 1994. Cryptographic Primitives Based on Hard Learning Problems. In Advances in Cryptology -CRYPTO' 93, Douglas R. Stinson (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 278-291."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49099-0_7"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30545-0_10"},{"key":"e_1_3_2_1_18_1","volume-title":"On the security of doubly efficient PIR. Cryptology ePrint Archive","author":"Boyle Elette","year":"2021","unstructured":"Elette Boyle, Justin Holmgren, Fermi Ma, and Mor Weiss. 2021. On the security of doubly efficient PIR. Cryptology ePrint Archive (2021)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36033-7_18"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70503-3_22"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17659-4_21"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Springer-Verlag Berlin Heidelberg 619-635. doi:10.1007\/978-3-030-17659-4_21 10.1007\/978-3-030-17659-4_21","DOI":"10.1007\/978-3-030-17659-4_21"},{"key":"e_1_3_2_1_23_1","volume-title":"Practical Secure Delegated Linear Algebra with Trapdoored Matrices. In Theory of Cryptography Conference. Springer.","author":"Braverman Mark","year":"2025","unstructured":"Mark Braverman and Stephen Newman. 2025. Practical Secure Delegated Linear Algebra with Trapdoored Matrices. In Theory of Cryptography Conference. Springer."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48910-X_28"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70503-3_23"},{"key":"e_1_3_2_1_26_1","volume-title":"Virtual Conference, Worldwide (Proceedings of Machine Learning Research","volume":"504","author":"Chen Aidao","year":"2021","unstructured":"Aidao Chen, Anindya De, and Aravindan Vijayaraghavan. 2021. Learning a mixture of two subspaces over finite fields. In Algorithmic Learning Theory, 16- 19 March 2021, Virtual Conference, Worldwide (Proceedings of Machine Learning Research, Vol. 132), Vitaly Feldman, Katrina Ligett, and Sivan Sabato (Eds.). PMLR, 481-504. http:\/\/proceedings.mlr.press\/v132\/chen21a.html"},{"key":"e_1_3_2_1_27_1","unstructured":"Caicai Chen Yuval Ishai Tamer Mour and Alon Rosen. 2025. Secret-Key PIR from Random Linear Codes. Cryptology ePrint Archive Paper 2025\/646. https: \/\/eprint.iacr.org\/2025\/646"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492461"},{"key":"e_1_3_2_1_29_1","first-page":"44","volume-title":"Zagreb","author":"Corrigan-Gibbs Henry","year":"2020","unstructured":"Henry Corrigan-Gibbs and Dmitry Kogan. 2020. Private information retrieval with sublinear online time. In Advances in Cryptology-EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part I 39. Springer, 44-75."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19571-6_10"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483562"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06944-"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45539-6_10"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536498"},{"key":"e_1_3_2_1_35_1","volume-title":"Cryptography based on the Hardness of Decoding. Ph. D. Dissertation","author":"D\u00f6ttling Nico","unstructured":"Nico D\u00f6ttling. 2014. Cryptography based on the Hardness of Decoding. Ph. D. Dissertation. Karlsruhe Institute of Technology. http:\/\/digbib.ubka.uni-karlsruhe. de\/volltexte\/1000041110"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520010"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_28"},{"key":"e_1_3_2_1_38_1","volume-title":"Scalable Multi-Server Private Information Retrieval. In Theory of Cryptography Conference (TCC)","author":"Ghoshal Ashrujit","year":"2025","unstructured":"Ashrujit Ghoshal, Baitian Li, Yaohua Ma, Chenxin Dai, and Elaine Shi. 2025. Scalable Multi-Server Private Information Retrieval. In Theory of Cryptography Conference (TCC) 2025."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613134"},{"key":"e_1_3_2_1_41_1","volume-title":"One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval. In 32nd USENIX Security Symposium, USENIX Security 2023","author":"Henzinger Alexandra","year":"2023","unstructured":"Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, and Vinod Vaikuntanathan. 2023. One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval. In 32nd USENIX Security Symposium, USENIX Security 2023, Anaheim, CA, USA, August 9-11, 2023, Joseph A. Calandrino and Carmela Troncoso (Eds.). USENIX Association, 3889-3905. https:\/\/www.usenix.org\/conference\/usenixsecurity23\/presentation\/henzinger"},{"key":"e_1_3_2_1_42_1","unstructured":"Alexandra Henzinger and Seyoon Ragavan. 2025. Two-Server Private Information Retrieval in Sublinear Time and Quasilinear Space. Cryptology ePrint Archive Paper 2025\/2008. https:\/\/eprint.iacr.org\/2025\/2008"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374438"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70936-7_31"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68400-5_5"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646125"},{"key":"e_1_3_2_1_49_1","unstructured":"Arthur Lazzaretti Zeyu Liu Ben Fisch and Charalampos Papamanthou. 2024. Multi-Server Doubly Efficient PIR. IACR Cryptol. ePrint Arch. (2024) 829. https: \/\/eprint.iacr.org\/2024\/829"},{"key":"e_1_3_2_1_50_1","unstructured":"Keewoo Lee. 2025. Barely Doubly-Efficient SimplePIR. Cryptology ePrint Archive Paper 2025\/1305. https:\/\/eprint.iacr.org\/2025\/1305"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91095-1_3"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585175"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/11556992_23"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-58751-1_6"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71677-8_26"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519956"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78023-3_14"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/SECPRI.2000.848445"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49649-"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2502.13065"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/06065773X"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84252-9_16"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34621-8_1"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30545-0_14"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:27:34Z","timestamp":1781216854000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":65,"alternative-id":["10.1145\/3798129.3800906","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800906","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}