Cryptanalysis of a Lattice-Based PIR Scheme for Arbitrary Database Sizes

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.