Paper 2023/1897
PRAC: Round-Efficient 3-Party MPC for Dynamic Data Structures
Abstract
We present Private Random Access Computations (PRAC), a 3-party Secure Multi-Party Computation (MPC) framework to support random-access data structure algorithms for MPC with efficient communication in terms of rounds and bandwidth. PRAC extends the state-of-the-art DORAM Duoram with a new implementation, more flexibility in how the DORAM memory is shared, and support for Incremental and Wide DPFs. We then use these DPF extensions to achieve algorithmic improvements in three novel oblivious data structure protocols for MPC. PRAC exploits the observation that a secure protocol for an algorithm can gain efficiency if the protocol explicitly reveals information leaked by the algorithm inherently. We first present an optimized binary search protocol that reduces the bandwidth from
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Proceedings on Privacy Enhancing Technologies 2024(3)
- Keywords
- Oblivious data structuresSecure multi-party computationOblivious RAMsDistributed privacy
- Contact author(s)
-
ssasy @ uwaterloo ca
avadapalli @ cse iitk ac in
iang @ uwaterloo ca - History
- 2024-03-07: revised
- 2023-12-10: received
- See all versions
- Short URL
- https://ia.cr/2023/1897
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1897, author = {Sajin Sasy and Adithya Vadapalli and Ian Goldberg}, title = {{PRAC}: Round-Efficient 3-Party {MPC} for Dynamic Data Structures}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1897}, year = {2023}, url = {https://eprint.iacr.org/2023/1897} }