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 \(\varphi \) -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 doubly-efficient mPIR scheme requiring only \(\textrm{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 indexes. 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Malicious Security for PIR (Almost) for Free

  • Brett Falk,
  • Pratyush Mishra,
  • Matan Shtepel

摘要

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 \(\varphi \) -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 doubly-efficient mPIR scheme requiring only \(\textrm{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 indexes. 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.