International Association
for Cryptologic Research

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.

Distributed Oblivious Random Access Memory (DORAM) is a secure multiparty protocol that allows a group of participants holding a secret-shared array to read and write to secret-shared locations within the array. The efficiency of a DORAM protocol is measured by the amount of communication and computation required per read/write query into the array. DORAM protocols are a necessary ingredient for executing Secure Multiparty Computation (MPC) in the RAM model. Although DORAM has been widely studied, all existing DORAM protocols have focused on the setting where the DORAM servers are semi-honest. Generic techniques for upgrading a semi-honest DORAM protocol to the malicious model typically increase the asymptotic communication complexity of the DORAM scheme. In this work, we present a 3-party DORAM protocol which requires $O((\kappa + D)\log N)$ communication and computation per query, for a database of size $N$ with $D$-bit values, where $\kappa$ is the security parameter. Our hidden constants in the big-O nation are small. We show that our protocol is UC-secure in the presence of a malicious, static adversary. This matches the communication and computation complexity of the best semi-honest DORAM protocols, and is the first malicious DORAM protocol with this complexity.