CryptoDB
Malicious Security for PIR (almost) for Free
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | Using Private Information Retrieval (PIR), a client can retrieve a database element from a semi-honest server without leaking which element was queried. 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 with respect to the same database. These additional security properties are crucial for many real-world applications. In this work we present a compiler that transforms _any_ single-server PIR scheme into an mPIR scheme in a black-box manner with minimal overhead and by relying only on collision-resistant hash functions. Since single-server PIR implies collision-resistant hash functions, our transformation requires _no_ additional cryptographic assumptions, establishing the equivalence of mPIR and PIR. Instantiating our compiler with appropriate base PIR schemes gives the first constructions of mPIR under assumptions such as Decisional Composite Residuosity, Quadratic Residuosity, and $\phi$-hiding. Efficiency-wise, our compiler yields mPIR schemes with $O(N^\varepsilon)$ communication and $O(1)$ computation overhead. Applying a slight tweak of our compiler to the recent breakthrough construction of doubly-efficient PIR [Lin et al., STOC '23], we construct a \emph{doubly-efficient mPIR} scheme requiring only $\polylog(N)$ communication and server and client computation. In comparison, all prior mPIR constructions incur at least $\Omega(\sqrt{N})$ cost in all these metrics. Along the way, we construct a novel local decoding procedure for special ``subcode''-locally decodable codes (LDC) which guarantees that _for all_ corruption patterns, the decoding success probability is almost the same for _any_ two indices. Because usual LDC decoders only give guarantees on the decoding probability if the fraction of corruptions is _bounded_, this does not simply follow by parallel repetition. |
BibTeX
@inproceedings{crypto-2025-35675,
title={Malicious Security for PIR (almost) for Free},
publisher={Springer-Verlag},
author={Brett Falk and Pratyush Mishra and Matan Shtepel},
year=2025
}