Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.05934 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913828457938944 |
|---|---|
| author | Lage, Svenja |
| author_facet | Lage, Svenja |
| contents | Private Information Retrieval (PIR) schemes enable users to securely retrieve files from a server without disclosing the content of their queries, thereby preserving their privacy. In 2008, Melchor and Gaborit proposed a PIR scheme that achieves a balance between communication overhead and server-side computational cost. However, 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 a binary-search-like preprocessing technique, which enables a significant reduction in the number of lattice problems that need to be considered. Specifically, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05934 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cryptanalysis of a Lattice-Based PIR Scheme for Arbitrary Database Sizes Lage, Svenja Cryptography and Security Private Information Retrieval (PIR) schemes enable users to securely retrieve files from a server without disclosing the content of their queries, thereby preserving their privacy. In 2008, Melchor and Gaborit proposed a PIR scheme that achieves a balance between communication overhead and server-side computational cost. However, 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 a binary-search-like preprocessing technique, which enables a significant reduction in the number of lattice problems that need to be considered. Specifically, 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. |
| title | Cryptanalysis of a Lattice-Based PIR Scheme for Arbitrary Database Sizes |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2505.05934 |