### Efficient, Oblivious Data Structures for MPC

Marcel Keller and Peter Scholl

##### Abstract

We present oblivious implementations of several data structures for secure multiparty computation (MPC) such as arrays, dictionaries, and priority queues. The resulting oblivious data structures have only polylogarithmic overhead compared with their classical counterparts. To achieve this, we give secure multiparty protocols for the ORAM of Shi et al. (Asiacrypt 11) and the Path ORAM scheme of van Dijk et al. (CCS 13), and we compare the resulting implementations. We subsequently use our oblivious priority queue for secure computation of Dijkstra's shortest path algorithm on general graphs, where the graph structure is secret. To the best of our knowledge, this is the first implementation of a non-trivial graph algorithm in multiparty computation with polylogarithmic overhead. We implemented and benchmarked all of our protocols using the SPDZ protocol of Damgaard et al. (Crypto 12), which works in the preprocessing model and ensures active security against an adversary corrupting all but one players. For two parties, the access time for an oblivious array of size 1 million is under 250 ms.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Multiparty computationdata structuresoblivious RAMshortest path algorithm
Contact author(s)
m keller @ bristol ac uk
History
2014-08-15: revised
See all versions
Short URL
https://ia.cr/2014/137

CC BY

BibTeX

@misc{cryptoeprint:2014/137,
author = {Marcel Keller and Peter Scholl},
title = {Efficient, Oblivious Data Structures for MPC},
howpublished = {Cryptology ePrint Archive, Paper 2014/137},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/137}},
url = {https://eprint.iacr.org/2014/137}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.