Parallel Oblivious Array Access for Secure Multiparty Computation and Privacy-Preserving Minimum Spanning Trees
Authors: Peeter Laud (Cybernetica AS)
Volume: 2015
Issue: 2
Pages: 188–205
DOI: https://doi.org/10.1515/popets-2015-0011
Abstract: 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. Our ORAM technique opens up a large class of parallel algorithms for adoption to run on SMC platforms. In this paper, we demonstrate how the minimum spanning tree (MST) finding algorithm by Awerbuch and Shiloach can be executed without revealing any details about the underlying graph (beside its size). The data accesses of this algorithm heavily depend on the location and weight of edges (which are private) and our ORAM technique is instrumental in their execution. Our implementation is the first-ever realization of a privacypreserving MST algorithm with sublinear round complexity.
Keywords: Secure Multiparty Computation; Oblivious Arrays; Minimum Spanning Tree
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
