Welcome to the resource topic for 2023/516
Title:
3-Party Secure Computation for RAMs: Optimal and Concretely Efficient
Authors: Atsunori Ichikawa, Ilan Komargodski, Koki Hamada, Ryo Kikuchi, Dai Ikarashi
Abstract:A distributed oblivious RAM (DORAM) is a method for accessing a secret-shared memory while hiding the accessed locations. DORAMs are the key tool for secure multiparty computation (MPC) for RAM programs that avoids expensive RAM-to-circuit transformations.
We present new and improved 3-party DORAM protocols. For a logical memory of size N and for each logical operation, our DORAM requires O(\log N) local CPU computation steps. This is known to be asymptotically optimal. Our DORAM satisfies passive security in the honest majority setting. Our technique results with concretely-efficient protocols and does not use expensive cryptography (such as re-randomizable or homomorphic encryption). Specifically, our DORAM is 25X faster than the known most efficient DORAM in the same setting.
Lastly, we extend our technique to handle malicious attackers at the expense of using slightly larger blocks (i.e., \omega(\log^2 N) vs. \Omega(\log N)). To the best of our knowledge, this is the first concretely-efficient maliciously secure DORAM.
Technically, our construction relies on a novel concretely-efficient 3-party oblivious permutation protocol. We combine it with efficient non-oblivious hashing techniques (i.e., Cuckoo hashing) to get a distributed oblivious hash table. From this, we build a full-fledged DORAM using a distributed variant of the hierarchical approach of Goldreich and Ostrovsky (J. ACM '96). These ideas, and especially the permutation protocol, are of independent interest.
ePrint: https://eprint.iacr.org/2023/516
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .