Cryptology ePrint Archive: Report 2014/137
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.
Category / Keywords: cryptographic protocols / Multiparty computation, data structures, oblivious RAM, shortest path algorithm
Date: received 21 Feb 2014, last revised 15 Aug 2014
Contact author: m keller at bristol ac uk
Available format(s): PDF | BibTeX Citation
Version: 20140815:182750 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]