Paper 2014/630

Efficient Oblivious Parallel Array Reads and Writes for Secure Multiparty Computation

Peeter Laud

Abstract

In this note we describe efficient protocols to perform in parallel many reads and writes in private arrays according to private indices. The protocol is implemented on top of the Arithmetic Black Box (ABB) and can be freely composed to build larger privacy-preserving applications. For a large class of secure multiparty computation (SMC) protocols, we believe our technique to have better practical performance than any previous ORAM technique that has been adapted for use in SMC. We also argue that for a significant class of SMC protocols, our technique has better asymptotic performance than previous approaches.