Ruffle: Rapid 3-Party Shuffle Protocols
Authors: Pranav Shriram A (JP Morgan Chase), Nishat Koti (Indian Institute of Science), Varsha Bhat Kukkala (Indian Institute of Science), Arpita Patra (Indian Institute of Science), Bhavish Raj Gopal (Indian Institute of Science), Somya Sangal (Indian Institute of Science)
Volume: 2023
Issue: 3
Pages: 24–42
DOI: https://doi.org/10.56553/popets-2023-0068
Abstract: Secure shuffle is an important primitive that finds use in several applications such as secure electronic voting, oblivious RAMs, secure sorting, to name a few. For time-sensitive shuffle-based applications that demand a fast response time, it is essential to design a fast and efficient shuffle protocol. In this work, we design secure and fast shuffle protocols relying on the techniques of secure multiparty computation. We make several design choices that aid in achieving highly efficient protocols. Specifically, we consider malicious 3-party computation setting with an honest majority and design robust ring-based protocols. Our shuffle protocols provide a fast online (i.e., input-dependent) phase compared to the state-of-the-art for the considered setting. To showcase the efficiency improvements brought in by our shuffle protocols, we consider two distinct applications of anonymous broadcast and secure graph computation via the GraphSC paradigm. In both cases, multiple shuffle invocations are required. Hence, going beyond standalone shuffle invocation, we identify two distinct scenarios of multiple invocations and provide customised protocols for the same. Further, we showcase that our customized protocols not only provide a fast response time, but also provide improved overall run time for multiple shuffle invocations. With respect to the applications, we not only improve in terms of efficiency, but also work towards providing improved security guarantees, thereby outperforming the respective state-of-the-art works. We benchmark our shuffle protocols and the considered applications to analyze the efficiency improvements with respect to various parameters.
Keywords: secure shuffle, anonymous broadcast, secure graph computation, secure multiparty computation
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
