Paper 2025/300

Pseudorandom Functions with Weak Programming Privacy and Applications to Private Information Retrieval

Ashrujit Ghoshal, Carnegie Mellon University
Mingxun Zhou, Carnegie Mellon University
Elaine Shi, Carnegie Mellon University
Bo Peng, Peking University
Abstract

Although privately programmable pseudorandom functions (PPPRFs) are known to have numerous applications, so far, the only known constructions rely on Learning with Error (LWE) or indistinguishability obfuscation. We show how to construct a relaxed PPPRF with only one-way functions (OWF). The resulting PPPRF satisfies security and works for polynomially sized input domains. Using the resulting PPPRF, we can get new results for preprocessing Private Information Retrieval (PIR) that improve the state of the art. Specifically, we show that relying only on OWF, we can get a 2-server preprocessing PIR with polylogarithmic bandwidth while consuming client space and server space for an arbitrarily small constant . In the 1-server setting, we get a preprocessing PIR from OWF that achieves polylogarithmic online bandwidth and offline bandwidth, while preserving the same client and server space as before. Our result, in combination with the lower bound of Ishai, Shi, and Wichs (CRYPTO'24), establishes a tight understanding of the bandwidth and client space tradeoff for 1-server preprocessing PIR from Minicrypt assumptions. Interestingly, we are also the first to show non-trivial ways to combine client-side and server-side preprocessing to get improved results for PIR.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2025
Keywords
PIR
Contact author(s)
aghoshal @ andrew cmu edu
mingxunz @ andrew cmu edu
rshi @ andrew cmu edu
bo peng @ stu pku edu cn
History
2025-02-21: approved
2025-02-20: received
See all versions
Short URL
https://ia.cr/2025/300
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/300,
      author = {Ashrujit Ghoshal and Mingxun Zhou and Elaine Shi and Bo Peng},
      title = {Pseudorandom Functions with Weak Programming Privacy and Applications to Private Information Retrieval},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/300},
      year = {2025},
      url = {https://eprint.iacr.org/2025/300}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.