Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Efficient, Oblivious Data Structures for MPC

Marcel Keller, Peter Schöll

Published Jan 1, 2014• 137 citations
Publisher
DOI
10.1007/978-3-662-45608-8_27

Related papers

Zero-Knowledge Systems from MPC-in-the-Head and Oblivious Transfer

Cyprien Delpech de Saint Guilhem, Ehsan Ebrahimi, Barry Van Leeuwen

Lecture notes in computer science•Dec 4, 2023•0 citations

Round-Optimal Oblivious Transfer and MPC from Computational CSIDH

Saikrishna Badrinarayanan, Daniel Masny, Pratyay Mukherjee +3 more

Lecture notes in computer science•Jan 1, 2023•12 citations

Communication-Efficient MPC for General Adversary Structures

Joshua Lampkins, Rafail Ostrovsky

Lecture notes in computer science•Jan 1, 2014•4 citations

Low Cost Constant Round MPC Combining BMR and Oblivious Transfer

Carmit Hazay, Peter Schöll, Eduardo Soria-Vázquez

Lecture notes in computer science•Jan 1, 2017•82 citations

Concretely Efficient MPC Protocols for Real-world Applications

Nan Cheng

•May 11, 2026•0 citations

Efficient, Oblivious Data Structures for MPC.

Marcel Keller, Peter Schöll

Abstract. We present oblivious implementations of several data structures for secure multiparty com-putation (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 all of our protocols using the SPDZ protocol of Damg̊ard 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 1 million is under 250 ms.

•Jan 1, 2014•0 citations
Abstract. We present oblivious implementations of several data structures for secure multiparty com-putation (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 all of our protocols using the SPDZ protocol of Damg̊ard 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 1 million is under 250 ms.