Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved. In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires $12 log (5n/4$ ) bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the number $n$ of parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost 36 bits per AND gate in the online phase and 30n + 24 bits per AND gate in the offline phase.Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved. In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires$12 log (5n/4$) bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the number$n$of parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost 36 bits per AND gate in the online phase and 30n + 24 bits per AND gate in the offline phase.

IEEE Computer Security Foundations Workshop (CSFW)Jul 8, 20242 citations

Unconditionally Secure MPC for Boolean Circuits with Constant Communication

Yubo Zeng, Kang Yang, Dengguo Feng +1 more

Lecture notes in computer scienceJan 1, 20260 citations

Big Secrets Small Shares: Revisiting Secure Multi-Party Computation

Wilton Kim, Van Long Phuoc Pham, Stanislav Kruglik +1 more

At CRYPTO 2007, Damgård and Nielsen introduced a preprocessing approach to multi-party computation (MPC) to achieve linear communication complexity. Another approach to reduce communication complexity was proposed by Cramer, Damgård, and de Haan at EUROCRYPT 2007, which involved using ramp-secret sharing schemes to jointly share base-field components of secrets from the extension field. In this paper, we combine these two ideas to achieve a non-asymptotic reduction of communication cost in a multi-phase MPC setup. We introduce a new modification of the ramp secret sharing scheme, called compact sharing, and tailor the MPC protocol to accommodate this modification. Compact sharing masks the polynomial coefficients that would otherwise leak during degree reduction. The protocol provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree. When the extension degree scales linearly with the number of parties, the gate-evaluation core achieves constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.At CRYPTO 2007, Damgård and Nielsen introduced a preprocessing approach to multi-party computation (MPC) to achieve linear communication complexity. Another approach to reduce communication complexity was proposed by Cramer, Damgård, and de Haan at EUROCRYPT 2007, which involved using ramp-secret sharing schemes to jointly share base-field components of secrets from the extension field. In this paper, we combine these two ideas to achieve a non-asymptotic reduction of communication cost in a multi-phase MPC setup. We introduce a new modification of the ramp secret sharing scheme, called compact sharing, and tailor the MPC protocol to accommodate this modification. Compact sharing masks the polynomial coefficients that would otherwise leak during degree reduction. The protocol provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree. When the extension degree scales linearly with the number of parties, the gate-evaluation core achieves constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.

arXiv:2610.27609Oct 20, 20260 citations

hbACSS: How to Robustly Share Many Secrets

Thomas Yurek, Licheng Luo, Jaiden Fairoze +2 more

Despite significant recent progress toward making multi-party computation (MPC) practical, no existing MPC library offers complete robustness-meaning guaranteed output delivery, including in the offline phase-in a network that even has intermittent delays.Importantly, several theoretical MPC constructions already ensure robustness in this setting.We observe that the key reason for this gap between theory and practice is the absence of efficient verifiable/complete secret sharing (VSS/CSS) constructions; existing CSS protocols either require a) challenging broadcast channels in practice or b) introducing computation and communication overhead that is at least quadratic in the number of players.This work presents hbACSS, a suite of optimal-resilience asynchronous complete secret sharing protocols that are (quasi)linear in both computation and communication overhead.Towards developing hbACSS, we develop hbPolyCommit, an efficient polynomial commitment scheme that is (quasi)linear (in the polynomial degree) in terms of computation and communication overhead without requiring a trusted setup.We implement our hbACSS protocols, extensively analyze their practicality, and observe that our protocols scale well with an increasing number of parties.In particular, we use hbACSS to generate MPC input masks: a useful primitive which had previously only been calculated nonrobustly in practice.Recent work shows how to make the online phase of practical asynchronous MPC robust [47].However, the preprocessing phase, which must be run by the servers prior to receiving input, is much harder to make robust in practice.To explain the problem we will focus on generating random input masks, which allow clients to easily contribute secret inputs to an MPC program.The goal is to produce a random secret sharing r t which satisfies the following: if no more than t of the N MPC server nodes are corrupted, r is uniformly random, unknown, and any t + 1 parties can reconstruct the same r.The standard way to generate such values is for all the servers to contribute shares they sample individually, which are then all combined to extract fully random values, even if some corrupt parties chose their inputs in a correlated way [11].This approach hinges on a protocol that can be used to verify that the individually chosen shares are chosen correctly.Verifiable Secret Sharing (VSS) [30], [40], [22] is a natural choice for this task.In particular, Asynchronous Complete Secret Sharing (ACSS) [54] provides all the robustness guarantees needed for the MPC application, since it guarantees not only that the secret inputs can be reconstructed if necessary, but also that each of the servers can receive its original share of the secret.However, existing ACSS protocols introduce a computation and communication overhead that is quadratic in the number of parties and cannot scale well beyond a small number of nodes.This motivates the design of an efficient, scalable ACSS protocol without compromising the optimal replication factor of 3t + 1 or the asynchronous communication setting.In targeting this threat model, we prefix the protocols designed in this paper with "hb" as a reference to the honey badger, a creature known for its resilience in harsh adversarial settings.A. Challenges and overview of our solution a) Good performance under worst case conditions: The asynchronous network setting is fundamentally challenging: unlike in synchrony, a protocol which waits to hear from all parties will stall indefinitely.Instead, we must proceed after hearing from only N -t of the parties, where t is a bound on the number of parties that can fail.Since crashed nodes are indistinguishable from slow nodes, it could be that t parties for which we waited are corrupted, and thus only N -2t correct parties received valid shares.To cope with asynchrony, the most closely related protocol, VSS-R [9], falls back to an inefficient backup mode with communication overhead that is quadratic in the number of servers, even after a brief period of desynchronization.Alternately, Patra et al. give AVSS protocols with linear communication overhead [53], but require weakening resilience (t < N/4).We remark, however, that many t < N/3, AVSS/AVCSS protocols (including ours) could improve their amortized bandwidth by a factor of O(N ) through the use of Packed Secret Sharing.Consequently, we focus on the t < N/3 setting, knowing that improvements here can also lead to improvements in more relaxed settings.b) Aggressive batching for large secrets: Motivated by our application of MPC preprocessing, we seek general efficiency but assume the amount of data that needs to be shared is large.We focus on the case where each single dealer needs to deal a large batch of secrets, such as for precomputation purposes.In doing so, we can amortize awayDespite significant recent progress toward making multi-party computation (MPC) practical, no existing MPC library offers complete robustness-meaning guaranteed output delivery, including in the offline phase-in a network that even has intermittent delays.Importantly, several theoretical MPC constructions already ensure robustness in this setting.We observe that the key reason for this gap between theory and practice is the absence of efficient verifiable/complete secret sharing (VSS/CSS) constructions; existing CSS protocols either require a) challenging broadcast channels in practice or b) introducing computation and communication overhead that is at least quadratic in the number of players.This work presents hbACSS, a suite of optimal-resilience asynchronous complete secret sharing protocols that are (quasi)linear in both computation and communication overhead.Towards developing hbACSS, we develop hbPolyCommit, an efficient polynomial commitment scheme that is (quasi)linear (in the polynomial degree) in terms of computation and communication overhead without requiring a trusted setup.We implement our hbACSS protocols, extensively analyze their practicality, and observe that our protocols scale well with an increasing number of parties.In particular, we use hbACSS to generate MPC input masks: a useful primitive which had previously only been calculated nonrobustly in practice.Recent work shows how to make the online phase of practical asynchronous MPC robust [47].However, the preprocessing phase, which must be run by the servers prior to receiving input, is much harder to make robust in practice.To explain the problem we will focus on generating random input masks, which allow clients to easily contribute secret inputs to an MPC program.The goal is to produce a random secret sharing r t which satisfies the following: if no more than t of the N MPC server nodes are corrupted, r is uniformly random, unknown, and any t + 1 parties can reconstruct the same r.The standard way to generate such values is for all the servers to contribute shares they sample individually, which are then all combined to extract fully random values, even if some corrupt parties chose their inputs in a correlated way [11].This approach hinges on a protocol that can be used to verify that the individually chosen shares are chosen correctly.Verifiable Secret Sharing (VSS) [30], [40], [22] is a natural choice for this task.In particular, Asynchronous Complete Secret Sharing (ACSS) [54] provides all the robustness guarantees needed for the MPC application, since it guarantees not only that the secret inputs can be reconstructed if necessary, but also that each of the servers can receive its original share of the secret.However, existing ACSS protocols introduce a computation and communication overhead that is quadratic in the number of parties and cannot scale well beyond a small number of nodes.This motivates the design of an efficient, scalable ACSS protocol without compromising the optimal replication factor of 3t + 1 or the asynchronous communication setting.In targeting this threat model, we prefix the protocols designed in this paper with "hb" as a reference to the honey badger, a creature known for its resilience in harsh adversarial settings.A. Challenges and overview of our solution a) Good performance under worst case conditions: The asynchronous network setting is fundamentally challenging: unlike in synchrony, a protocol which waits to hear from all parties will stall indefinitely.Instead, we must proceed after hearing from only N -t of the parties, where t is a bound on the number of parties that can fail.Since crashed nodes are indistinguishable from slow nodes, it could be that t parties for which we waited are corrupted, and thus only N -2t correct parties received valid shares.To cope with asynchrony, the most closely related protocol, VSS-R [9], falls back to an inefficient backup mode with communication overhead that is quadratic in the number of servers, even after a brief period of desynchronization.Alternately, Patra et al. give AVSS protocols with linear communication overhead [53], but require weakening resilience (t < N/4).We remark, however, that many t < N/3, AVSS/AVCSS protocols (including ours) could improve their amortized bandwidth by a factor of O(N ) through the use of Packed Secret Sharing.Consequently, we focus on the t < N/3 setting, knowing that improvements here can also lead to improvements in more relaxed settings.b) Aggressive batching for large secrets: Motivated by our application of MPC preprocessing, we seek general efficiency but assume the amount of data that needs to be shared is large.We focus on the case where each single dealer needs to deal a large batch of secrets, such as for precomputation purposes.In doing so, we can amortize away

Network and Distributed System Security SymposiumJan 1, 202235 citations

12 log (5n/4

) bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the number

n

of parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost 36 bits per AND gate in the online phase and 30n + 24 bits per AND gate in the offline phase.