Concretely Efficient Parallel-Accessible DORAM for 100K-Sized Array
摘要
We propose a concretely efficient parallel-accessible distributed oblivious RAM (DORAM). DORAM is a secure multi-party computation (MPC) protocol that enables private access to secret-shared arrays. Due to its wide application to more complex MPC protocols, many studies have been conducted on concretely efficient DORAMs. The best known concrete performance is about 900 accesses/second for arrays of sizes in the range \(2^{13}\) to \(2^{30}\) , achieved by a DORAM proposed by Falk et al. In this paper, we propose a DORAM that provides concretely efficient parallel access for relatively small-sized arrays. Our DORAM is a three-party MPC protocol that is perfectly secure against a passive and static adversary who can corrupt up to one party. For an N-element array of D-bit elements, our DORAM accesses elements at k distinct addresses with \(O(k\sqrt{N} (\log N + D))\) bits communication in 7 rounds and \(O(kN (\log N + D))\) bits computation. When \(D=61\) and \(N=2^{17}\approx \text {100K}\) , the concrete performance of our DORAM is 452 accesses/second for sequential accesses. Thanks to the round complexity that is independent of the number of parallel access elements, the concrete performance of our protocol improves as k increases, achieving 1,076 accesses/second and 1,521 accesses/second in the cases of \(k=4\) and \(k=16\) , respectively. As a byproduct, our DORAM simultaneously achieves information-theoretic security, constant round complexity, and sublinear communication complexity for the first time.