{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:15:17Z","timestamp":1778040917843,"version":"3.51.4"},"reference-count":25,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T00:00:00Z","timestamp":1769126400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2026,4,21]]},"abstract":"<jats:p>Private information retrieval schemes enable users to privately retrieve files from a server without disclosing the content of their queries. In 2008, Aguilar Melchor and Gaborit proposed a PIR scheme that balances communication and server-side computational cost. For particularly small databases, Liu and Bi identified a vulnerability in the scheme using lattice-based methods. Nevertheless, the rapid increase in computational cost associated with the attack limited its practical applicability, leaving the scheme's overall security largely intact. In this paper, we present a novel two-stage attack that extends the work of Liu and Bi to databases of arbitrary sizes. To this end, we employ an innovative binary-search-like preprocessing technique, which enables a significant reduction in the number of lattice problems that need to be considered. We demonstrate how to compromise the scheme in a matter of minutes using an ordinary laptop. Our findings are substantiated through both rigorous analytical proofs and comprehensive numerical experiments.<\/jats:p>","DOI":"10.62056\/an-4c3tw9","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T18:09:08Z","timestamp":1777918148000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Cryptanalysis of a Lattice-Based PIR Scheme for Arbitrary Database Sizes"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-9026-863X","authenticated-orcid":false,"given":"Svenja","family":"Lage","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04bwf3e34","id-type":"ROR","asserted-by":"publisher"}],"name":"German Aerospace Center (DLR)","place":["Germany"],"department":["Institute of Communications and Navigation"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:PIR","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","article-title":"Private information retrieval","volume":"45","author":"Benny Chor","year":"1998","journal-title":"Journal of the ACM"},{"key":"ref2:KushilevitzOstrovsky","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1109\/SFCS.1997.646125","article-title":"Replication is NOT Needed: SINGLE Database,\n  Computationally-Private Information Retrieval","author":"Eyal Kushilevitz","year":"1997"},{"key":"ref3:CachinEtAl","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/3-540-48910-X_28","article-title":"Computationally Private Information Retrieval with\n  Polylogarithmic Communication","volume":"1592","author":"Christian Cachin","year":"1999"},{"key":"ref4:SionCarbunar","article-title":"On the Practicality of Private Information Retrieval","author":"Radu Sion","year":"2007"},{"key":"ref5:Shor","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","article-title":"Polynomial-Time Algorithms for Prime Factorization and\n  Discrete Logarithms on a Quantum Computer","volume":"26","author":"Peter W. Shor","year":"1997","journal-title":"SIAM Journal on Computing"},{"key":"ref6:SimplePIR","first-page":"3889","article-title":"One Server for the Price of Two: Simple and Fast\n  Single-Server Private Information Retrieval","author":"Alexandra Henzinger","year":"2023"},{"key":"ref7:XPIR","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1515\/popets-2016-0010","article-title":"XPIR : Private Information Retrieval for Everyone","volume":"avril 2016","author":"Carlos Aguilar Melchor","year":"2016","journal-title":"Proceedings on Privacy Enhancing Technologies"},{"key":"ref8:BrakerskiVaikuntanathan","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1109\/FOCS.2011.12","article-title":"Efficient Fully Homomorphic Encryption from (Standard)\n  LWE","author":"Zvika Brakerski","year":"2011"},{"key":"ref9:CodeBased1","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1109\/ISIT44484.2020.9174138","article-title":"Computational Code-Based Single-Server Private Information\n  Retrieval","author":"Lukas Holzbaur","year":"2020"},{"key":"ref10:CodeBased2","volume-title":"CB-cPIR: Code-based computational private information\n  retrieval","author":"Camilla Hollanti","year":"2025"},{"key":"ref11:OriginalScheme","doi-asserted-by":"publisher","first-page":"1848","DOI":"10.1109\/ISIT.2008.4595308","article-title":"A fast private information retrieval protocol","author":"Carlos Aguilar Melchor","year":"2008"},{"key":"ref12:Attack","series-title":"AsiaPKC '16","isbn-type":"print","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/2898420.2898427","article-title":"Cryptanalysis of a fast private information retrieval\n  protocol","author":"Jiayang Liu","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450342865"},{"key":"ref13:Ajtai","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/276698.276705","article-title":"The Shortest Vector Problem in L2 is NP-hard for\n  Randomized Reductions (Extended Abstract)","author":"Mikl\u00f3s Ajtai","year":"1998"},{"key":"ref14:NPcomplete","volume-title":"Another NP-complete partition problem and the complexity\n  of computing short vectors in a lattice","author":"Peter van Emde-Boas","year":"1981"},{"key":"ref15:Kannan","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1287\/moor.12.3.415","article-title":"Minkowski's Convex Body Theorem and Integer Programming","volume":"12","author":"Ravi Kannan","year":"1987","journal-title":"Mathematics of Operations Research"},{"key":"ref16:StudyKannan","isbn-type":"print","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/978-3-319-89500-0_47","article-title":"An Experimental Study of Kannan's Embedding Technique for\n  the Search LWE Problem","author":"Yuntao Wang","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319895000"},{"key":"ref17:MGbook","series-title":"The Springer International Series in Engineering and\n  Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of Lattice Problems: a cryptographic\n  perspective","volume":"671","author":"Daniele Micciancio","year":"2002"},{"key":"ref18:Chamizo1995","doi-asserted-by":"crossref","first-page":"417","DOI":"10.4171\/rmi\/178","article-title":"On the sphere problem","volume":"11","author":"Fernando Chamizo","year":"1995","journal-title":"Revista Matem\u00e1tica Iberoamericana"},{"key":"ref19:Odlyzko1990","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01571276","article-title":"Lattice points in high-dimensional spheres","volume":"110","author":"James E. Mazo","year":"1990","journal-title":"Monatshefte f\u00fcr Mathematik"},{"key":"ref20:LL","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Arjen K. Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref21:FastLLL","series-title":"ISSAC '16","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1145\/2930889.2930917","article-title":"Faster LLL-type Reduction of Lattice Bases","author":"Arnold Neumaier","year":"2016"},{"key":"ref22:BKZ","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and\n  solving subset sum problems","volume":"66","author":"Claus P. Schnorr","year":"1994","journal-title":"Mathematical Programming"},{"key":"ref23:Bordage2021","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s12095-021-00477-z","article-title":"On the privacy of a code-based single-server computational\n  PIR scheme","volume":"13","author":"Sarah Bordage","year":"2021"},{"key":"ref24:lage2025securitycodebasedpirscheme","volume-title":"On the Security of a Code-Based PIR Scheme","author":"Svenja Lage","year":"2025"},{"key":"ref25:sage","volume-title":"SageMath, the Sage Mathematics Software System\n  (Version 10.3)","author":"The Sage Developers","year":"2024"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:02:36Z","timestamp":1778040156000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":25,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/an-4c3tw9","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"2026-01-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-31"}}