Paper 2024/964

Malicious Security for PIR (almost) for Free

Brett Falk, University of Pennsylvania
Pratyush Mishra, University of Pennsylvania
Matan Shtepel, University of Pennsylvania
Abstract

Private Information Retrieval (PIR) enables a client to retrieve a database element from a semi-honest server while hiding the element being queried from the server. Maliciously-secure PIR (mPIR) [Colombo et al., USENIX Security '23] strengthens the guarantees of plain (i.e., semi-honest) PIR by ensuring that even a misbehaving server (a) cannot compromise client privacy via selective-failure attacks, and (b) must answer every query *consistently* (i.e., with respect to the same database). These additional security properties are crucial for many real-world applications. In this work we present a generic compiler that transforms any PIR scheme into an mPIR scheme in a black-box manner, minimal overhead, and without requiring additional cryptographic assumptions. Since mPIR trivially implies PIR, our compiler establishes the equivalence of mPIR and PIR. By instantiating our compiler with existing PIR schemes, we immediately obtain mPIR schemes with $O(N^\epsilon)$ communication cost. In fact, by applying our compiler to a recent doubly-efficient PIR [Lin et al., STOC '23], we are able to construct a *doubly-efficient* mPIR scheme that requires only $\text{polylog}(N)$ communication and server and client computation. In comparison, all prior work incur a $\Omega(\sqrt{N})$ cost in these metrics. Our compiler makes use of smooth locally-decodable codes (LDCs) that have a robust decoding procedure. We term these codes "subcode"-LDCs, because they are LDCs where the query responses are from an error-correcting code. This property is shared by Reed--Muller codes (whose query responses are Reed--Solomon codewords) and more generally lifted codes. Applying our compiler requires us to consider decoding in the face of *non-signaling adversaries*, for reasons analogous to the need for non-signaling PCPs in the succinct-argument literature. We show how to construct such decoders for Reed--Muller codes, and more generally for smooth locally-decodable codes that have a robust decoding procedure.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Private Information RetrievalPIRLocally Decodable CodesLDCsMalicious Security
Contact author(s)
fbrett @ cis upenn edu
prat @ upenn edu
matan shtepel @ gmail com
History
2024-06-18: last of 3 revisions
2024-06-14: received
See all versions
Short URL
https://ia.cr/2024/964
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/964,
      author = {Brett Falk and Pratyush Mishra and Matan Shtepel},
      title = {Malicious Security for {PIR} (almost) for Free},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/964},
      year = {2024},
      url = {https://eprint.iacr.org/2024/964}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.