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

TinyKeys: A New Approach to Efficient Multi-Party Computation

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

Published Jan 1, 2018• 44 citations
Publisher

Abstract

We present a new approach to designing concretely efficient MPC protocols with semi-honest security in the dishonest majority setting. Motivated by the fact that within the dishonest majority setting the efficiency of most practical protocols does not depend on the number of honest parties, we investigate how to construct protocols which improve in efficiency as the number of honest parties increases. Our central idea is to take a protocol which is secure for $$n-1$$ corruptions and modify it to use short symmetric keys, with the aim of basing security on the concatenation of all honest parties’ keys. This results in a more efficient protocol tolerating fewer corruptions, whilst also introducing an LPN-style syndrome decoding assumption. We first apply this technique to a modified version of the semi-honest GMW protocol, using OT extension with short keys, to improve the efficiency of standard GMW with fewer corruptions. We also obtain more efficient constant-round MPC, using BMR-style garbled circuits with short keys, and present an implementation of the online phase of this protocol. Our techniques start to improve upon existing protocols when there are around $$n=20$$ parties with $$h=6$$ honest parties, and as these increase we obtain up to a 13 times reduction (for $$n=400, h=120$$ ) in communication complexity for our GMW variant, compared with the best-known GMW-based protocol modified to use the same threshold.

DOI
10.1007/978-3-319-96878-0_1

Related papers

Fast and Secure Three-party Computation: The Garbled Circuit Approach.

Payman Mohassel, Mike Rosulek, Ye Zhang

Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao’s (semi-honest) 2PC protocol. We demonstrate the practicality of our protocol with an implementation based on the JustGarble framework of Bellare et al. (S&P 2013). The implementation incorporates various optimizations including the most recent techniques for efficient circuit garbling. We perform experiments on several benchmarking circuits, in different setups. Our experiments confirm that, despite providing a more demanding security guarantee, our protocol has performance comparable to existing information-theoretic 3PC. 1

•Jan 1, 2015•16 citations

Fast and Secure Three-party Computation: The Garbled Circuit Approach

Payman Mohassel, Mike Rosulek, Ye Zhang

Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao's (semi-honest) 2PC protocol.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 6, 2015•114 citations

A New Paradigm for Practical Maliciously Secure Multi-Party Computation

Xiao Wang

Secure Multi-Party Computation (MPC) protocols allow a group of mutually distrusting users to compute a function jointly on their inputs without revealing any information beyond the output. For many years, implementations of MPC protocols have targeted security against semi-honest adversaries, i.e., attackers are assumed to execute the protocol honestly but try to learn private information after the fact. Protocols secure against stronger and more realistic malicious adversaries, who could behave arbitrarily during the protocol execution, were known to exist but were much less efficient. This thesis introduces a new paradigm to construct extremely efficient MPC protocols with malicious security. In particular, this thesis consists of three major contributions. 1. We introduce the authenticated garbling framework, and present an efficient concrete instantiation of the protocol. The resulting protocol partially closes the gap between semi-honest and malicious MPC protocols asymptotically; the implementation of the protocol represents the state-of-the-art system for malicious two-party computation. 2. We discuss how to apply authenticated garbling to the multi-party setting, where all-but-one parties can be corrupted by the adversary. The resulting protocol improves upon the best previous constant-round protocol by orders of magnitude. We also present a system that, for the first time, enables MPC executions among hundreds of parties, distributed globally. 3. We present a series of optimizations to two-party authenticated garbling by interpreting authenticated garbling in a new way. The improved malicious protocol has essentially the same concrete efficiency as the best semi-honest protocol in the preprocessing model. 4. We develop these protocols in EMP-toolkit, a practical and efficient MPC tool that can be used to build new protocols and to develop applications using our existing protocols.

•Jan 1, 2018•2 citations

More Efficient MPC from Improved Triple Generation and Authenticated Garbling

Kang Yang, Xiao Shaun Wang, Jiang Zhang

Recent works on distributed garbling have provided highly efficient solutions for constant-round MPC tolerating an arbitrary number of corruptions. In this work, we improve upon state-of-the-art protocols in this paradigm for further performance gain. First, we propose a new protocol for generating authenticated AND triples, which is a key building block in many recent works. \beginitemize \item We propose a new authenticated bit protocol in the two-party and multi-party settings from bare IKNP OT extension, allowing us to reduce the communication by about $24%$ and eliminate many computation bottlenecks. We further improve the computational efficiency for multi-party authenticated AND triples with cheaper and fewer consistency checks and fewer hash function calls. \item We implemented our triple generation protocol and observe around $4\times$ to $5\times$ improvement compared to the best prior protocol in most settings. For example, in the two-party setting with 10 Gbps network and 8 threads, our protocol can generate more than $4$ million authenticated triples per second, while the best prior implementation can only generate $0.8$ million triples per second. In the multi-party setting, our protocol can generate more than $37000$ triples per second over 80 parties, while the best prior protocol can only generate the same number of triples per second over 16 parties. \enditemize We also improve the state-of-the-art multi-party authenticated garbling protocol. \beginitemize \item We take the first step towards applying half-gates in the multi-party setting, which enables us to reduce the size of garbled tables by $2κ$ bits per gate per garbler, where κ is the computational security parameter. This optimization is also applicable in the semi-honest multi-party setting. \item We further reduce the communication of circuit authentication from $4ρ$ bits to $1$ bit per gate, using a new multi-party batched circuit authentication, where ρ is the statistical security parameter. Prior solution with similar efficiency is only applicable in the two-party setting. \enditemize For example, in the three-party setting, our techniques can lead to roughly a $35%$ reduction in the size of a distributed garbled circuit.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 30, 2020•55 citations

Scalable Mixed-Mode MPC

Radhika Garg, Kang Yang, Jonathan Katz +1 more

Protocols for secure multi-party computation (MPC) supporting mixed-mode computation have found a lot of applications in recent years due to their flexibility in representing the function to be evaluated. However, existing mixed-mode MPC protocols are only practical for a small number of parties: they are either tailored to the case of two/three parties, or scale poorly for a large number of parties.In this paper, we design and implement a new system for highly efficient and scalable mixed-mode MPC tolerating an arbitrary number of semi-honest corruptions. Our protocols allow secret data to be represented in Encrypted, Boolean, Arithmetic, or Yao form, and support efficient conversions between these representations.1)We design a multi-party table-lookup protocol, where both the index and the table can be kept private. The protocol is scalable even with hundreds of parties.2)Using the above protocol, we design efficient conversions between additive arithmetic secret sharings and Boolean secret sharings for a large number of parties. For 32 parties, our conversion protocols require 1184× to 8141× less communication compared to the state-of-the-art protocols MOTION and MP-SPDZ; this leads to up to 1275× improvement in running time under 1 Gbps network. The improvements are even larger with more parties.3)We also use new protocols to design an efficient multi-party distributed garbling protocol. The protocol could achieve asymptotically constant communication per party.Our implementation will be made public.

IEEE Symposium on Security and Privacy (S&P)•May 19, 2024•15 citations

Towards Secure Multi-Party Computation on the Internet

Eduardo Soria-Vázquez

ulti-Party Computation (MPC) protocols allow a set of mutually distrustful parties to securely compute on their joint private inputs, maintaining the privacy of those.Since its early conception in the eighties, a plethora of research as well as some real world deployments have taken place, demonstrating the relevance of such an interesting mathematical problem.Nevertheless, most of the research and all deployments have focused on scenarios where both the number of parties and network latency are very low.This thesis lays out the first steps towards practical deployments of large-scale MPC, where many parties may be involved and they might only be connected through a high-latency network such as the Internet.Both theoretical and empirical evidence shows that non-constant-round protocols cannot perform well on slow networks for many functions.In order to overcome this issue, all the works in this thesis include concretely efficient constant-round protocols based on multi-party garbled circuits.Chapter 3 and Chapter 4 deal with the very strong setting where an active adversary corrupts all but one parties.The former achieves such goal by using homomorphic encryption for low-depth circuits.The latter, based on subsequent work, improves the theoretical understanding of the problem and utilises oblivious transfer to improve efficiency.In Chapter 5 we provide both constant and non-constant round protocols that can handle large numbers of parties more efficiently.We leverage our performance improvements by relaxing the setting where all but one parties are corrupted to one where a small minority of honest participants can be assumed.Concretely, such change allows to distribute secret key material so that each party only holds a 'short' part of the key.Security is then based on the concatenation of all honest parties' keys rather than on each party's individual key, improving both the communication and computation complexities.iii researcher.They would have not been the same without the support of family, friends and colleagues.I would like to start by thanking Nigel Smart for giving me this opportunity, being my advisor and introducing me to others in the community.Martijn Stam

•Feb 1, 2019•0 citations
We present a new approach to designing concretely efficient MPC protocols with semi-honest security in the dishonest majority setting. Motivated by the fact that within the dishonest majority setting the efficiency of most practical protocols does not depend on the number of honest parties, we investigate how to construct protocols which improve in efficiency as the number of honest parties increases. Our central idea is to take a protocol which is secure for n−1n-1n−1 corruptions and modify it to use short symmetric keys, with the aim of basing security on the concatenation of all honest parties’ keys. This results in a more efficient protocol tolerating fewer corruptions, whilst also introducing an LPN-style syndrome decoding assumption. We first apply this technique to a modified version of the semi-honest GMW protocol, using OT extension with short keys, to improve the efficiency of standard GMW with fewer corruptions. We also obtain more efficient constant-round MPC, using BMR-style garbled circuits with short keys, and present an implementation of the online phase of this protocol. Our techniques start to improve upon existing protocols when there are around n=20n=20n=20 parties with h=6h=6h=6 honest parties, and as these increase we obtain up to a 13 times reduction (for n=400,h=120n=400, h=120n=400,h=120 ) in communication complexity for our GMW variant, compared with the best-known GMW-based protocol modified to use the same threshold.
Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao’s (semi-honest) 2PC protocol. We demonstrate the practicality of our protocol with an implementation based on the JustGarble framework of Bellare et al. (S&P 2013). The implementation incorporates various optimizations including the most recent techniques for efficient circuit garbling. We perform experiments on several benchmarking circuits, in different setups. Our experiments confirm that, despite providing a more demanding security guarantee, our protocol has performance comparable to existing information-theoretic 3PC. 1
Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao's (semi-honest) 2PC protocol.
Secure Multi-Party Computation (MPC) protocols allow a group of mutually distrusting users to compute a function jointly on their inputs without revealing any information beyond the output. For many years, implementations of MPC protocols have targeted security against semi-honest adversaries, i.e., attackers are assumed to execute the protocol honestly but try to learn private information after the fact. Protocols secure against stronger and more realistic malicious adversaries, who could behave arbitrarily during the protocol execution, were known to exist but were much less efficient. This thesis introduces a new paradigm to construct extremely efficient MPC protocols with malicious security. In particular, this thesis consists of three major contributions. 1. We introduce the authenticated garbling framework, and present an efficient concrete instantiation of the protocol. The resulting protocol partially closes the gap between semi-honest and malicious MPC protocols asymptotically; the implementation of the protocol represents the state-of-the-art system for malicious two-party computation. 2. We discuss how to apply authenticated garbling to the multi-party setting, where all-but-one parties can be corrupted by the adversary. The resulting protocol improves upon the best previous constant-round protocol by orders of magnitude. We also present a system that, for the first time, enables MPC executions among hundreds of parties, distributed globally. 3. We present a series of optimizations to two-party authenticated garbling by interpreting authenticated garbling in a new way. The improved malicious protocol has essentially the same concrete efficiency as the best semi-honest protocol in the preprocessing model. 4. We develop these protocols in EMP-toolkit, a practical and efficient MPC tool that can be used to build new protocols and to develop applications using our existing protocols.
Recent works on distributed garbling have provided highly efficient solutions for constant-round MPC tolerating an arbitrary number of corruptions. In this work, we improve upon state-of-the-art protocols in this paradigm for further performance gain. First, we propose a new protocol for generating authenticated AND triples, which is a key building block in many recent works. \beginitemize \item We propose a new authenticated bit protocol in the two-party and multi-party settings from bare IKNP OT extension, allowing us to reduce the communication by about 2424%24 and eliminate many computation bottlenecks. We further improve the computational efficiency for multi-party authenticated AND triples with cheaper and fewer consistency checks and fewer hash function calls. \item We implemented our triple generation protocol and observe around 4×4\times4× to 5×5\times5× improvement compared to the best prior protocol in most settings. For example, in the two-party setting with 10 Gbps network and 8 threads, our protocol can generate more than 444 million authenticated triples per second, while the best prior implementation can only generate 0.80.80.8 million triples per second. In the multi-party setting, our protocol can generate more than 370003700037000 triples per second over 80 parties, while the best prior protocol can only generate the same number of triples per second over 16 parties. \enditemize We also improve the state-of-the-art multi-party authenticated garbling protocol. \beginitemize \item We take the first step towards applying half-gates in the multi-party setting, which enables us to reduce the size of garbled tables by 2κ2κ2κ bits per gate per garbler, where κ is the computational security parameter. This optimization is also applicable in the semi-honest multi-party setting. \item We further reduce the communication of circuit authentication from 4ρ4ρ4ρ bits to 111 bit per gate, using a new multi-party batched circuit authentication, where ρ is the statistical security parameter. Prior solution with similar efficiency is only applicable in the two-party setting. \enditemize For example, in the three-party setting, our techniques can lead to roughly a 3535%35 reduction in the size of a distributed garbled circuit.
Protocols for secure multi-party computation (MPC) supporting mixed-mode computation have found a lot of applications in recent years due to their flexibility in representing the function to be evaluated. However, existing mixed-mode MPC protocols are only practical for a small number of parties: they are either tailored to the case of two/three parties, or scale poorly for a large number of parties.In this paper, we design and implement a new system for highly efficient and scalable mixed-mode MPC tolerating an arbitrary number of semi-honest corruptions. Our protocols allow secret data to be represented in Encrypted, Boolean, Arithmetic, or Yao form, and support efficient conversions between these representations.1)We design a multi-party table-lookup protocol, where both the index and the table can be kept private. The protocol is scalable even with hundreds of parties.2)Using the above protocol, we design efficient conversions between additive arithmetic secret sharings and Boolean secret sharings for a large number of parties. For 32 parties, our conversion protocols require 1184× to 8141× less communication compared to the state-of-the-art protocols MOTION and MP-SPDZ; this leads to up to 1275× improvement in running time under 1 Gbps network. The improvements are even larger with more parties.3)We also use new protocols to design an efficient multi-party distributed garbling protocol. The protocol could achieve asymptotically constant communication per party.Our implementation will be made public.
ulti-Party Computation (MPC) protocols allow a set of mutually distrustful parties to securely compute on their joint private inputs, maintaining the privacy of those.Since its early conception in the eighties, a plethora of research as well as some real world deployments have taken place, demonstrating the relevance of such an interesting mathematical problem.Nevertheless, most of the research and all deployments have focused on scenarios where both the number of parties and network latency are very low.This thesis lays out the first steps towards practical deployments of large-scale MPC, where many parties may be involved and they might only be connected through a high-latency network such as the Internet.Both theoretical and empirical evidence shows that non-constant-round protocols cannot perform well on slow networks for many functions.In order to overcome this issue, all the works in this thesis include concretely efficient constant-round protocols based on multi-party garbled circuits.Chapter 3 and Chapter 4 deal with the very strong setting where an active adversary corrupts all but one parties.The former achieves such goal by using homomorphic encryption for low-depth circuits.The latter, based on subsequent work, improves the theoretical understanding of the problem and utilises oblivious transfer to improve efficiency.In Chapter 5 we provide both constant and non-constant round protocols that can handle large numbers of parties more efficiently.We leverage our performance improvements by relaxing the setting where all but one parties are corrupted to one where a small minority of honest participants can be assumed.Concretely, such change allows to distribute secret key material so that each party only holds a 'short' part of the key.Security is then based on the concatenation of all honest parties' keys rather than on each party's individual key, improving both the communication and computation complexities.iii researcher.They would have not been the same without the support of family, friends and colleagues.I would like to start by thanking Nigel Smart for giving me this opportunity, being my advisor and introducing me to others in the community.Martijn Stam