Paper 2026/243
Towards Making Doubly-Efficient PIR Practical
Abstract
Doubly-efficient private information retrieval (DEPIR) enables sublinear per-query work (in the database size $N$) for both client and server, while requiring no client state. Despite its theoretical promise, single-server DEPIR exhibits a prohibitive concrete efficiency gap: for $N=2^{23}$, the state-of-the-art construction (Eurocrypt '25) requires a 733TB server state and over $2^{37}$ online RAM/Disk reads, rending it infeasible to execute. This paper advances single-server DEPIR towards practicality through a series of algorithmic innovations. Compared with the state-of-the-art, we achieve a 4 orders of magnitude reduction in server state and a 6 orders of magnitude reduction in query time. In particular, for the same level database ($N=2^{23}$), querying $5461$ elements in a single batch requires only 171GB of server state and $2^{24}$ online RAM/disk reads, yielding a 112s total query time and a 21ms amortized query time.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Private Information RetrievalPIRHomomorphic Encryption
- Contact author(s)
-
pan xiao @ zju edu cn
huntianddy @ gmail com
12521213 @ zju edu cn
0022090 @ zju edu cn
liujian2411 @ zju edu cn
kuiren @ zju edu cn
chenc @ zju edu cn - History
- 2026-02-16: revised
- 2026-02-13: received
- See all versions
- Short URL
- https://ia.cr/2026/243
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/243,
author = {Pan Xiao and Heng Zhang and Rending Ouyang and Cong Zhang and Jian Liu and Kui Ren and Chun Chen},
title = {Towards Making Doubly-Efficient {PIR} Practical},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/243},
year = {2026},
url = {https://eprint.iacr.org/2026/243}
}
