Parallel Oblivious Array Access for Secure Multiparty Computation and Privacy-Preserving Minimum Spanning Trees

In this paper, 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 privacypreserving applications. For a large class of secure multiparty computation (SMC) protocols, our technique has better practical and asymptotic performance than any previous ORAM technique that has been adapted for use in SMC