Paper 2023/1072
Simple and Practical Amortized Sublinear Private Information Retrieval
Abstract
Recent works in amortized sublinear 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 lightweight amortized sublinear stateful private information retrieval schemes without these drawbacks using new techniques in hint construction and usage. Our scheme can work with two non-colluding servers or a single server. Our schemes achieve close to optimal amortized or online response overhead, which is only two or four times that of simply fetching the desired entry without privacy. Our schemes have practical efficiency. For an 8 GB database with 32-byte entries, 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
- Preprint.
- Keywords
- Private information retrieval
- Contact author(s)
-
mughees @ illinois edu
is16 @ illinois edu
renling @ illinois edu - History
- 2023-08-07: last of 2 revisions
- 2023-07-10: received
- See all versions
- Short URL
- https://ia.cr/2023/1072
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1072,
author = {Muhammad Haris Mughees and Sun I and Ling Ren},
title = {Simple and Practical Amortized Sublinear Private Information Retrieval},
howpublished = {Cryptology ePrint Archive, Paper 2023/1072},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1072}},
url = {https://eprint.iacr.org/2023/1072}
}
