Projects per year
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 Stefanov 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 most of our protocols using the SPDZ protocol of Damgård 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 online access time for an oblivious array of size one million is under 100 ms.
We implemented and benchmarked most of our protocols using the SPDZ protocol of Damgård 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 online access time for an oblivious array of size one million is under 100 ms.
Original language | English |
---|---|
Title of host publication | Advances in Cryptology - ASIACRYPT 2014 |
Subtitle of host publication | 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II |
Publisher | Springer Berlin Heidelberg |
Pages | 506-525 |
Volume | 8874 |
ISBN (Electronic) | 978-3-662-45608-8 |
ISBN (Print) | 978-3-662-45607-1 |
DOIs | |
Publication status | Published - Dec 2014 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Berlin Heidelberg |
ISSN (Print) | 0302-9743 |
Fingerprint
Dive into the research topics of 'Efficient, Oblivious Data Structures for MPC'. Together they form a unique fingerprint.Projects
- 1 Finished