Round-Efficient Byzantine Agreement and Multi-party Computation with Asynchronous Fallback

Abstract

Protocols for Byzantine agreement (BA) and secure multi-party computation (MPC) can be classified according to the underlying communication model. The two most commonly considered models are the synchronous one and the asynchronous one. Synchronous protocols typically lose their security guarantees as soon as the network violates the synchrony assumptions. Asynchronous protocols remain secure regardless of the network conditions, but achieve weaker security guarantees even when the network is synchronous.

Recent works by Blum, Katz and Loss [TCC’19], and Blum, Liu-Zhang and Loss [CRYPTO’20] introduced BA and MPC protocols achieving security guarantees in both settings: security up to $t_s$ corruptions in a synchronous network, and up to $t_a$ corruptions in an asynchronous network, under the provably optimal threshold trade-offs $t_a \le t_s$ and $t_a + 2t_s < n$. However, current solutions incur a high synchronous round complexity when compared to state-of-the-art purely synchronous protocols. When the network is synchronous, the round complexity of BA protocols is linear in the number of parties, and the round complexity of MPC protocols also depends linearly on the depth of the circuit to evaluate.

In this work, we provide round-efficient constructions for both primitives with optimal resilience: fixed-round and expected constant-round BA protocols, and an MPC protocol whose round complexity is independent of the circuit depth.

C.-D. Liu-Zhang—This work was partially carried out while the author was at ETH Zürich.

1 Introduction

1.1 Motivation

Byzantine agreement (BA) and secure multi-party computation (MPC) are two fundamental and widely explored problems in distributed computing and cryptography.

The general problem of MPC allows a set of n parties to correctly carry out an arbitrary computation, without revealing anything about their inputs that could not be inferred from the computed output [45, 46]. Such guarantees must hold even when a subset of the parties are corrupted and actively deviate from the protocol specification. BA can be seen as an instance of MPC, in which the function to evaluate guarantees agreement on a common output [42, 44] and privacy is not a requirement. Protocols for BA are often used as building blocks within larger constructions, including crucially in MPC protocols, and have received renewed attention in the context of blockchain protocols (starting with [38]).

There are two prominent communication models in the literature when it comes to the design of such primitives. In the synchronous model, parties have synchronized clocks and messages are assumed to be delivered within some (publicly known) delay $\varDelta$. Protocols in this setting achieve very strong security guarantees: under standard setup assumptions, BA [23, 31] and MPC [4, 5, 7, 15, 18, 19, 21, 26, 27, 29, 43] are achievable even when up to $t<n/2$ parties are corrupted. However, the security of synchronous protocols is often completely compromised as soon as the synchrony assumptions are violated (for example, if even one message is delayed by more than $\varDelta$ due to unpredictable network delays). This is particularly undesirable in real-world applications, where even the most stable networks, such as the Internet, occasionally experience congestion or failures. In the asynchronous model, no timing assumptions are needed, and messages can be arbitrarily delayed. Protocols designed in this model are robust even in unpredictable real-world networks, but the security guarantees that can be achieved are significantly weaker. For example, protocols in this realm can only tolerate up to $t < n/3$ corruptions [8, 14, 25].

As a consequence, when deploying protocols in real-world scenarios, one has to decide between employing synchronous protocols—risking catastrophic failures in the case of unforeseen network delays—or settling for the weaker security guarantees of asynchronous protocols.

1.2 Contributions

A recent line of work [9, 11] provides BA and MPC protocols that are secure up to $t_s < n/2$ corruptions when the network is synchronous, and $t_a\le t_s$ corruptions when the network is asynchronous, for the optimal trade-off $t_a + 2t_s < n$.

Such protocols strive to achieve the best of both models, but current solutions are far from being efficient, especially when it comes to running time; in this paper, we focus on minimizing round complexity when the network is synchronous. This is of primary importance in typical scenarios, where the network is stable and synchronous most of the time, but may suffer from unexpected congestion.

Current BA and MPC protocols in this realm [9, 11] require a linear number of rounds in the number of parties. Moreover, known MPC protocols [11] also have linear round complexity in the depth of the circuit to evaluate.

This is in contrast to the efficiency of state-of-the-art purely synchronous protocols: fixed-round BA protocols (Monte-Carlo type) require only $O(\kappa )$ rounds, and BA protocols with probabilistic termination (Las-Vegas type) require an expected constant number of rounds. Furthermore, current MPC protocols only require a constant number of broadcast rounds.¹ We therefore ask the following natural question.

We answer this question affirmatively by providing the following results.

Round-Efficient Synchronous BA with Asynchronous Fallback. We obtain the first BA protocols in this realm that are round efficient when the network is synchronous and with the optimal trade-off $t_a+2t_s < n$, by providing fixed-round and expected constant-round constructions. In doing so, we completely characterize the feasibility of a primitive that we believe to be of independent interest: a round-efficient BA that is secure in a synchronous network for up to $t_s$-corruptions, and retains some weak validity guarantee even in an asynchronous network up to $t_a$-corruptions. We show that its optimal tradeoff is $2t_a + t_s < n$ and $t_s < n/2$. As a side result, we also provide a simpler construction of the primitive for the trade-off $t_a+2t_s < n$. We then use this primitive as a fundamental building block to design further round-efficient primitives: broadcast protocols with similar guarantees, and also synchronous BA/MPC protocols with asynchronous fallback.

Round-Efficient Synchronous MPC with Asynchronous Fallback. We obtain the first synchronous MPC protocol with asynchronous fallback with optimal guarantees (i.e. $t_a + 2t_s < n$ and $(n-t_s)$-output quality as in [11]) that requires a constant number of all-to-all broadcast/BA invocations. In particular, the round complexity is independent of the depth of the circuit. When instantiating the broadcast/BA protocols with our constructions (in their fixed-round version), we achieve a total round complexity of $O(\kappa )$.² For this, we adapt techniques based on garbled circuits [5, 20, 46] to our setting.

1.3 Related Work

Protocols achieving security guarantees in both synchronous and asynchronous networks have only begun to be studied in relatively recent works. Closest to ours are works by Blum et al. [9, 11], which consider the problem of BA and MPC achieving security guarantees in both communication models. Our work improves upon the round efficiency of these protocols. In the same setting, the work in [10] considers the problem of state-machine replication (SMR).

The work in [28] introduces a variant of the purely synchronous model, which allows for network partitions, motivated by eclipse attacks. In this model, the adversary is allowed to disconnect a certain fraction of parties from the rest of the network in each round. BA and MPC protocols tolerating the optimal corruption threshold in this model are also provided. In [2], similar results are achieved for SMR. These results are crucially different from ours, as they rely on the fact that synchrony is maintained in part of the network. In contrast, our protocols give guarantees even if the network is fully asynchronous.

Other works that provide hybrid security guarantees include BA achieving guarantees in synchronous or partially synchronous networks [37], or guarantees against active corruptions in a synchronous network and fail-stop in an asynchronous network [34].

A different line of work [35, 36, 39, 40] has recently investigated protocols that achieve responsiveness. These protocols operate under a synchronous network, and provide the additional guarantee that parties obtain output as fast as the network delay allows. Note that these works do not provide any security guarantees when the network is not synchronous.

2 Model

We consider a set of n parties $\mathcal {P} = \{P_1, \dots , P_n\}$. We denote by $\kappa$ the security parameter.

2.1 Communication and Adversarial Models

We consider a complete network of authenticated channels. Our protocols strive to be secure in the two main communication models in the literature: the synchronous and the asynchronous models.

In the synchronous model, parties have access to synchronized clocks, and all messages are delivered within a known delay $0 \le \varDelta \in \mathbb {R}$. In this setting, protocols can be conveniently described as proceeding in rounds: parties begin the protocol simultaneously, and the r-th round identifies the time interval $[(r-1)\varDelta , r\varDelta )$ for all integers $r \ge 1$. If a party receives a message within this time interval, we say they receive a message in round r. When a party sends a message in round r, it means they send it at time $(r-1)\varDelta$. Within each round, the adversary can schedule the delivery of messages arbitrarily. In particular, we consider a rushing adversary that generates the messages of corrupted parties after seeing all messages sent by honest parties.

In the asynchronous model, parties do not have access to synchronized clocks, and the adversary can schedule the delivery of messages arbitrarily. However, the adversary cannot drop messages, meaning that all messages are eventually delivered.

We consider a static adversary that can corrupt parties in an arbitrary manner at the beginning of the protocol.³

2.2 Cryptographic Primitives

Public-Key Infrastructure. We assume that parties have access to a public-key infrastructure. This means parties agree on a set of public keys $(\texttt {pk}_1, \dots , \texttt {pk}_n)$ and party $P_i$ holds the secret key $\texttt {sk}_i$ associated with $\texttt {pk}_i$.

Definition 1

A (digital) signature scheme is a triple $({\mathsf {Sgn}},{\mathsf {Vfy}},{\mathsf {Kgn}})$ of algorithms such that:

• given the security parameter $\kappa$, the key generation algorithm ${\mathsf {Kgn}}$ outputs a public/secret key pair $({\mathtt {pk}}, {\mathtt {sk}}) \in \mathcal {PK}\times \mathcal {SK}$;

• given a secret key ${\mathtt {sk}} \in \mathcal {SK}$ and a message $m \in \{0,1\}^*$, the signing algorithm ${\mathsf {Sgn}}$ outputs $\mathcal {S} \ni \sigma := {\mathsf {Sgn}}(m, {\mathtt {sk}})$;

• given a message $m \in \{0,1\}^*$, a public key ${\mathtt {pk}} \in \mathcal {PK}$, and a signature $\sigma \in \mathcal {S}$, the verifying algorithm ${\mathsf {Vfy}}$ outputs ${\mathsf {Vfy}}(m, \sigma , {\mathtt {pk}}) \in \{0,1\}$;

• ${\mathsf {Vfy}}(m, \sigma , {\mathtt {pk}}) =1$ if and only if $\sigma = {\mathsf {Sgn}}(m, {\mathtt {sk}})$ where $({\mathtt {pk}}, {\mathtt {sk}})$ is a key pair output by ${\mathsf {Kgn}}$.

We require the signature scheme to be unforgeable against chosen message attacks.

Coin-Flip. Parties have access to a $\mathsf {Coin}$-$\mathsf {Flip}$ functionality, parametrized by t, that allow mutually distrustful parties to generate a common uniformly random bit.

Such a functionality can be realized in the asynchronous model (e.g. [1, 14, 41]) under general assumptions up to $t<n/3$ corruptions, or even 1-round using unique threshold signatures in the random oracle model (e.g. [12]) up to $t<n/2$ corruptions.

3 Definitions

The definitions we give are somewhat non-standard, out of necessity to allow for different abort behaviors depending on the network condition (synchronous/asynchronous), which is unknown to the parties at the start of the protocol. If an honest party outputs symbol $\top$, this means they detected (during the execution) that the network is asynchronous. Whenever desirable, our definitions are equivalent to the standard notions.

3.1 Agreement Primitives

Byzantine agreement (BA) allows a set of parties (each holding an input) to agree on a common value, even when a subset of parties has arbitrary behavior.

Definition 2

(Byzantine agreement). Let $\varPi$ be a protocol executed by parties $P_1, \dots , P_n$ where each party $P_j$ holds input $v_j \in \{0,1\}$ and terminates upon generating an output $f_j \in \{0, 1, \top \}$. We say protocol $\varPi$ achieves

• (t-validity) if whenever up to t parties are corrupted: if there is v such that each honest party holds input $v_j = v$, then every honest party outputs $f_j = v$.

• (t-weak validity) if whenever up to t parties are corrupted: if there is v such that each honest party holds input $v_j = v$, then every honest party outputs $f_j \in \{v, \top \}$.

• (t-consistency) if whenever up to t parties are corrupted: there is $v \in \{0,1, \top \}$ such that each honest party outputs $f_j = v$.

• (t-liveness) if whenever up to t parties are corrupted: no honest party outputs $f_j = \top$.

Together, the t-consistency and t-liveness properties imply the more widely adopted consistency notion. If a protocol $\varPi$ achieves t-validity, t-consistency, and t-liveness, we say it achieves t-security (or that it is t-secure).

Weak consensus (WC) is a primitive that achieves a weaker form of agreement compared to BA: it guarantees agreement among all the parties that output a bit, but parties are allowed to output a special symbol $\bot$.

Definition 3

(Weak consensus). Let $\varPi$ be a protocol executed by $P_1, \dots , P_n$ where each party $P_j$ holds input $v_j \in \{0,1\}$ and terminates upon generating an output $f_j \in \{0, 1, \bot , \top \}$. We say protocol $\varPi$ achieves

• (t-validity) if whenever up to t parties are corrupted: if there is v such that each honest party holds input $v_j = v$, then each honest party outputs $f_j = v$.

• (t-weak validity) if whenever up to t parties are corrupted: if there is v such that each honest party holds input $v_j = v$, then all honest parties output $f_j \in \{v, \top \}$.

• (t-weak consistency) if whenever up to t parties are corrupted: if an honest party outputs $f_j = v \in \{0,1\}$, no honest party outputs $f_j = 1-v$.

• (t-liveness) if whenever up to t parties are corrupted: no honest party outputs $f_j = \top$.

3.2 Broadcast Primitives

Broadcast (BC, sometimes called Byzantine broadcast) allows a designated party, called the sender, to consistently send a message to multiple parties in the presence of active adversarial behavior.

Definition 4

(Broadcast). Let $\varPi$ be a protocol executed by parties $P_1, \dots , P_n$ where a designated party $P^*$ holds input $v^* \in \{0, 1\}$ and each party $P_j$ terminates upon generating an output $f_j \in \{0, 1, \top \}$. We say protocol $\varPi$ achieves

• (t-validity) if whenever up to t parties are corrupted: if the sender $P^*$ is honest, then each honest party outputs $f_j = v^*$.

• (t-weak-validity) if whenever up to t parties are corrupted: if the sender $P^*$ is honest, then each honest party outputs $f_j \in \{v^*, \top \}$.

• (t-consistency) if whenever up to t parties are corrupted: there is $v \in \{0,1,\top \}$ such that each honest party outputs $f_j = v$.

Gradecast (GBC) is a primitive that is similar to broadcast, but achieves a weaker form of consistency guarantees.

Definition 5

(Gradecast). Let $\varPi$ be a protocol executed by parties $P_1, \dots , P_n$ where a designated sender $P^*$ holds input $v^* \in \{0,1\}$ and each party $P_j$ terminates upon generating an output value and a grade $(f_j, g_j) \in \{0, 1, \bot \} \times \{0, 1, 2\}$. We say protocol $\varPi$ achieves

• (t-graded validity) if whenever up to t parties are corrupted: if $P^*$ is honest, then all honest parties output $(v^*, 2)$.

• (t-graded consistency) if whenever up to t parties are corrupted:

  • a. there is a $v \in \{0, 1\}$ such that all honest parties output either (v, 2), (v, 1) or $(\bot , 0)$.

  • b. if some honest party outputs (v, 2) for any $v \in \{0, 1\}$, no honest party outputs $(\bot , 0)$.

• (t-weak-graded validity) if whenever up to t parties are corrupted in an execution of $\varPi$: if $P^*$ is honest, then each honest party outputs either $(v^*, 2)$, $(v^*, 1)$ or $(\bot , 0)$.

3.3 Multi-party Computation

A protocol for multi-party computation (MPC) allows a set of n mutually distrustful parties (each holding an input $v_i)$ to correctly compute a function $g(v_1, \dots , v_n)$ without revealing anything about their inputs that could not be inferred from the output. The security of MPC is usually described in the UC framework [13]. At a high-level, a protocol is secure if it is “indistinguishable” from an ideal functionality with the desired properties.

We recall the ideal functionality for MPC with full security (where parties are guaranteed to obtain the correct output), and with L-output quality (the number of inputs taken into account for the computation), as introduced in [11].

A weaker notion of security is also of interest. In MPC with unanimous output, the ideal world adversary can choose whether all honest parties receive the correct output or they all receive symbol $\top$. We denote ideal functionality describing this security notion by $\mathcal {F}_\mathsf {MPC} ^{\mathsf {uout},L}$.

Definition 6

An MPC protocol $\varPi$ achieves t-full security (t-unanimous output) with L-output quality if it UC-realizes functionality $\mathcal {F}_{\mathsf {MPC}}^{{\mathsf {sec}},L}$ ($\mathcal {F}_{\mathsf {MPC}}^{{\mathsf {uout}},L}$), whenever up to t parties are corrupted in an execution of $\varPi$.

4 Round-Efficient Byzantine Agreement with Asynchronous Weak Validity

We study the feasibility and efficiency of BA protocols that are $t_s$-secure when the network is synchronous, and at the same time achieve $t_a$-weak validity when the network is asynchronous. This primitive is of independent interest, as it is used to construct BA protocols with asynchronous fallback (see Sect. 5). Moreover, it turns out to be fundamental in the design of further distributed protocols, for example to obtain constant-round synchronous broadcast protocols with asynchronous weak validity (see Sect. F), which in turn are used to construct synchronous MPC protocols with asynchronous fallback [11].

In this section, we completely characterize the threshold conditions under which such a primitive exists, and provide different round-efficient constructions (fixed-round and with probabilistic termination).

In Sect. 4.2, we show a fixed-round BA protocol that runs in $O(\kappa )$ rounds when the network is synchronous. In the full version of this paper [22], one can also find a version running in expected constant-rounds when the network is synchronous.⁴

While the optimal achievable trade-off (see [9]) of a BA protocol with full asynchronous fallback security is $t_a + 2t_s < n$ and $t_a \le t_s$ (which together imply $t_s < n/2$), we show that there is room for improvement when only requiring asynchronous weak-validity. In this case, we prove the optimal threshold trade-off to be $2t_a + t_s < n$ and $t_s < n/2$.

4.1 Weak Consensus with Asynchronous Weak Validity

The main tool in our BA constructions is a round-based weak consensus protocol that is secure in a synchronous network (up to $t_s$-corruptions), and achieves weak validity even if the network is asynchronous (up to $t_a$-corruptions).

In traditional weak-consensus, parties are allowed to output a symbol $\bot$, signaling they are unsure about what bit to output. We also allow parties to output symbol $\top$, which also signals a lack of information necessary to reach agreement, but only due to the network being asynchronous. Distinguishing between these two outcomes is essential, but not trivial. The reason is that, when designing round-based protocols, if the network is asynchronous one cannot take advantage of eventual delivery of messages, since parties only wait for a fixed amount of time $\varDelta$ per round. Therefore, when an expected message is not delivered within a round, parties cannot decide if 1) the network is synchronous and the sender is corrupted, or 2) the network is asynchronous and the message was delayed by the adversary.

We address this problem by making use of a gradecast (GBC) protocol that achieves graded validity and graded consistency when the network is synchronous, and weak-graded validity when the network is asynchronous (see Sect. B).

By requiring each party to gradecast their input, we can have parties take a non-$\top$ decision only if they receive at least $n-t_s$ values with grade 2. Indeed, if the network is synchronous, honest parties output grade 2 in all executions with honest senders. Therefore, less than $n-t_s$ outputs with grade 2 guarantee that the network is asynchronous and it is safe to output $\top$.

In case at least $n-t_s$ values with grade 2 are received, the output determination ensures the required guarantees: party $P _i$ outputs v if 1) they received (v, 2) from $n-t_s$ gradecasts, or 2) they received (v, 2) from at least $n-t_s-t_a$ gradecasts and $(1-v,\cdot )$ from up to $t_a$; in any other case they output $\bot$.

In particular, if the network is asynchronous and there are up to $t_a$ corruptions, weak validity is achieved: any party that does not output $\top$ has received at least $n-t_s$ values with grade 2, and $n - t_s - t_a > t_a$ of those values correspond to the inputs of honest parties. Moreover, when the network is synchronous and up to $t_s$ parties are corrupted, there cannot be honest parties $P _i$ and $P _j$ that output different bits v and $1-v$, respectively. This is because 1) if $P _i$ receives $(1-v,\cdot )$ up to $t_a$ times, then $P _j$ cannot receive $(1-v,2)$ more than $t_a$ times, and 2) if $P _i$ receives (v, 2) at least $n-t_s$ times, then $P_j$ receives $(v,\cdot )$ at least $n-t_s > t_a$ times.

We formally describe the protocol below. Let $\varPi _\mathsf {GBC} ^{t}$ be a gradecast protocol running in s rounds. The n executions of $\varPi _\mathsf {GBC} ^{t}$ are to be run in parallel to preserve round-efficiency. Security is proven in Sect. C.

Lemma 1

Assume protocol $\varPi _{\mathsf {GBC}}^{\max \{t_a,t_s\}}$ achieves the following security guarantees.

• When run over a synchronous network: $(\max \{t_s, t_a\})$-graded validity and $(\max \{t_s,t_a\})$-graded consistency.

• When run over an asynchronous network: $(\max \{t_s, t_a\})$-weak graded validity.

Then, if $2t_a + t_s < n$ and $t_s < n/2$, protocol $\varPi _{\mathsf {WC}}^{t_a, t_s}\left( \varPi _{\mathsf {GBC}}^{\max \{t_a,t_s\}}\right)$ achieves the following security guarantees.

• When run over a synchronous network: $t_s$-liveness, $t_s$-validity, $t_s$-weak consistency.

• When run over an asynchronous network: $t_a$-weak validity.

When assuming a worse tradeoff $t_a + 2t_s < n$ and $t_s \le t_a$ (which is optimal to achieve BA with full asynchronous fallback) one can obtain a simpler and more efficient weak consensus protocol with asynchronous weak validity (see Sect. D for a construction and security proof).

4.2 Fixed-Round Synchronous BA with Asynchronous Weak Validity

We now present a fixed-round synchronous Byzantine agreement protocol with asynchronous weak validity. If the network is synchronous and there are up to $t_s$ corruptions, agreement is reached with overwhelming probability after $O(\kappa )$ rounds. Moreover, even when the network is asynchronous and there are up to $t_a$ corruptions, the protocol achieves weak validity.

Following the traditional Feldman-Micali paradigm [24], parties run a sequence of iterations. Each iteration consists of a weak consensus protocol $\varPi _{\mathsf {WC}}^{t_a, t_s}$ followed by an invocation to the coin-flip functionality $\mathcal {F}_\mathsf {CoinFlip} ^{t_s}$, where: 1) parties that obtain a bit as output of $\varPi _{\mathsf {WC}}^{t_a, t_s}$ keep this value for the next iteration, 2) parties that obtained $\bot$ adopt the value of the coin, and 3) parties that obtained $\top$ keep their initial value of the iteration.

Notice that, if the network is synchronous, the output of an honest party in the execution of $\varPi _{\mathsf {WC}}^{t_a, t_s}$ is binary or $\bot$. Since weak consensus guarantees that honest parties do not output contradicting bits, and the coin value is uniform and independent of the output of weak consensus, agreement is reached with probability 1/2 per iteration.⁵

Moreover, if the network is asynchronous, weak validity is achieved. The reason is that in each iteration, if all honest parties start with the same value v, then weak validity of $\varPi _{\mathsf {WC}}^{t_a, t_s}$ ensures that they all output v or $\top$, and the coin value is ignored. Therefore, they keep v as the value for the next iteration.

We formally describe the protocol below. Security is proven in Section E.

Lemma 2

Assume protocol $\varPi _{\mathsf {WC}}^{t_a, t_s}$ achieves the following security guarantees.

• When run over a synchronous network: $t_s$-liveness, $t_s$-validity, and $t_s$-weak consistency.

• When run over an asynchronous network: $t_a$-weak validity.

Then, protocol $\varPi _{{\mathsf {SBA}}}^{t_a, t_s}\left( \varPi _{\mathsf {WC}}^{t_a, t_s}, \mathcal {F}_{\mathsf {CoinFlip}}^{t_s}\right)$ achieves the following security guarantees with overwhelming probability.

• When run over a synchronous network: $t_s$-security. Moreover, the protocol runs in $O(\kappa )$ rounds and achieves simultaneous termination.

• When run over an asynchronous network: $t_a$-weak validity.

4.3 Optimality of Synchronous BA with Asynchronous Weak Validity

In this section we prove the optimality of our constructions with respect to corruption thresholds. More specifically, we show that the tradeoff assumption $2t_a + t_s < n$ is not only sufficient, but also necessary to obtain BA protocols that are secure up to $t_s$ corruptions in a synchronous network, and achieve weak validity up to $t_a$ corruptions in an asynchronous network.

Lemma 3

Assume $2t_a + t_s \ge n$. There does not exist an n-party Byzantine agreement protocol that is both

• $t_s$-secure when run over a synchronous network;

• $t_a$-weakly valid when run over a synchronous network

Proof

Assume there exists a protocol $\varPi$ achieving all the above security guarantees. Partition the party set $\mathcal {P}$ into sets $S_a, S_b$ and K where $\#S_a = \#S_b=t_a$ and $\#K = t_s$.

• Scenario 1. The network is synchronous. Parties in $S_a$ participate in $\varPi$ with input 0. Parties in $S_b$ participate in $\varPi$ with input 1. Parties in K are corrupted by the adversary and simply abort.

• Scenario 2. All messages from parties in K are dropped (delayed for longer than the round time) by the adversary. Parties in $S_a$ participate in $\varPi$ with input 0. Parties in $S_b$ are corrupted by the adversary, but participate in $\varPi$ as if they were honest with input 1. Parties in K partecipate in the protocol with input 0.

• Scenario 3. All messages from parties in K are dropped (delayed for time $\delta > \varDelta$) by the adversary. Parties in $S_b$ participate in $\varPi$ with input 1. Parties in $S_a$ are corrupted by the adversary and participate in $\varPi$ as if they were honest with input 0. Parties in K participate in the protocol using input 1.

In scenario 1, parties in $S_a$ and $S_b$ output the same value $b_1 \in \{0,1\}$ by $t_s$-consistency and $t_s$-liveness of $\varPi$. In scenario 2, parties in $S_a$ output 0 or $\top$ by $t_a$-weak validity of $\varPi$. In scenario 3, parties in $S_b$ output 1 or $\top$ by $t_a$-weak validity of $\varPi$. Since the views of parties in $S_a$ in scenarios 1 and 2 are indistinguishable, and the views of parties in $S_b$ in scenarios 1 and 3 are indistinguishable, then in scenario 2 (respectively 3) no party in $S_a$ (respectively $S_b$) outputs $\top$. However, this means that $0 = b_1 = 1,$ which is a contradiction (here, we assumed parties are deterministic, but the same argument can be adapted to probabilistic parties and their output distributions).    $\square$

5 Synchronous BA with Asynchronous Fallback

In order to achieve a BA protocol that is $t_s$-secure when the network is synchronous, and $t_a$-secure when the network is asynchronous, we use the compiler $\varPi _{\mathsf {HBA}}^{t_a, t_s}$ introduced by Blum et al. [9]. The compiler assumes 1) a $t_s$-secure synchronous BA protocol $\varPi _\text {1}$ that is $t_a$-weakly valid even when run over an asynchronous network, and 2) a $t_a$-secure asynchronous BA protocol $\varPi _\text {2}$ that achieves validity and terminates for a higher corruption threshold $t_s \ge t_a$ when the network is synchronous. The idea is to run, in sequence, the synchronous BA protocol followed by the asynchronous one. The output from the first protocol is used as input to the second.

Intuitively, when the network is synchronous, security is provided by the synchronous protocol, and preserved by $t_s$-validity with termination of the asynchronous one. On the other hand, when the network experiences delays, security is provided by the asynchronous protocol, while $t_a$-weak validity of the round-based protocol ensures an adversary cannot break pre-agreement among honest parties.

Lemma 4

([9], Theorem 3). Assume protocol $\varPi _\text {1}$ achieves the following security guarantees.

• When run over a synchronous network: $t_s$-security.

• When run over an asynchronous network: $t_a$-weak validity.

Furthermore, assume protocol $\varPi _\text {2}$ achieves the following security guarantees.

• When run over a synchronous network: $t_s$-validity with termination.

• When run over an asynchronous network: $t_a$-security.

Then, if $t_a \le t_s$ and $t_a + 2t_s < n$, protocol $\varPi _{\mathsf {HBA}}^{t_a, t_s}\left( \varPi _\text {1}, \varPi _\text {2}\right)$ achieves the following security guarantees.

• When run over a synchronous network: $t_s$-security.

• When run over an asynchronous network: $t_a$-security.

By using our round-efficient synchronous BA protocols as the $\varPi _1$ component of the compiler (the fixed-round version in Sect. 4.2, or the expected constant-round version in the full version [22]), and the asynchronous protocols with increased validity from [9] as the second component $\varPi _2$,⁶ we obtain the following corollaries.

Corollary 1

Let $t_a \le t_s$ and $t_a + 2t_s < n$. There exists a protocol that achieves the following security guarantees with overwhelming probability.

• When run over a synchronous network: $t_s$-security. Moreover, it runs in $O(\kappa )$ rounds and achieves simultaneous termination.

• When run over an asynchronous network: $t_a$-security.

Corollary 2

Let $t_a \le t_s$ and $t_a + 2t_s < n$. There exists a protocol that achieves the following security guarantees with overwhelming probability.

• When run over a synchronous network: $t_s$-security. Moreover, it runs in expected constant number of rounds.

• When run over an asynchronous network: $t_a$-security.

6 Round-Efficient MPC with Asynchronous Fallback

Blum et al. [11] obtain the first MPC protocol that is $t_s$-secure in a synchronous network, and $t_a$-secure with $(n-t_s)$-output quality in an asynchronous network (these guarantees are provably optimal).

Their protocol requires black-box access to 1) a Byzantine agreement primitive that is $t_s$-secure in a synchronous network and $t_a$-secure in an asynchronous network, and 2) a broadcast primitive that is $t_s$-secure in a synchronous network and $t_a$-weakly valid in an asynchronous network. Their constructions for these primitives (borrowed from [9]) both require O(n) rounds. Moreover, their protocol evaluates the circuit in a gate-by-gate fashion, and therefore requires O(d) communication rounds, where d denotes the multiplicative depth of the circuit representing the function to evaluate.

Using our fixed-round BA and broadcast from Sect. 4.2 and Sect. F, and adapting Yao’s garbled circuit techniques [46], we obtain the first MPC protocol in this realm with optimal security guarantees and that has a total round complexity of $O(\kappa )$, independent of the circuit depth. We loosely follow the structure of [17].

6.1 Multi-party Garbled Circuits

Let g denote the function to evaluate, represented as a boolean circuit $\mathsf {circ} _g$ containing only $\texttt {NAND}$ gates.⁷ In general, the circuit-depth d of $\mathsf {circ} _g$ depends on g, and MPC protocols following the gate-by-gate paradigm typically require O(d) communication rounds. Using garbled circuit techniques,⁸ we obtain an MPC protocol with round complexity independent of d.

The high-level idea is to use MPC to evaluate a function $f_\mathsf {GRBL}$ that produces a garbled version of $\mathsf {circ} _g$, which parties can then evaluate locally. As we will discuss, the function $f_\mathsf {GRBL}$ can be represented as a circuit whose depth is independent of g.

Roughly speaking, $f_\mathsf {GRBL}$ outputs an encrypted version of $\mathsf {circ} _g$, in which all entries of each function table are encrypted using secret keys associated with the corresponding input values. A party holding two input values to a gate, together with the corresponding keys, can decrypt the corresponding entry of the function table and obtain the output of the gate (and the corresponding key). To preserve privacy, the values travelling on each wire are masked by $\texttt {XOR}$ing them with random bits. If a party is entitled to learn an output, they are given the corresponding random mask.

The function $f_\mathsf {GRBL}$ can be represented by a constant-depth circuit. The reason is that once the secret masks and keys for each wire have been generated, the garbled function tables of $\mathsf {circ} _g$ can be computed in parallel.

Distributed Encryption. There is a complication with the approach we described. To compute encryptions of the function table entries within the MPC, parties need white-box access to an encryption scheme. This is undesirable in itself, but matters are worsened by the fact that the circuit-representations of even the most efficient block-ciphers are fairly large ($\sim$6400 $\texttt {AND}$ gates for AES-128),⁹ making this approach unfeasible.

To overcome this problem, we use a distributed encryption technique due to Damgård and Ishai [20]. Let m denote a plaintext. Instead of computing $\mathsf {Enc} _k(m)$ within the multi-party computation, m is shared among the parties by means of a secret-sharing scheme (see Sect. A, Definition 8). Party $P_i$ receives a share $[m]_i$ and a secret key $K_i$ as output of the computation, and locally computes $c_i = \mathsf {Enc} _{K_i}([m_i])$. Each party then sends their encrypted shares to all parties. Upon receiving a sufficient number of encrypted shares, a party in possession of the necessary keys can decrypt them and reconstruct the secret (for example, if $P_j$ is entitled to know the secret, they receive the keys as output from the multi-party computation). This approach extends to the dual-key setting (see Definition 7, Sect. A), and only requires black-box access to the encryption scheme.

Information Checking Protocol. Moving encryption outside the MPC comes at the price of secret-sharing the plaintexts to preserve privacy. In our setting, the secrets are the entries of each function table of $\mathsf {circ} _g$, together with the key associated with the output value. Since we work (at least when the network is synchronous) with an honest majority, authentication of the shares is necessary to prevent corrupted parties to tamper with the reconstruction phase. This can be achieved by requiring the dealer (in our setting, $f_\mathsf {GRBL}$) to sign the shares using digital signatures, but computing signatures within the MPC of $f_\mathsf {GRBL}$ is also inefficient.

Instead, one can use the Information Checking Protocol by Rabin and Ben-Or [43]. It works over a finite field $\mathbb {F}_q$. For a secret s, the dealer samples uniformly random elements $(\mathfrak {b}, \mathfrak {y})$, and computes $\mathfrak {c} = s + \mathfrak {by}$. Party $P_i$ is given $(s, \mathfrak {y})$: the authentication vector. Another party $P_j$ (to whom $P_i$ wishes to forward s at a later time), is given $(\mathfrak {b}, \mathfrak {c})$: the check vector. Upon receiving the couple $(s, \mathfrak {y})$ from $P_i$, party $P_j$ can check that $\mathfrak {c} = s + \mathfrak {by}$. If $P_i$ is corrupted and wants to send $s' \ne s$ to $P_j$, party $P_i$ has to guess the unique $\mathfrak {y}'$ solving $\mathfrak {c} = s'\mathfrak {b} + \mathfrak {y}'$, which they can only do with probability $1/(q-1)$, as the field element $\mathfrak {c} - s'\mathfrak {b}$ is distributed according to $\mathfrak {b}$.

The resulting function $f_\mathsf {GRBL}$ is formally described below. The wires of $\mathsf {circ} _g$ are denoted by lower-case greek letters ($\alpha , \beta , \gamma$, $\dots$), and the gates with lower case english letters (a, b, c, $\dots$). The input $b_i$ of party $P_i$ is a vector containing a boolean encoding of their input to g as well as extra inputs needed to generate randomness.

In the next section, we describe the MPC protocol we will use to compute $f_\mathsf {GRBL}$.

6.2 MPC with Linear Round Complexity in d and $\kappa$ and Asynchronous Fallback

To achieve security in both synchronous and asynchronous networks, we want to compute $f_\mathsf {GRBL}$ using the compiler from [11]. We recall the construction and its security guarantees below.

Lemma 5

([11], Theorem 2). Assume protocol $\varPi _1$ achieves the following security guarantees.

• When run over a synchronous network: $t_s$-security.

• When run over an asynchronous network: $t_a$-unanimous output, $t_a$-weak termination and $(n-t_s)$-output quality.

Furthermore, assume protocol $\varPi _2$ achieves the following security guarantees.

• When run over an asynchronous network: $t_a$-security with $(n-t_a)$-output quality.

Then, assuming $t_a \le t_s$ and $t_a + 2t_s < n$, protocol $\varPi _{\mathsf {HMPC}}^{t_s, t_a}\left( \varPi _1, \varPi _2\right)$ achieves the following security guarantees.

• 1. When run over a synchronous network: $t_s$-security.

• 2. When run over an asynchronous network: $t_a$-security and $(n-t_s)$-output quality.

We provide sub-protocols $\varPi _1, \varPi _2$ with the security guarantees required by Lemma 5, and that in addition 1) securely evaluate boolean circuits, and 2) require O(d) communication rounds.

We take $\varPi _1$ to be the synchronous protocol $\varPi _\mathsf {SMPC} ^{t_a, t_s}$ of [11, Section 4.5], which requires O(d) rounds; it is the only known synchronous protocol to date providing the necessary security guarantees.

However, we cannot use $\varPi _\mathsf {SMPC} ^{t_s, t_a}$ in a black-box manner, since it evaluates arithmetic circuits defined over “large” fields ($\#\mathbb {F}_q > n$), while in our construction it is natural to represent the boolean function $f_\mathsf {GRBL}$ as a boolean circuit. One solution is to embed the boolean circuit into a larger field through the inclusion map $i\,:\,\mathbb {F}_2 \rightarrow \mathbb {F}_{q}$ and to represent $\texttt {NAND}$ gates with arithmetic gates computing $a(x,y):= 1 - xy$ (it is straightforward to verify that $i \circ a = a \circ i$).

To keep actively corrupted parties from giving inputs in $\mathbb {F}_q \setminus \{0,1\}$, a checking mechanism has to be put into place. The high level idea of $\varPi _\mathsf {SMPC} ^{t_s, t_a}$ is that the inputs of each party are encrypted using an additively-homomorphic threshold encryption scheme. To ensure correctness, after broadcasting their encrypted inputs, parties must prove (in ZK) knowledge for the corresponding plaintext. In addition, we require parties to prove in ZK that the plaintext lies in $\{0,1\}$.

The protocol then follows the gate-by-gate paradigm, with additional interaction required to evaluate multiplication gates. After the circuit is evaluated, parties reconstruct the outputs using threshold decryption. A security proof can be obtained as for [11, Theorem 1] with minor changes.

We take $\varPi _2$ to be the modified version (by Coretti et al. [17]) of protocol $\pi _{\text {BKR}}$ by Ben-Or et al. [8], which evaluates boolean circuits and requires O(d) rounds. Security is proven in [17, Lemma 2].

Lemma 5, with these choices of $\varPi _1$ and $\varPi _2$, yields the following corollary.

Corollary 3

Assume $t_a \le t_s$ and $t_a + 2t_s <n$. There exists a protocol $\varPi _{{\mathsf {HMPC}}}^{t_s, t_a}$ evaluating boolean circuits and requiring O(d) communication rounds achieving the following security guarantees.

• When run over a synchronous network: $t_s$-security.

• When run over an asynchronous network: $t_a$-security and $(n-t_s)$-output quality.

Our modification of Protocol $\varPi _\mathsf {SMPC} ^{t_a, t_a}$ [11], used as $\varPi _1$ in compiler $\varPi _\mathsf {HMPC} ^{t_a, t_s}$, requires black-box access to:

• (i) a Byzantine agreement sub-protocol that is $t_s$-secure when run over a synchronous network, and $t_a$-secure when run over an asynchronous network;

• (ii) a broadcast sub-protocol that is $t_s$-secure when run over a synchronous network, and $t_a$-weakly valid when run over an asynchronous network.

At the time of [11], the only known protocols with these guarantees required O(n) rounds,¹⁰ resulting in O(n) round-complexity of the MPC protocol.

In Sect. F, we present a broadcast protocol $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}\left( \varPi _{{\mathsf {SBA}}}^{t_a, t_s}\right)$ running in a fixed number of rounds that is weakly valid in asynchronous networks. Our solution is inspired by a synchronous construction that obtains BC from BA, but requires some modifications to achieve security guarantees in asynchronous networks.

Combining this with results from previous sections, we obtain an MPC protocol running in $O(\kappa )$ rounds with respect to n. More specifically,

• Lemma 1 (or Lemma 8), Lemma 2, and Lemma 4, guarantee that protocol $\varPi _{\mathsf {HBA}}^{t_a, t_s}\left( \varPi _{\mathsf {SBA}}^{t_a, t_s}, \varPi _{\mathsf {ABA}}^{t_a, t_s}\right)$ from Sect. 5 (which runs in $O(\kappa )$ rounds with respect to the number of parties n) achieves the security guarantees (i);

• Lemma 1, (or Lemma 8), Lemma 2, and Lemma 9, guarantee protocol $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}\left( \varPi _{{\mathsf {SBA}}}^{t_a, t_s}\right)$ from Sect. F (that also runs in $O(\kappa )$ rounds with respect to the number of parties n) achieves the security guarantees (ii).

Combining this with Corollary 3, we obtain the following corollary.

Corollary 4

Assume $t_a \le t_s$ and $t_a + 2t_s <n$. There exists a MPC protocol with the following properties.

• When run over a synchronous network: $t_s$-security.

• When run over an asynchronous network: $t_a$-security and $(n-t_s)$-output quality.

• If the network is synchronous, runs in $O(\kappa )$ rounds.

• Runs in O(d) rounds.

Recall that the security guarantees of Corollary 4 are optimal ([11, Theorems 3, 4]).

6.3 Protocol Description

We now present our fully constant-round MPC protocol that is 1) $t_s$-secure if the network is synchronous, and 2) $t_a$-secure with $(n-t_s)$-output quality if the network is asynchronous. The construction, that we already discussed, consists of three steps.

• (Parties jointly) use an MPC protocol with the properties of Corollary 4 to compute function $f_\mathsf {GRBL}$.

• (Each party) encrypts the authenticated shares of the entries of each gate of $\mathsf {circ} _g$ received as output of $f_\mathsf {GRBL}$ (the keys are also part of the output). They send the resulting ciphertexts to all parties.

• (Each party) evaluates the circuit locally: given two (masked) inputs to a gate and the corresponding keys, they decrypt the received shares of the corresponding entry of the gate, recovering the (masked) output value and the corresponding key. They do this until all gates are evaluated. Finally, they unmask the accessible outputs.

A phase indicator $\phi$ guarantees that, if the network is asynchronous, parties do not terminate before sending the encryptions of their shares to other parties. Security is discussed in Sect. G.

Lemma 6

Suppose that $t_a \le t_s$ and $t_a + 2t_s <n$, and assume that protocol $\varPi _{\mathsf {HMPC}}^{t_s, t_a}$ achieves the security guarantees of Corollary 4. Then, protocol $\varPi _{\mathsf {CR-HMPC}}^{t_s, t_a}\left( \varPi _{\mathsf {HMPC}}^{t_s, t_a}\right)$ achieves the same security guarantees, and requires a number of rounds independent of the circuit depth of the function to be evaluated, when the network is synchronous.

Appendices

Appendix

A Additional Definitions

Symmetric-Key Encryption. We recall the definition of a symmetric encryption scheme.

Definition 7

A symmetric encryption scheme is a triple $({\mathsf {Enc}},{\mathsf {Dec}},{\mathsf {Kgn}})$ of algorithms such that:

• the key generation algorithm ${\mathsf {Kgn}}$ outputs a secret key $K \in \mathcal {K}$;

• given a secret key $K \in \mathcal {K}$ and a plaintext $m \in \{0,1\}^*$, the encryption algorithm ${\mathsf {Enc}}$ outputs a ciphertext $\mathcal {C} \ni c := {\mathsf {Enc}}_K(m)$;

• given a ciphertext $c \in \mathcal {C}$ and a secret key $K \in \mathcal {K}$, the decryption algorithm ${\mathsf {Dec}}$ outputs ${\mathsf {Dec}}_K(c) \in \{0,1\}^*$;

• ${\mathsf {Dec}}_K\left( {\mathsf {Enc}}_K(m)\right) =m$ for all $m \in \{0,1\}^*$ and $K \in \mathcal {K}$.

In a dual key encryption scheme, two keys $K_1, K_2$ are needed to encrypt and decrypt. The semantics are otherwise unchanged.

Secret-Sharing. A secret-sharing scheme allows a dealer D to distribute a secret s among a set $\mathcal {P}$ of n parties, so that only certain qualified subsets of parties can reconstruct the secret. Other subsets should obtain no information about the secret. A secret-sharing scheme is specified by its access structure $\varGamma \subseteq 2^\mathcal {P}$: the collection of the qualified subsets of parties.

Definition 8

A secret-sharing scheme for access structure $\varGamma$ is a pair of protocols $({\mathsf {Share}}, {\mathsf {Reconstruct}})$with the following properties.

• After ${\mathsf {Share} (s)}$, there is a unique value $s'$ that can be reconstructed, and $s' = s$ if the dealer is honest. Furthermore, any subset of parties $S \in \varGamma$ can execute ${\mathsf {Reconstruct}}$ to reconstruct s.

• After ${\mathsf {Share} (s)}$, any subset of parties $S \notin \varGamma$ obtains no information about s.

We are interested in t-out-of-n secret-sharing schemes, that is, secret sharing schemes where $\varGamma := \{S \in 2^\mathcal {P} \,:\, \#S \ge t\}$.

B Gradecast with Asynchronous Weak Validity

We present, using slightly different notation, a 4-round gradecast protocol by Katz et al. [32] and explicitly show that their construction achieves t-weak graded validity (q.v. Definition 5) for all $t < n/2$ when the network is asynchronous. We refer to the full version [22] for the security proofs.

Lemma 7

Assume $t < n/2$. Protocol $\varPi _\mathsf {GBC} ^t$ achieves the following security guarantees.

• When run over a synchronous network: t-graded validity and t-graded consistency.

• When run over an asynchronous network: t-weak graded validity.

C Proof of Lemma 1

Assume that that at most $t_s$ parties are corrupted in an execution of protocol $\varPi _{\mathsf {WC}}^{t_a, t_s}\left( \varPi _{\mathsf {GC}}^{\max \{t_a, t_s\}}\right)$ over a synchronous network.

[liveness] Synchrony of the network and $t_s$-graded validity of $\varPi _{\mathsf {GC}}^{\max \{t_a, t_s\}}$ guarantee that each honesty party $P_j$ sets $b_{ij} := \varPi _{\mathsf {GC}}^{\max \{t_a, t_s\}}(i) = (v_i, 2)$ each time party $P_i$ is honest. Therefore, $\#(S_j^v \sqcup S_j^{1-v}) \ge n -t_s$, so that $P_j$ sets $b_j \in \{0, 1, \bot \}$ during output determination and does not output $\top$. This proves $t_s$-liveness.

[validity] Suppose that all honest parties hold the same input v. synchrony of the network and $t_s$-graded validity of protocol $\varPi _{\mathsf {GC}}^{\max \{t_a, t_s\}}$ guarantee that each honesty party $P_j$ sets $b_{ij} := \varPi _{\mathsf {GC}}^{\max \{t_a, t_s\}}(i) = (v, 2)$ each time party $P_i$ is honest. Therefore, $\#S^v_j \ge n-t_s$ and party $P_j$ outputs v. It is worth noting that if both $\#S_j^v \ge n-t_s$ and $\#S_j^{1-v} \ge n-t_s$, then $n \ge \#(S_j^v \sqcup S_j^{1-v}) \ge 2n - 2t_s > n$, which is absurd. This proves $t_s$-validity.

[weak consistency] Suppose an honest party $P_j$ outputs $v \in \{0,1\}$. There are two possibilities. The first is that

$$\begin{aligned} {\left\{ \begin{array}{ll} \begin{aligned} &{}\#S_j^{v} \ge n - t_s - t_a\\ &{}\#(S^{1-v}_j \sqcup U_j^{1-v}) \le t_a. \end{aligned} \end{array}\right. } \end{aligned}$$

(1)

If $P_i$ is another honest party, then synchrony of the network and $t_s$-graded consistency of $\varPi _{\mathsf {GBC}}^{\max \{t_a,t_s\}}$ guarantee that $\#S_i^{1-v} \le t_a < n - t_s - t_a \le n - t_s.$ If this was not the case, by $t_s$-graded consistency of $\varPi _{\mathsf {GBC}}^{\max \{t_a,t_s\}}$ we would have $\#(S^{1-v}_j \sqcup U_j^{1-v}) > t_a$, which is a contradiction. Therefore, party $P_i$ does not output $1-v$. The second case is that $\#S_j^v \ge n-t_s$. In this case (reasoning as above), for an honest player $P_i$

$$\begin{aligned} {\left\{ \begin{array}{ll} \#(S_i^{v} \sqcup U_i^{v}) \ge n - t_s > 2t_a \ge t_a\\ \#S_i^{1-v} < n - t_s \end{array}\right. } \end{aligned}$$

(2)

so that $P_i$ does not output $1-v$. This proves $t_s$-weak consistency.

Assume that that at most $t_a$ parties are corrupted in an execution of protocol $\varPi _{\mathsf {WC}}^{t_a, t_s}\left( \varPi _{\mathsf {GC}}^{\max \{t_a, t_s\}}\right)$ over an asynchronous network.

[weak validity] Assume all honest parties hold the same input v. Suppose an honest party $P_j$ does not output $\top$. This means $\#(S_j^v \sqcup S_j^{1-v}) \ge n-t_s$. By $t_a$-weak graded validity of protocol $\varPi _{\mathsf {GC}}^{\max \{t_a, t_s\}}$, party $P_j$ sets $b_{ij} := \varPi _{\mathsf {GC}}^{\max \{t_a, t_s\}}(i) \in \{v, \top \}$ for each honest party $P_i$. Therefore, $\#S_j^{1-v} \le t_a < n - t_s - t_a \le n - t_s$ (so that party $P_j$ does not output $1-v$), but also

$$\begin{aligned} {\left\{ \begin{array}{ll} \#S_j^{v} \ge n-t_s - \#S_j^{1-v} \ge n - t_s - t_a\\ \#(S_j^{1-v} \sqcup U_j^{1-v}) \le t_a \end{array}\right. } \end{aligned}$$

(3)

so that party $P_j$ outputs v. This proves $t_a$-weak validity and concludes the proof of the lemma.

D A Simpler Weak-Consensus with Asynchronous Weak Validity for $t_a + 2t_s<n$ and $t_a\le t_s$

We show a simple 3-round construction for a weak consensus protocol that is 1) $t_s$-secure in a synchronous network, and 2) $t_a$-weakly valid in an asynchronous network, under the stronger assumptions that $t_a + 2t_s < n$, $t_a \le t_s$ (these assumptions are optimal for BA with full asynchronous fallback [9]). The public key infrastructure available allows parties to forward cryptographic evidence (in the form of digital signatures) that they received a given message from other parties by appropriately combining this evidence to generate what we refer to as certificates (see e.g. [30]). An $\ell$-certificate on a bit b is simply a concatenation of at least $\ell$ valid signatures on b from distinct parties.

Lemma 8

Assume $t_a + 2t_s < n$ and $t_a \le t_s$. Protocol $\varPi _{{\mathsf {WC}}}^{t_a, t_s}$ achieves the following security guarantees.

• When run over a synchronous network: $t_s$-liveness, $t_s$-validity, and $t_s$-weak consistency.

• When run over an asynchronous network: $t_a$-weak validity.

Proof

Assume that at most $t_s$ parties are corrupted in an execution of $\varPi _{{\mathsf {WC}}}^{t_a, t_s}$ over a synchronous network.

[liveness] Each honest party $P_j$ sends message $(v_j, \mathsf {Sgn} (v_j, \texttt {pk}_j))$ to all parties at in Round 1. synchrony of the network guarantees all these messages are delivered within the round. It follows that, in Round 2, $\#S_j \ge n - t_s$ for each honest party $P_j$, so that $P_j$ sets $b_j = \bot$. This proves $t_s$-liveness, as $b_j$ is never set to $\top$.

[validity] Assume each honest party holds the same input $v \in \{0, 1\}$. In Round 1, each honest $P_j$ sends message $(v_j, \mathsf {Sgn} (v_j, \texttt {pk}_j))$ to all parties. synchrony of the network guarantees that $\#S_j^v \ge n - t_s \ge n - t_s - t_a$ for each honest party $P_j$, so that $P_j$ sets $b_j = v$ in Round 2. Notice that $\#S_j^{1-v} \le t_s < n - t_s - t_a$. No honest party signs bit $1-v$ at any point in the execution of the protocol, and the adversary cannot forge signatures on behalf of honest parties. Together with $t_s < n - t_s -t_a$, this implies that no $(n-t_s-t_a)$-certificate on bit $1-v$ can be produced by corrupted parties, so that no honest party $P_j$ sets $b_j = \bot$ in Round 3. In conclusion, each honest party $P_j$ outputs $b_j = v$. This proves $t_s$-validity.

[weak consistency] Assume an honest party $P_j$ outputs v. This means $P_j$ sets $b_j = v$ in Round 2, and sends a $(n-t_s-t_a)$-certificate on v to all parties in Round 3. synchrony of the network guarantees that this certificate is delivered to all honest parties by the end of the round. In conclusion, no honest party outputs $1-v$. This proves $t_s$-weak consistency.

Assume that that at most $t_a$ parties are corrupted in an execution of $\varPi _{{\mathsf {WC}}}^{t_a, t_s}$ over an asynchronous network.

[weak validity] Assume each honest party holds the same input $v \in \{0, 1\}$ and assume an honest party $P_j$ does not output $\top$. This means $\#S_j \ge n-t_s$. Notice that $S_j = S_j^{v} \sqcup S_j^{1-v}$. The adversary cannot forge honest parties’ signatures, which guarantees $\#S_j^{1-v} \le t_a$; this implies $\#S_j^v \ge \#S_j - t_a \ge n - t_s - t_a$, so that $P_j$ sets $b_j = v$ in Round 2. The assumption $t_a \le t_s$ guarantees that $t_a \le t_s < n - t_s - t_a$, which means corrupted parties cannot produce an $(n - t_s - t_a)$-certificate on $1-v$. In conclusion, party $P_j$ outputs $b_j = v$ in Round 3. This proves $t_a$-weak validity and concludes the proof of the lemma.    $\square$

E Proof of Lemma 2

Assume that that at most $t_s$ parties are corrupted in an execution of $\varPi _{\mathsf {SBA}}^{t_a, t_s}$ over a synchronous network.

[liveness] We claim that each honest party $P_j$ inputs $b_j \in \{0,1\}$ to the execution of $\varPi _{\mathsf {WC}}^{t_a, t_s}$ in iteration k (for all k). This holds trivially for $k=1$. Suppose it holds for k. synchrony of the network guarantees that, by $t_s$-liveness of $\varPi _{\mathsf {WC}}^{t_a, t_s}$, $b_j \in \{0, 1, \bot \}$ for each honest party $P_j$ after running weak-consensus in iteration k. Since ${\mathsf {coin}}_k \in \{0,1\}$, then $b_j \in \{0,1\}$ for each honest party $P_j$ at the end of iteration k, so that $P_j$ inputs $b_j \in \{0,1\}$ to the execution of $\varPi _{\mathsf {WC}}^{t_a, t_s}$ in iteration $k+1$. The claim follows by induction on k. Therefore, after iteration $\kappa$, party $P_j$ outputs $b_j \in \{0,1\}$. This proves $t_s$-liveness.

[validity] Assume each honest party $P_j$ holds the same input $v \in \{0,1\}$. We claim that each honest party $P_j$ inputs v to the execution of $\varPi _{\mathsf {WC}}^{t_a, t_s}$ in iteration k (for all k). This holds trivially for $k=1$. Suppose it holds for k. synchrony of the network guarantees that, by $t_s$-validity of $\varPi _{\mathsf {WC}}^{t_a, t_s}$, $b_j = v \in \{0,1\}$ for each honest party $P_j$ after round the execution of weak-consensus in iteration k. Therefore, party $P_j$ ignores the value $\mathsf {coin} _k$ and keeps $b_j = v$ at the end of the iteration. In conclusion, party $P_j$ inputs v to the execution of $\varPi _{\mathsf {WC}}^{t_a, t_s}$ in iteration $k+1$. The claim follows by induction on k. Therefore, after iteration $\kappa$, party $P_j$ outputs $b_j =v$. This proves $t_s$-validity.

[consistency] synchrony of the network guarantees that, by $t_s$-weak consistency of $\varPi _{\mathsf {WC}}^{t_a, t_s}$, after the execution of weak consensus in iteration k, there is $b^k \in \{0, 1\}$ such that $b_j = b^k$ or $b_j = \bot$ for each honest party $P_j$ (for all k). Since $\mathsf {coin} _k$ is a uniformly random bit (independent of $b^k$, since the adversary only learns the value $\mathsf {coin} _k$ after each honest party has produced output from weak consensus in iteration k), then $\mathbb {P}(\mathsf {coin} _k = b^k) = 1/2$ for all k. Furthermore, synchrony of the network guarantees that, by $t_s$-validity of $\varPi _{\mathsf {WC}}^{t_a, t_s}$, if $\mathsf {coin} _k =b^k$ for some k, then $b_j = b^k$ at the end of iteration k for each honest party $P_j$ and for all $k' \ge k$ (the proof is by induction on $k'$ as above, and we omit it).

For each positive integer k, let $\mathsf {agree} _k$ denote the event that there exists $b \in \{0,1\}$ such that $b_j = b$ for each honest party $P_j$ at the end of iteration k. We denote by $\mathsf {agree} _{0}$ the event that all honest parties hold the same input. Furthermore, let $\mathsf {abort} _k$ denote the event that some honest party $P_j$ outputs $\bot$ from the execution of $\varPi _{{\mathsf {WC}}}^{t_a, t_s}$ in iteration k. For each $k \ge 0$ we have

$$\begin{aligned} \begin{aligned} \mathbb {P}(\mathsf {agree} _{k+1}\,|\,\mathsf {agree} _k^c)&= \mathbb {P}\big ( \mathsf {agree} _{k+1} \cap (\mathsf {abort} _{k+1} \sqcup \mathsf {abort} _{k+1}^c)\,|\,\mathsf {agree} _k^c\big )\\&= \mathbb {P}\big ( \mathsf {agree} _{k+1} \cap \mathsf {abort} _{k+1}\,|\,\mathsf {agree} _k^c\big )\\&= \mathbb {P}\big (\mathsf {agree} _{k+1}\,|\,\mathsf {abort} _{k+1}\cap \mathsf {agree} _k^c\big )\mathbb {P}\big (\mathsf {abort} _{k+1}\big )\\&+\mathbb {P}\big (\mathsf {agree} _{k+1}\,|\,\mathsf {abort} _{k+1}^c \cap \mathsf {agree} _k^c\big )\mathbb {P}\big (\mathsf {abort} _{k+1}^c\big )\\&= \mathbb {P}\big (\mathsf {coin} _{k+1}= b^{k+1}\big )\mathbb {P}\big (\mathsf {abort} _{k+1}\big )+ 1 \cdot \mathbb {P}\big (\mathsf {abort} _{k+1}^c\big )\\&= \frac{1}{2}\left( \mathbb {P}\big (\mathsf {abort} _{k+1}\big ) + \mathbb {P}\big (\mathsf {abort} _{k+1}^c\big )\right) + \frac{1}{2}\mathbb {P}\big (\mathsf {abort} _{k+1}^c\big ) \ge \frac{1}{2}. \end{aligned} \end{aligned}$$

(4)

Notice, once again, that the above equality $\mathbb {P}\big (\mathsf {agree} _{k+1}\,|\,\mathsf {abort} _{k+1} \cap \mathsf {agree} _k^c\big ) = \mathbb {P}\big (\mathsf {coin} _{k+1}= b^{k+1}\big )$ holds because $t_s$ corrupted parties alone cannot learn $\mathsf {coin} _{k+1}$ in advance, so that the output of honest parties in the execution of $\varPi _{{\mathsf {WC}}}^{t_a, t_a}$ is independent from the value of $\mathsf {coin} _{k+1}$ in iteration $k+1$. The observation that $\mathsf {agree} _k^c \supseteq \mathsf {agree} _{k+1}^c$ allows us to finally estimate

(5)

This proves $t_s$-consistency.

Assume that that at most $t_a$ parties are corrupted in an execution of $\varPi _{\mathsf {SBA}}^{t_a, t_s}$ over an asynchronous network.

[weak validity] Assume each honest party $P_j$ holds the same input $v \in \{0,1\}$. We claim that each honest party $P_j$ inputs v to the execution of $\varPi _{\mathsf {WC}}^{t_a, t_s}$ in iteration k (for all k). The claim is trivially true for $k=1$. Assume it is true for k. By $t_a$-weak validity of protocol $\varPi _{\mathsf {WC}}^{t_a, t_s}$, each honest party $P_j$ outputs either v or $\top$ from $\varPi _{\mathsf {WC}}^{t_a, t_s}$ in iteration k. Therefore, each honest party $P_j$ ignores the coin-flip value and sets $b_j = v$ at the end of iteration k, and therefore inputs $b_j = v$ to the following execution of $\varPi _{\mathsf {WC}}^{t_a, t_s}$ in iteration $k+1$. The claim follows by induction on k. In conclusion, each honest party outputs $b_j = v$ at the end of iteration $\kappa$. This proves $t_a$-weak validity.

F Synchronous Broadcast with Asynchronous Weak Validity

We now explain how to obtain a broadcast protocol that is $t_s$-secure in a synchronous network and $t_a$-weakly valid in an asynchronous network, starting from a BA with the same guarantees. In addition to the rounds required by the BA, our construction runs only 2 rounds. In particular, given a fixed-round BA, it yields a fixed-round broadcast protocol. The opposite construction (BA from broadcast) is shown in [9]. Together, these result completely resolve the question of equivalence of BA and broadcast with asynchronous weak validity.

The idea, well known in the synchronous model, is for the sender $P^*$ to send their input to all parties in the first round; parties then run a Byzantine agreement protocol on the values they received to ensure consistency. However, this construction cannot be directly translated to our setting: if an honest party $P_j$ does not receive a message from the sender $P^*$ within the first round, then $P^*$ could be corrupted, or the adversary might have delayed the message. In the former scenario, an easy patch would be to input a default value to the BA protocol, but this solution does not allow to achieve weak validity in the latter scenario. On the other hand, not inputting any message to the Byzantine agreement protocol fails to provide consistency if the network is synchronous.

We solve this problem by having parties run two BAs: one to agree on whether the sender behaved honestly, and one to agree on a received value. These executions can be carried out in parallel for improved round efficiency.

Let $\varPi _{{\mathsf {SBA}}}^{t_a, t_s}$ be a synchronous Byzantine agreement protocol (for example, our protocol with asynchronous weak validity from Sect. 4.2) which runs in s rounds.

Lemma 9

Assume protocol $\varPi _{{\mathsf {SBA}}}^{t_a, t_s}$ achieves the following security guarantees.

• When run over a synchronous network: $t_s$-validity and $t_s$-consistency.

• When run over an asynchronous network: $t_a$-weak validity.

Then, protocol $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}\left( \varPi _{{\mathsf {SBA}}}^{t_a, t_s}\right)$ achieves the following security guarantees.

• When run over a synchronous network: $t_s$-validity and $t_s$-consistency.

• When run over an asynchronous network: $t_a$-weak validity.

Proof

Assume that that at most $t_s$ parties are corrupted in an execution of $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}\left( \varPi _{{\mathsf {SBA}}}^{t_a, t_s}\right)$ over a synchronous network.

[validity] If the sender $P^*$ is honest, they send $(v^*, \mathsf {Sgn} (v^*, \texttt {pk}^*))$ to all parties in round 1. synchrony of the network guarantees these messages are delivered within the round, so that each honest party $P_j$ sets $\mathsf {received-input} _j :=1$ and $b_j := v^*$ in round 1. By $t_s$-validity of $\varPi _{\mathsf {SBA}}^{t_a, t_s}$, each honest party sets $\mathsf {received-input} _j := \varPi _{\mathsf {SBA}}^{t_a, t_s}( \mathsf {received-input} _j = 1) = 1$ and $b_j := \varPi _{\mathsf {SBA}}^{t_a, t_s}(b_j = v^*) = v^*$ in round $3+s$, and outputs $b_j = v^*$ from $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}\left( \varPi _{{\mathsf {SBA}}}^{t_a, t_s}\right)$. This proves $t_s$-validity.

[consistency] Assume an honest party $P_j$ outputs $v \ne \top$. This means that $\mathsf {received-input} _j$ equals 1 in round $3+s$. Then, $t_s$-consistency of $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}$ guarantees $\mathsf {received-input} _i = 1$ in round $3+s$ for each honest party $P_i$. Furthermore, $t_s$-validity of $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}$ guarantees that at least one honest party $P_k$ inputs $\mathsf {received-input} _k =1$ to $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}$ in round 3. This means party $P_k$ received a validly signed message from the sender in round 1, and forwarded this message to all parties in round 2. synchrony of the network then guarantees $b_i \ne \top$ for each honest party $P_i$ in round 3. Since each honest party provides a valid input, $t_s$-consistency of $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}$ guarantees that $b_i = b_j = v$ in round $3+s$ for each honest party $P_i$, so that $P_i$ outputs v from $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}\left( \varPi _{{\mathsf {SBA}}}^{t_a, t_s}\right)$. This proves $t_s$-consistency.

Assume that that at most $t_a$ parties are corrupted in an execution of protocol $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}\left( \varPi _{{\mathsf {SBA}}}^{t_a, t_s}\right)$ over an asynchronous network.

[weak validity] Assume the sender $P^*$ is honest and has input $v^*$. Up to (and including) round 3, an honest party $P_j$ sets $b_j :=v \ne \top$ only if they receive a message $(v, \sigma )$ such that $\mathsf {Vfy} (v, \sigma , \texttt {pk}^*) =1$. Since corrupted parties cannot forge an honest sender’s signature, $b_j \in \{v^*, \top \}$ in round 3 for each honest party $P_j$. Observe that, if $b_j = \top$ in round 3, party $P_j$ does not send a message whenever they are supposed to share their input in $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}$; this does not break $t_a$-weak validity of $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}$, since messages can be arbitrarily delayed by the adversary. Therefore, $t_a$-weak validity of $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}$ guarantees that $b_j \in \{v^*, \top \}$ in round $3+s$ for each honest party $P_j$. In conclusion, each honest party $P_j$ outputs either $v^*$ or $\top$ from $\varPi _{{\mathsf {SBC}}}^{t_a, t_s}\left( \varPi _{{\mathsf {SBA}}}^{t_a, t_s}\right)$. This proves $t_a$-weak validity, and concludes the proof of the lemma.    $\square$

G Proof of Lemma 6

We sketch the proof. Assume at most $t_s$ parties are corrupted and the network is synchronous. Then, $t_s$-security of $\varPi _{\mathsf {HMPC}}^{t_s, t_a}$ guarantees that each party receives the same correct output from the computation of $f_\mathsf {GRBL}$ in Step 1 (which takes into account the input of all honest parties). Therefore, each honest party encrypts their (authenticated) shares of each gate of $\mathsf {circ} _g$ and sends the resulting ciphertexts to all parties. synchrony of the network guarantees that each honest party receives at least $n - t_s > t_s$ valid (i.e. such that the information checking protocol succeeds) and consistent shares for each gate within one extra round. Since dishonest parties cannot forge authentication vectors, even a rushing adversary cannot compromise the reconstruction of the function table entries. Together with the masked inputs and the relative keys for each input wire, as well as the masks for the accessible output wires, the (only) reconstructed function table entry for each gate allows each honest party $P_j$ to evaluate the garbled version of $\mathsf {circ} _g$ locally and recover the output. In particular, each honest party terminates.

Now, Assume at most $t_a$ parties are corrupted and the network is asynchronous. Then, $t_a$-security of protocol $\varPi _{\mathsf {HMPC}}^{t_s, t_a}\left( {\mathsf {circ}}_{f_{\mathsf {GRBL}}}; {\mathsf {circ}}_g; b_j\right)$ guarantees that each honest party receives the same output (taking into account the inputs of at least $n-t_s$ honest parties) from the computation of $f_\mathsf {GRBL}$ in Step 1. Notice that if $\phi _j = 0$ (i.e. if $P_j$ has not yet sent their encrypted shares), then party $P_j$ does not terminate. Eventual delivery then guarantees that each honest party receives at least $n-t_a \ge n - t_s \ge t_s+1$ valid and consistent encrypted shares of each function table entry of $\mathsf {circ} _g$. Since dishonest parties cannot forge authentication vectors, each set of $t_s+1$ valid shares identifies the same secret. Together with the masked inputs and the relative keys for each input wire, as well as the masks for the accessible output wires, the (only) reconstructed function table entry for each gate allows each honest party $P_j$ to evaluate the garbled version of $\mathsf {circ} _g$ locally and recover the output. In particular, each honest party terminates.