Paper 2023/1072
Simple and Practical Amortized Sublinear Private Information Retrieval using Dummy Subsets
Abstract
Recent works in amortized sublinear Private Information Retrieval (PIR) have demonstrated great potential. Despite the inspiring progress, existing schemes in this new paradigm are still faced with various challenges and bottlenecks, including large client storage, high communication, poor practical efficiency, need for non-colluding servers, or restricted client query sequences. We present simple and practical amortized sublinear stateful private information retrieval schemes without these drawbacks using new techniques in hint construction and usage. In particular, we introduce a dummy set to the client's request to eliminate any leakage or correctness failures. Our techniques can work with two non-colluding servers or a single server. The resulting PIR schemes achieve practical efficiency. The online response overhead is only twice that of simply fetching the desired entry without privacy. For a database with $2^{28}$ entries of 32-byte, each query of our two-server scheme consumes 34 KB of communication and 2.7 milliseconds of computation, and each query of our single-server scheme consumes amortized 47 KB of communication and 4.5 milliseconds of computation. These results are one or more orders of magnitude better than prior works.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. The ACM Conference on Computer and Communications Security (CCS)
- DOI
- 10.1145/3658644.3690266
- Keywords
- Private information retrieval
- Contact author(s)
-
renling @ illinois edu
mughees @ illinois edu
is16 @ illinois edu - History
- 2024-09-28: last of 3 revisions
- 2023-07-10: received
- See all versions
- Short URL
- https://ia.cr/2023/1072
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1072,
author = {Ling Ren and Muhammad Haris Mughees and Sun I},
title = {Simple and Practical Amortized Sublinear Private Information Retrieval using Dummy Subsets},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1072},
year = {2023},
doi = {10.1145/3658644.3690266},
url = {https://eprint.iacr.org/2023/1072}
}
