Paper 2014/630

Privacy-Preserving Minimum Spanning Trees through Oblivious Parallel RAM for Secure Multiparty Computation

Peeter Laud


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 privacy-preserving applications. For a large class of secure multiparty computation (SMC) protocols, we believe our technique to have 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 probably the first-ever realization of a privacy-preserving MST algorithm.

Available format(s)
Publication info
Preprint. MINOR revision.
secure multiparty computationoblivious RAMminimum spanning tree
Contact author(s)
peeter laud @ cyber ee
2014-11-25: revised
2014-08-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Peeter Laud},
      title = {Privacy-Preserving Minimum Spanning Trees through Oblivious Parallel {RAM} for Secure Multiparty Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/630},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.