Research Scientist at JP Morgan AlgoCRYPT (US)
17th January 2024, 4:00pm - 5:00pm (GST)
|TurboPack: honest majority MPC with O(|C|) online communication
We present Turbopack (CCS 2022), a novel approach to honest majority secure multiparty computation in the preprocessing model with information theoretic security that achieves the best online communication complexity. The online phase of our protocol requires 12 elements in total per multiplication gate with circuit-dependent preprocessing, or 20 elements in total with circuit-independent preprocessing. Prior works achieved linear online communication complexity in n, the number of parties, with the best prior existing solution involving 1.5n elements per multiplication gate. Only one recent work (Goyal et al, CRYPTO’22) achieves constant online communication complexity, but the constants are large (108 elements for passive security, and twice that for active security). That said, our protocol offers a very efficient information theoretic online phase for any number of parties.
The total end-to-end communication cost with the preprocessing phase is linear in n, i.e., 10n + 44, which is larger than the 4n complexity of the state-of-the-art protocols. The gap is not significant when the online phase must be optimized as a priority and a reasonably large number of parties is involved. Unlike previous works based on packed secret-sharing to reduce communication complexity, we further reduce the communication by avoiding the use of complex and expensive network routing or permutations tools. Furthermore, we also allow for a maximal honest majority adversary, while most previous works require the set of honest parties to be strictly larger than a majority.
Our protocol is simple and offers concrete efficiency. To illustrate this we present a full-fledged open-source implementation together with experimental results that show improvements in online phase runtimes that go up to 5X in certain settings (e.g. 45 parties, LAN network, circuit of depth 10 with 1M gates).
Finally, we also hint at Superpack (Eurocrypt 2023), which is a computationally secure protocol suitable for the setting where t<n*(1-eps), for any constant 0<eps<1. Superpack also achieves an online phase with O(|C|) communication. Note that, if 1/2<=eps<1, then there is an honest majority and Turbopack, which is information-theoretic secure and more lightweight, can be used. However, Superpack shines in the case in the dishonest majority case where 0<eps<1/2: prior dishonest majority works operate with only one honest party, and minor a few exceptions, no benefits are obtained by having more than one honest party; Superpack exploits the presence of a constant fraction of honest parties to enable O(|C|) communication in the online phase. We provide an open-source implementation and discuss concrete improvements through our extensive experiments.
|Daniel Escudero is a Research Scientist at JP Morgan AlgoCRYPT Center of Excellence. Prior to this, starting on May 2017 until August 2021, he was a PhD student at the Cryptography and Security group at Aarhus University, Denmark, working under the supervision of Ivan Damgård, Jesper Buus Nielsen and Peter Scholl. He obtained his Bachelor's degree in Mathematics from Universidad Nacional de Colombia in 2016 where he had the valuable opportunity to work in a research project on Multivariate Public Key Cryptography during the last two years of his studies. His research focuses on cryptographic techniques that allows us to perform computation on private data. This includes topics like secure multiparty computation (MPC), homomorphic encryption, and zero-knowledge proofs (ZKP). His interests cover both theory and practice, ranging from interesting connections between algebra and cryptography (like the study of MPC or ZKP over more general rings than finite fields), to actual implementations and even deployments in real use-cases.