Welcome to the resource topic for 2023/1897
Title:
PRAC: Round-Efficient 3-Party MPC for Dynamic Data Structures
Authors: Sajin Sasy, Adithya Vadapalli, Ian Goldberg
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 O(\lg^2 n) to O(\lg n) for obliviously searching over n items. We then present an oblivious heap protocol with rounds reduced from O(\lg n) to O(\lg \lg n) for insertions, and bandwidth reduced from O(\lg^2 n) to O(\lg n) for extractions. Finally, we also present the first oblivious AVL tree protocol for MPC where no party learns the data or the structure of the AVL tree, and can support arbitrary insertions and deletions with O(\lg n) rounds and bandwidth. We experimentally evaluate our protocols with realistic network settings for a wide range of memory sizes to demonstrate their efficiency. For instance, we observe our binary search protocol provides >27\times and >3\times improvements in wall-clock time and bandwidth respectively over other approaches for a memory with 2^{26} items; for the same setting our heap’s extract-min protocol achieves >31\times speedup in wall-clock time and >13\times reduction in bandwidth.
ePrint: https://eprint.iacr.org/2023/1897
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .