Paper 2025/1313
Two-Server Sublinear PIR with Symmetric Privacy and Statistical Security
Abstract
The field of private information retrieval (PIR) has made significant strides with a recent focus on protocols that offer sublinear online time, ensuring efficient access to public databases without compromising the privacy of the queries. The pioneering two-server PIR protocols developed by Corrigan-Gibbs and Kogan (EUROCRYPT 2020) enjoy the dual benefits of sublinear online time and statistical security. This allows their protocols to provide high efficiency and resist computationally unbounded adversaries. In this work, we extend this seminal work to the symmetric PIR (SPIR) context, where the protocol must ensure that the client is privy only to the requested database entries, with no knowledge of the remaining data. This enhancement aligns with scenarios where the confidentiality of non-requested information is as critical as the query itself. Our main result is the introduction of the first two-server SPIR protocols that achieve both sublinear online time and statistical security, together with an enhancement for achieving sublinear amortized time. Our protocols require a pragmatic level of shared randomness between the servers, which however is necessary for implementing statistical security in two-server SPIR, as showed by Gertner et al. (STOC 1998).
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Contact author(s)
-
liss @ zgclab edu cn
anyuwang @ tsinghua edu cn
zhangcong @ tsinghua edu cn
xiaoyunwang @ tsinghua edu cn - History
- 2025-07-19: approved
- 2025-07-18: received
- See all versions
- Short URL
- https://ia.cr/2025/1313
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1313,
author = {Shuaishuai Li and Anyu Wang and Cong Zhang and Xiaoyun Wang},
title = {Two-Server Sublinear {PIR} with Symmetric Privacy and Statistical Security},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1313},
year = {2025},
url = {https://eprint.iacr.org/2025/1313}
}
