Paper 2025/552
Black Box Crypto is Useless for Doubly Efficient PIR
Abstract
A (single server) private information retrieval (PIR) allows a client to read data from a public database held on a remote server, without revealing to the server which locations she is reading. In a doubly efficient PIR (DEPIR), the database is first preprocessed offline into a data structure, which then allows the server to answer any client query efficiently in sub-linear online time. Constructing DEPIR is a notoriously difficult problem, and this difficulty even extends to a weaker notion secret-key DEPIR (SK-DEPIR), where the database is preprocessed using secret randomness and the client is given a secret key for making queries. We currently only have constructions of SK-DEPIR from the Ring LWE assumption or from non-standard code-based assumptions. We show that the black-box use of essentially all generic cryptographic primitives (e.g., key agreement, oblivious transfer, indistinguishability obfuscation, etc.), including idealized primitives (e.g., random oracles, generic multilinear groups, virtual black-box obfuscation, etc.) is essentially useless for constructing SK-DEPIR. In particular, in any such SK-DEPIR construction, we can replace all black-box use of these primitives with just a black-box use of one-way functions. While we conjecture that SK-DEPIR cannot be constructed using black-box one-way functions alone, we are unable to show this in its full generality. However, we do show this for 2-round schemes with a passive server that simply outputs requested locations in the preprocessed data structure, which is the format of all known schemes. Overall, this shows that the black-box use of essentially all crypto primitives is insufficient for constructing 2-round passive-server SK-DEPIR, and does not provide any benefit beyond black-box one-way functions for constructing general SK-DEPIR.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2025
- Keywords
- depir
- Contact author(s)
-
wklin @ virginia edu
mook e @ northeastern edu
wichs @ ccs neu edu - History
- 2025-03-27: approved
- 2025-03-25: received
- See all versions
- Short URL
- https://ia.cr/2025/552
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/552, author = {Wei-Kai Lin and Ethan Mook and Daniel Wichs}, title = {Black Box Crypto is Useless for Doubly Efficient {PIR}}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/552}, year = {2025}, url = {https://eprint.iacr.org/2025/552} }