Crust: Verifiable and Efficient Private Information Retrieval With Sublinear Online Time

Yinghao Wang; Xuanming Liu; Jiawen Zhang; Jian Liu; Xiaohu Yang

Paper 2023/1607

Crust: Verifiable and Efficient Private Information Retrieval With Sublinear Online Time

Yinghao Wang, Zhejiang University

Xuanming Liu, Zhejiang University

Jiawen Zhang

Jian Liu, Zhejiang University

Xiaohu Yang, Zhejiang University

Abstract

Private Information Retrieval (PIR) is a cryptographic primitive that allows a user to access data from a database without disclosing the specific information being requested, thereby safeguarding privacy. PIR schemes suffer from a significant computational burden. By running an offline preprocessing phase, PIR schemes can achieve sublinear online computation. While protocols for semi-honest servers have been well-studied in both single-server and multi-server scenarios, scant attention has been given to scenarios involving malicious servers. In this study, we introduce a straightforward yet efficient sublinear PIR scheme named Crust. The scheme is tailored for verifiability and ensures privacy and data integrity against malicious servers. Our proposal is designed to function under two configurations: (i) with two non-colluding servers, or (ii) with a standalone single server. Apart from its verifiability, our scheme demonstrates notable efficiency. Regarding online computation efficiency, our scheme outperforms state-of-the-art two-server schemes by a factor of 16 and single-server sublinear PIR schemes by a factor of 6. Furthermore, relative to leading verifiable PIR schemes, our scheme showcases approximately 1000 times greater efficiency. To the best of our knowledge, this is the first PIR scheme to achieve both verifiability and amortized $O(\sqrt{n})$ online computation.

Note: Rewrite most of the paper

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Private Information Retrieval PIR Malicious Security
Contact author(s): asternight @ zju edu cn
hinsliu @ zju edu cn
History: 2024-03-04: last of 2 revisions; 2023-10-17: received; See all versions
Short URL: https://ia.cr/2023/1607
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1607,
      author = {Yinghao Wang and Xuanming Liu and Jiawen Zhang and Jian Liu and Xiaohu Yang},
      title = {Crust: Verifiable and Efficient Private Information Retrieval With Sublinear Online Time},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1607},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1607}},
      url = {https://eprint.iacr.org/2023/1607}
}