TinyKeys: A New Approach to Efficient Multi-Party Computation

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=10$ parties with $h=4$ 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.

1 Introduction

Secure multi-party computation (MPC) protocols allow a group of n parties to compute some function f on the parties’ private inputs, while preserving a number of security properties such as privacy and correctness. The former property implies data confidentiality, namely, nothing leaks from the protocol execution but the computed output. The latter requirement implies that the protocol enforces the integrity of the computations made by the parties, namely, honest parties are not lead to accept a wrong output. Security is proven either in the presence of an honest-but-curious adversary that follows the protocol specification but tries to learn more than allowed from its view of the protocol, or a malicious adversary that can arbitrarily deviate from the protocol specification in order to compromise the security of the other parties in the protocol.

The efficiency of a protocol typically also depends on how many corrupted parties can be tolerated before security breaks down, a quantity known as the threshold, t. With semi-honest security, most protocols either require $t < n/2$ (where n is the number of parties), in which case unconditionally secure protocols [11, 27] based on Shamir secret-sharing can be used, or support any choice of t up to $n-1$, as in computationally secure protocols based on oblivious transfer [39, 40]. Interestingly, within these two ranges, the efficiency of most practical semi-honest protocols does not depend on t. For instance, the GMW [39] protocol (and its many variants) is full-threshold, so supports any $t<n$ corruptions. However, we do not know of any practical protocols with threshold, say, $t=\frac{2}{3} n$, or even $t=n/2+1$, that are more efficient than full-threshold GMW-style protocols. One exception to this is when the number of parties becomes very large, in which case protocols based on committees can be used. In this approach, due to an idea of Bracha [23], first a random committee of size $n' \ll n$ is chosen. Then, every party secret-shares its input to the parties in the committee, who runs a secure computation protocol for $t < n'$ to obtain the result. The committee size $n'$ must be chosen to ensure (with high probability) that not the whole committee is corrupted, so clearly a lower threshold t allows for smaller committees, giving significant efficiency savings. However, this technique is only really useful when n is very large, at least in the hundreds or thousands.

In this paper, we investigate designing MPC protocols where an arbitrary threshold for the number of corrupted parties can be chosen, which are practical both when n is very large, and also for small to medium sizes of n. Specifically, we ask the question:

Can we design concretely efficient MPC protocols where the performance improves gracefully as the number of honest parties increases?

Note that the performance of an MPC protocol can be measured both in terms of communication overhead and computational overhead. Using fully homomorphic encryption [37], it is possible to achieve very low communication overhead that is independent of the circuit size even in the malicious setting [6], but for reasonably complex functions FHE is impractical due to very high computational costs. On the other hand, practical MPC protocols typically communicate for every AND gate in the circuit, and use oblivious transfer (OT) to carry out the computation. Fast OT extension techniques allow a large number of secret-shared bit multiplications¹ to be performed using only symmetric primitives and an amortized communication complexity of $O(\kappa )$ [46] or $O(\kappa /\log {\kappa })$ [31, 49] bits, where $\kappa$ is a computational security parameter. This leads to an overall communication complexity which grows with $O(n^2\kappa /\log {\kappa })$ bits per AND gate for GMW-style protocols based on secret-sharing, and $O(n^2\kappa )$ in those based on garbled circuits [14, 20, 73].

1.1 Short Keys for Secure Computation

Our main idea towards achieving the above goal is to build a secure multi-party protocol with h honest parties, by distributing secret key material so that each party only holds a small part of the key. Instead of basing security on secret keys held by each party individually, we then base security on the concatenation of all honest parties’ keys.

As a toy example, consider the following simple distributed encryption of a message m under n keys:

$$\begin{aligned} {\mathsf {E}}_k(m) = \bigoplus _{i=1}^n {\mathsf {H}}(i, k_i) \oplus m \end{aligned}$$

where ${\mathsf {H}}$ is a suitable hash function and each key $k_i \in \{0,1\}^\ell$ belongs to party $P_i$. In the full-threshold setting with up to $n-1$ corruptions, to hide the message we need each party’s key to be of length $\ell =128$ to ensure 128-bit computational security. However, if only $t < n-1$ parties are corrupted, it seems that, intuitively, an adversary needs to guess all $h := n-t$ honest parties’ keys to recover the message, and potentially each key $k_i$ can be much less than 128 bits long when h is large enough. This is because the “obvious” way to try to guess m would be to brute force all h keys until decrypting “successfully”.

In fact, recovering m when there are h unknown keys corresponds to solving an instance of the regular syndrome decoding (RSD) problem [4], which is related to the well-known learning parity with noise (LPN) problem, and believed to be hard for suitable choices of parameters.

1.2 Our Contribution

In this work, we use the above idea of short secret keys to design new MPC protocols in both the constant round and non-constant round settings, which improve in efficiency as the number of honest parties increases. We consider security against a static, honest-but-curious adversary. Our contribution is captured by the following:

GMW-style MPC with short keys (Sect. 4). We present a GMW-style MPC protocol for binary circuits, where multiplications are done with OT extension using short symmetric keys. This reduces the communication complexity of OT extension-based GMW from $O(n^2 \kappa /\log \kappa )$ [49] to $O(nt\ell )$, where the key length $\ell$ decreases as the number of honest parties, $h=n-t$, increases. When h is large enough ($h = \varOmega (\kappa )$), we can even have $\ell$ as small as 1. To construct this protocol, we first analyse the security of the IKNP OT extension protocol [46] when using short keys and formalise the leakage obtained by a corrupt receiver in this case. We then show how to use this version of “leaky OT” to generate multiplication triples using a modified version of the GMW method, where pairs of parties use OT to multiply their shares of random values. We also optimize our protocol by reducing the number of communication channels using two different-sized committees, improving upon the standard approach of choosing one committee to do all the work.

Multi-party garbled circuits with short keys (Sect. 5). Our second contribution is the design of a constant round, BMR-style [20] protocol based on garbled circuits with short keys. Our offline phase uses the multiplication protocol from the previous result in order to generate the garbled circuit, using secret-shared bit and bit/string multiplications as done in previous works [14, 45], with the exception that the keys are shorter. In the online phase, we then use the LPN-style assumption to show that the combination of all honest parties’ $\ell$-bit keys suffices to obtain a secure garbling protocol. This allows us to save on the key length as a function of the number of honest parties.

As well as reducing communication with a smaller garbled circuit, we also reduce computation when evaluating the circuit, since each garbled gate can be evaluated with only $O(n^2 \ell /\kappa )$ block cipher calls (assuming the ideal cipher model), instead of $O(n^2)$ when using $\kappa$-bit keys. For this protocol, $\ell$ can be as small as 8 when n is large enough, giving a significant saving over 128-bit keys used previously.

1.2.1 Concrete Efficiency Improvements

The efficiency of our protocols depends on the total number of parties, n, and the number of honest parties, h, so there is a large range of parameters to explore when comparing with other works. We discuss this in more detail in Sect. 6. Our protocols seem most significant in the dishonest majority setting, since when there is an honest majority there are unconditionally secure protocols with $O(n\log {n})$ communication overhead and reasonable computational complexity, e.g. [33], whilst our protocols have $\varOmega (nt)$ communication overhead.

Our GMW-style protocol starts to improve upon previous protocols already when we reach $n=10$ parties and $t=6$ corruptions: here, our triple generation method requires less than half the communication cost of the fastest triple generation protocol based on OT extension [31] tolerating up to $n-1$ corruptions. When the number of honest parties is large enough, we can use 1-bit keys, giving a 25-fold reduction in communication over previous protocols when $n=400$ and $t=280$. In some settings, we rely on yet another improvement that optimizes our triple generation protocol using Vandermonde matrices. As shown in Sect. 6, this approach is particularly convenient when the number of honest parties is small and allows us to avoid relying on the RSD assumption. Finally, we describe a simple threshold-t variant of GMW-style protocols, which our protocol still outperforms by 1.1x and 13x, respectively, in these two scenarios.

For our constant round protocol, with $n=20,t=10$ we can use 32-bit keys, so the size of each garbled AND gate is 1/4 the size of [14]. As n increases, the improvements become greater, with a 16-fold reduction in garbled AND gate size for $n=400,t=280$. We also reduce the communication cost of creating the garbled circuit. Here, the improvement starts at around 50 parties and goes up to a 7 times reduction in communication when $n=400,t=280$. Note that our protocol does incur a slight additional overhead, since we need to use extra “splitter gates”, but this cost is relatively small.

To demonstrate the practicality of our approach, we also present an implementation of the online evaluation phase of our constant-round protocol for key lengths ranging between 1 and 4 bytes, and with an overall number of parties ranging from 15 to 1000; more details can be found in Sect. 6.

1.2.2 Applications

Our techniques seem most useful for large-scale MPC with around 70% corruptions, where we obtain the greatest concrete efficiency improvements. An important motivation for this setting is privacy-preserving statistical analysis of data collected from a large network with potentially thousands of nodes. In scenarios where the nodes are not always online and connected, our protocols can also be used with the “random committee” approach discussed earlier, so only a small subset of, say, a hundred nodes need to be online and interacting during the protocol.

An interesting example is safely measuring the Tor network [32] which is among the most popular tools for digital privacy, consisting of more than 6000 relays that can opt-in for providing statistics about the use of the network. Nowadays, due to privacy risks, the statistics collected over Tor are generally poor: There is a reduced list of computed functions and only a minority of the relays provide data, which has to be obfuscated before publishing [32]. Hence, the statistics provide an incomplete picture which is affected by a noise that scales with the number of relays. Running MPC in this setting would enable for more complex, accurate and private data processing, for example through anomaly detection and more sophisticated censorship detection. Moreover, our protocols are particularly well-suited to this setting since all relays in the network must be connected to one another already, by design.

Another possible application is for securely computing the interdomain routing within the Border Gateway Protocol (BGP), which is performed at a large scale of thousands of nodes. A recent solution in the dishonest majority setting [2] centralizes BGP so that two parties run this computation for all Autonomous Systems. Our techniques allow scaling to a large number of systems computing the interdomain routing themselves using MPC, hence further reducing the trust requirements.

1.2.3 Decisional Regular Syndrome Decoding Problem

The security of our protocols relies on the Decisional Regular Syndrome Decoding (DRSD) problem, which, given a random binary matrix ${\mathbf {H}}$, is to distinguish between the syndrome obtained by multiplying ${\mathbf {H}}$ with an error vector ${\varvec{e}}= ({\varvec{e}}_1 \Vert \cdots \Vert {\varvec{e}}_h)$ where each ${\varvec{e}}_i \in \{0,1\}^{2^\ell }$ has Hamming weight one, and the uniform distribution. This can equivalently be described as distinguishing $\bigoplus _{i=1}^h {\mathsf {H}}(i,k_i)$ from the uniform distribution, where ${\mathsf {H}}$ is a random function and each $k_i$ is a random $\ell$-bit key (as in the toy example described earlier).

This problem was introduced in 2003 by Augot, Finiasz and Sendrier [4], who used it for the SHA-3 candidate FSB (Fast Syndrome-Based) hash function. RSD is similar to the (standard) syndrome decoding problem [21, 58], where each component of the error vector is 0 or 1 with some constant probability, and which, in turn, is equivalent to the problem of learning parity with noise (LPN) [10] for a restricted number of samples. Like LPN, the RSD problem is NP-hard in general, and the best-known attacks on RSD do not perform much better than those against LPN. We also show that RSD admits a simple search-to-decision reduction, similar to a previous reduction for LPN [5].

We remark that in some of our settings, the problem is unconditionally hard even for $\ell =1$, which means for certain parameter choices in our GMW-based protocol we can use much smaller keys without introducing any additional assumptions. This introduces a significant saving in our triple generation protocol.

Overall, our approach demonstrates a new application of LPN-type assumptions to efficient MPC without introducing asymmetric operations. Our techniques may also be useful in other distributed applications where only a small fraction of nodes are honest.

1.2.4 Additional Related Work

Another work which applies a similar assumption to secure computation is that of Applebaum [8], who built garbled circuits with the free-XOR technique in the standard model under the LPN assumption. Conceptually, our work differs from Applebaum’s since our focus is to improve the efficiency of multi-party protocols with fewer corruptions, whereas in [8], LPN is used in a more modular way in order to achieve encryption with stronger properties and under a more standard assumption.

In a recent work [62], Nielsen and Ranellucci designed a protocol in the dishonest majority setting with malicious, adaptive security in the presence of $t< cn$ corruption for $c\in [0,1)$. Their protocol is aimed to work with a large number of parties and uses committees to obtain a protocol with poly-logarithmic overhead. This protocol introduces high constants and is not useful for practical applications.

Finally, in work concurrent to the proceedings version of this work [22], Ben-Efraim and Omri also explore how to optimize garbled circuits in the presence of non-full-threshold adversaries. By using deterministic committees, they achieve AND gates of size $4(t+1)\kappa$, where $\kappa$ is the computational security parameter. By using the same technique, our work achieves a size of $4(t+h)\ell$, where h is the minimum number of honest parties in the committee and the parameter $\ell \ll \kappa$ depends on h according to the Decisional Regular Syndrome Decoding problem. The rest of their results apply only to the honest majority setting.

1.2.5 History and Subsequent Work

An earlier version of this work was published at Crypto 2018 [43]. The current version extends this with complete security proofs, more detailed complexity and security analysis, and an additional optimization. In particular, Sect. 4.3 describes a new variant of our GMW protocol which leads to lower communication in several settings and can also remove reliance on the DRSD assumption for a wider range of parameters.

In follow-up work, we extended these techniques to the malicious setting [42]. There, we show how to improve the communication and computation complexity of protocols from the ‘TinyOT’ family [35, 45, 61, 72]. Furthermore, such techniques can be combined with the BMR protocol of [45] to obtain more efficient constant-round MPC.

1.3 Technical Overview

In what follows, we explain the technical side of our results in more detail.

1.3.1 Leaky Oblivious Transfer (OT)

We first present a two-party secret-shared bit multiplication protocol, based on the IKNP OT extension protocol [46] which we adapt to use short keys. Recall that the IKNP protocol can be broken into two stages: first, the parties create a batch of correlated OTs, where the sender’s messages in each OT are strings of the form $q_i,q_i\oplus \varDelta$ for some fixed $\varDelta \in \{0,1\}^\kappa$. Secondly, the parties break the correlation by hashing each string individually; if the hash function ${\mathsf {H}}$ has one-bit output, this produces OTs on random bits, which can be directly used for secret-shared multiplication. For security, ${\mathsf {H}}$ must satisfy a correlation robustness property, namely, if $\varDelta$ is a random, secret string, then ${\mathsf {H}}(q_i\oplus \varDelta )$ is indistinguishable from random to the receiver, even given $q_i$. Note that this last step is completely local, while the first step requires $\kappa$ bits of communication per OT when using optimized IKNP variants [7, 49] which we build upon.

In our protocol, we modify the first step by choosing the sender’s secret $\varDelta$ to be an $\ell$-bit string, for some $\ell < \kappa$, instead of $\kappa$ bits. This reduces the communication cost of this step down to $\approx \ell$ bits per OT. However, the protocol now leaks some information on the sender’s secret $\varDelta \leftarrow \{0,1\}^\ell$ to the receiver, which also reveals information about the sender’s inputs. Roughly speaking, the leakage is of the form ${\mathsf {H}}(i,\varDelta ) + x_i$, where $x_i \in \{0,1\}$ is an input of the sender and ${\mathsf {H}}$ is a hash function with 1-bit output. Clearly, when $\ell$ is short, this is not secure to use on its own, since all of the receiver’s inputs only have $\ell$ bits of min-entropy (based on the choice of $\varDelta$).

1.3.2 MPC from Leaky OT

We then show how to apply this leaky two-party protocol to the multi-party setting, whilst preventing any leakage on the parties shares. The main observation is that, when using additive secret-sharing, we only need to ensure that the sum of all honest parties’ shares is unpredictable; if the adversary learns just a few shares, they can easily be rerandomized by adding pseudorandom shares of zero, which can be done non-interactively using a PRF. However, we still have a problem, which is that in the standard GMW approach, each party $P_i$ uses OT to multiply their share $x^i$ with every other party $P_j$’s share $y^j$. Now, there is leakage on the same share $x^i$ from each of the OT instances between all other parties, which seems much harder to prevent than leakage from just a single OT instance.

To work around this problem, we have the parties add shares of zero to their $x^i$ inputs before multiplying them. So, every pair $(P_i,P_j)$ will use leaky OT to multiply $x^i \oplus s^{i,j}$ with $y^j$, where $s^{i,j}$ is a random share of zero satisfying $\bigoplus _{i=1}^n s^{i,j} = 0$. This preserves correctness of the protocol, because the parties end up computing an additive sharing of:

$$\begin{aligned} \bigoplus _{i=1}^n \bigoplus _{j=1}^n (x^i \oplus s^{i,j}) y^j = \bigoplus _{j=1}^n y^j \bigoplus _{i=1}^n (x^i \oplus s^{i,j}) = xy. \end{aligned}$$

This also effectively removes leakage on the individual shares, so we only need to be concerned with the sum of the leakage on all honest parties’ shares, and this turns out to be of the form: $\bigoplus _{i=1}^n ({\mathsf {H}}(i, \varDelta _i) + x^i)$ which is pseudorandom under the decisional regular syndrome decoding assumption.

We realize our protocol using a hash function with a polynomial-sized domain, so that is can be implemented using a CRS which simply outputs a random lookup-table. This means that, unlike when using the IKNP protocol, we do not need to rely on a random oracle or a correlation robustness assumption (which is also defined using an oracle). Furthermore, in some cases we can avoid reliance on decisional regular syndrome decoding, by choosing parameters such that the problem is information-theoretically secure. We present two variants of this approach, where the first requires a large number of honest parties but allows $\ell =1$, while the second requires $\ell \ge \log n$, and uses Vandermonde matrices to extract randomness from a smaller number of honest parties.

When the number of parties is large enough, we can also improve our triple generation protocol using random committees. In this case, the amortized communication cost is $\le n_h n_1(\ell + \ell \kappa /r + 1)$ bits per multiplication where we need to choose two committees of sizes $n_h$ and $n_1$ which have at least h and 1 honest parties, respectively.

1.3.3 Garbled Circuits with Short Keys

We next revisit the multi-party garbled circuits technique by Beaver, Micali and Rogaway, known as BMR, that extends the classic Yao garbling [73] to an arbitrary number of parties, where essentially all the parties jointly garble using one set of keys each. This method was recently improved in a sequence of works [14, 45, 54, 55], where the two latter works further support the free-XOR property.

Our garbling method uses an expansion function ${\mathsf {H}}: [n] \times \{0,1\}\times \{0,1\}^{\ell } \rightarrow \{0,1\}^{n\ell +1}$, where $\ell$ is the length of each parties’ keys used as wire labels in the garbled circuit. To garble a gate, the hash values of the input wire keys $k^i_{u,b}$ and $k^i_{v,b}$ are XORed over i and used to mask the output wire keys.

Specifically, for an AND gate g with input wires u, v and output wire w, the 4 garbled rows ${\tilde{g}}_{a,b}$, for each $(a,b) \in \{0,1\}^2$, are computed as:

$$\begin{aligned} {\tilde{g}}_{a,b} = \left( \bigoplus _{i=1}^n {\mathsf {H}}(i,b,k^i_{u,a}) \oplus {\mathsf {H}}(i,a,k^i_{v,b}) \right) \oplus \left( c, k^1_{w,c}, \ldots , k^n_{w,c}\right) . \end{aligned}$$

Security then relies on the $\mathsf {DRSD}$ assumption, which implies that the sum of h hash values on short keys is pseudorandom, which suffices to construct a secure garbling method with h honest parties.

Using this assumption instead of a PRF (as in recent works) comes with difficulties, as we can no longer garble gates with arbitrary fan-out, or use the free-XOR technique, without degrading the $\mathsf {DRSD}$ parameters. To allow for arbitrary fan-out circuits with our protocol, we use splitter gates, which take as input one wire w and provide two outputs wires u, v, representing the same wire value. Splitter gates were previously introduced as a fix for an error in the original BMR paper in [69]. We stress that transforming a general circuit description into a circuit where XOR and AND gates are fan-out-1 requires adding at most a single splitter gate per AND or XOR gate.

The restriction to fan-out-1 gates and the use of splitter gates allow us to garble XOR gates ‘almost for free’ in BMR, more specifically at the cost of at most one splitter gate per arbitrary-fan-in XOR gate. Our technique is based on FlexOR [50], by setting each XOR gate to use a unique offset. As a side effect of using different offsets, we do not need to rely on circular security assumptions or correlation-robust hash functions. Furthermore, the overhead of splitter gates is very low, since garbling a splitter gate does not use the underlying MPC protocol: shares of the garbled gate can be generated non-interactively.

2 Preliminaries

We denote the security parameter by $\kappa$. We say that a function $\mu :{\mathbb {N}}\rightarrow {\mathbb {N}}$ is negligible if for every positive polynomial $p(\cdot )$ and all sufficiently large $\kappa$ it holds that $\mu (\kappa )<\frac{1}{p(\kappa )}$. The function $\mu$ is noticeable (or non-negligible) if there exists a positive polynomial $p(\cdot )$ such that for all sufficiently large $\kappa$ it holds that $\mu (\kappa ) \ge \frac{1}{p(\kappa )}$. We use the abbreviation PPT to denote probabilistic polynomial-time. We further denote by $a \leftarrow A$ the uniform sampling of a from a set A, and by [d] the set of elements $\{1,\ldots ,d\}$. We often view bit-strings in $\{0,1\}^k$ as vectors in ${\mathbb {F}}_2^k$, depending on the context, and denote exclusive-or by “$\oplus$” or “$+$”. If $a, b \in {\mathbb {F}}_2$, then $a \cdot b$ denotes multiplication (or AND), and if ${\varvec{c}}\in {\mathbb {F}}_2^\kappa$, then $a \cdot {\varvec{c}}\in {\mathbb {F}}_2^\kappa$ denotes the product of a with every component of ${\varvec{c}}$.

We first specify the definition of computational indistinguishability.

Definition 2.1

Let $X=\{X(a,\kappa )\}_{a\in \{0,1\}^*,\kappa \in {\mathbb {N}}}$ and $Y=\{Y(a,\kappa )\}_{a\in \{0,1\}^*,\kappa \in {\mathbb {N}}}$ be two distribution ensembles. We say that X and Y are computationally indistinguishable, denoted $X{\mathop {\approx }\limits ^{\mathrm{c}}}Y$, if for every PPT machine $\mathcal{D}$ and every $a\in \{0,1\}^*$, there exists a negligible function $\mathsf {negl}$ such that:

$$\begin{aligned} \big |\mathrm{Pr}\left[ \mathcal{D}(X(a,\kappa ),a,1^\kappa )=1\right] -\mathrm{Pr}\left[ \mathcal{D}(Y(a,\kappa ),a,1^\kappa )=1\right] \big | <\mathsf {negl}(\kappa ). \end{aligned}$$

2.1 Security and Communication Models

We prove security of our protocols in the universal composability (UC) framework [24]. See Appendix A for a summary of this. We assume all parties are connected via secure, authenticated point-to-point channels, which is the default method of communication in our protocols. The adversary model we consider is a static, honest-but-curious adversary who corrupts a subset $A \subset [n]$ of parties at the beginning of the protocol. We denote by ${\bar{A}}$ the subset of honest parties and define $h = |\bar{A} | = n - t$.

Fig. 1

Random zero sharing functionality

2.2 Random Zero-Sharing

Our protocols require the parties to generate random additive sharings of zero, as in the ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}$ functionality in Fig. 1. This can be done efficiently using a PRF F, with interaction only during a setup phase, as in [3]. We do this by asking each party $P_i$ to send a random PRF key $k_{i,j}$ to every other party $P_j$. Next, $P_i$ defines its share by $\bigoplus _{j\ne i} (F_{k_{i,j}}(\tau )\oplus F_{k_{j,i}}(\tau ))$ where $\tau$ is an index that identifies the generated share. It is simple to verify that all the shares XOR to zero since each PRF value is used exactly twice. Moreover, privacy holds in the presence of any subset of $n-2$ corrupted parties because the respective values $F_{k_{l,l'}}$ and $F_{k_{l',l}}$ of honest parties $P_l$ and $P_{l'}$ are pseudorandom, which implies that their zero shares are also pseudorandom. Finally, the communication complexity of the setup phase amounts to sending $O(n^2)$ PRF keys, whilst creating the shares requires $2(n-1)$ PRF evaluations to produce $\kappa$ bits.

2.3 IKNP OT Extension

Here, we shortly recall the passively secure OT extension protocol presented by Ishai, Kilian, Nissim and Petrank in 2003 [46], including some optimations by Asharov, Lindell, Schneider and Zohner [7]. This protocol allows to generate $r=\mathsf {poly}(\kappa )$ random oblivious transfers from $\kappa$ oblivious transfers using only cheap symmetric cryptographic primitives. At a high level, the protocol can be divided into three phases. The private inputs of the receiver $P_B$ are the choice bits ${\varvec{x}}=(x_1,\ldots ,x_r)$.

In the first step, called “seed OT phase”, the sender, $P_A$, and the receiver, $P_B$, acting with their roles reversed, perform $\kappa$ OTs on random strings of length $\kappa$. $P_B$ obtains random $({\varvec{s}}_0^i,{\varvec{s}}_1^i) \in \{0,1\}^\kappa$ and $P_A$ obtains $({\varvec{s}}^i_{\varDelta _i})$, where $\varDelta =(\varDelta _1,\ldots \varDelta _\kappa ) \in \{0,1\}^\kappa$ is the choice vector used by $P_A$ as input in the OTs.

Then, they locally expand these strings through a pseudorandom generator, so that $P_B$ obtains $({\varvec{t}}^i_0,{\varvec{t}}^i_1) \in \{0,1\}^r, i \in [\kappa ]$, and $P_A$ obtains $({\varvec{t}}_{\varDelta _i}^i)$. In the second step, $P_B$ introduces a correlation by sending the values

$$\begin{aligned} {\varvec{u}}^i= {\varvec{t}}_i^0 \oplus {\varvec{t}}_1^1 \oplus {\varvec{x}}, \end{aligned}$$

where ${\varvec{x}}=(x_1,\ldots ,x_r)$ are the receiver’s r choice bits. In this way, the sender $P_A$ can compute

$$\begin{aligned} {\varvec{q}}^i&= \, {\varvec{t}}_{\varDelta _i}^i \oplus \varDelta _i \cdot {\varvec{u}}^i \\&= {\varvec{t}}_0^i \oplus \varDelta _i \cdot {\varvec{x}}= {\varvec{t}}^i \oplus \varDelta \cdot {\varvec{x}}, \end{aligned}$$

and can define the matrix $Q \in \{0,1\}^{\kappa \times r}$ having the vectors ${\varvec{q}}^i$ as rows. Similarly, $P_B$ can define the matrix $T \in \{0,1\}^{\kappa \times r}$ with rows ${\varvec{t}}^i_0$. By taking the columns of these two matrices, $P_A$ and $P_B$, respectively, obtain ${\varvec{q}}_j, {\varvec{t}}_j \in \{0,1\}^\kappa , j \in [r]$ such that:

$$\begin{aligned} {\varvec{t}}_j \oplus {\varvec{q}}_j = \varDelta \cdot x_j. \end{aligned}$$

Finally, the last step permits to obtain r OTs on random strings, by breaking the correlation $\varDelta$. To do this, the sender computes ${\mathsf {H}}({\varvec{q}}_j)$ and ${\mathsf {H}}({\varvec{q}}_j \oplus \varDelta )$ and the receiver computes ${\mathsf {H}}({\varvec{t}}_j)$, where ${\mathsf {H}}$ is a correlation robust hash function.

Note that this protocol only requires interaction to generate the seed OTs and during the second phase when the receiver sends the values ${\varvec{u}}^i$. Note that in this second interaction the receiver must communicate $\kappa$ bits for each of the r OTs to be produced.

3 Syndrome Decoding Problem

We now describe the Regular Syndrome Decoding (RSD) problem [4] and some of its properties.

Definition 3.1

A vector ${\varvec{e}}\in {\mathbb {F}}_2^m$ is (m, h)-regular if ${\varvec{e}}= ({\varvec{e}}_1 \Vert \cdots \Vert {\varvec{e}}_h)$ where each ${\varvec{e}}_i \in \{0,1\}^{m/h}$ has Hamming weight one. We denote by $R_{m,h}$ the set of all the (m, h)-regular vectors in ${\mathbb {F}}_2^m$.

Definition 3.2

(Regular Syndrome Decoding (RSD)) Let $r, h,\ell \in {\mathbb {N}}$ with $m = h \cdot 2^\ell$, ${\mathbf {H}}\leftarrow {\mathbb {F}}_2^{r \times m}$ and ${\varvec{e}}\leftarrow R_{m,h}$. Given $({\mathbf {H}}, {\mathbf {H}}{\varvec{e}})$, the $\mathsf {RSD}_{r,h,\ell }$ problem is to recover ${\varvec{e}}$ with noticeable probability.

The decisional version of the problem, given below, is to distinguish the syndrome ${\mathbf {H}}{\varvec{e}}$ from uniform.

Definition 3.3

(Decisional Regular Syndrome Decoding (DRSD)) Let ${\mathbf {H}}\leftarrow {\mathbb {F}}_2^{r \times m}$ and ${\varvec{e}}\leftarrow R_{m,h}$, and let $U_r$ be the uniform distribution on r bits. The $\mathsf {DRSD}_{r,h,\ell }$ problem is to distinguish between $({\mathbf {H}}, {\mathbf {H}}{\varvec{e}})$ and $({\mathbf {H}}, U_r)$ with noticeable advantage.

3.1 Hash Function Formulation

The $\mathsf {DRSD}$ problem can be equivalently described as distinguishing from uniform $\bigoplus _{i=1}^h {\mathsf {H}}(i,k_i)$ where ${\mathsf {H}}: [h] \times \{0,1\}^\ell \rightarrow \{0,1\}^r$ is a random hash function, and each $k_i \leftarrow \{0,1\}^\ell$. With this formulation, it is easier to see how the $\mathsf {DRSD}$ problem arises when using our protocols with short keys, since this appears when summing up a hash function applied to h honest parties’ secret keys.

To see the equivalence, we can define a matrix ${\mathbf {H}}\in {\mathbb {F}}_2^{r \times h\cdot 2^\ell }$, where for each $i \in \{0,\ldots ,h-1\}$ and $k \in [2^\ell ]$, column $i \cdot 2^\ell + k$ of ${\mathbf {H}}$ contains ${\mathsf {H}}(i,k)$. Then, multiplying ${\mathbf {H}}$ with a random (m, h)-regular vector ${\varvec{e}}$ is equivalent to taking the sum of ${\mathsf {H}}$ over h random inputs, as above.

3.2 Statistical Hardness of DRSD

We next observe that for certain parameters where the output size of ${\mathbf {H}}$ is sufficiently smaller than the min-entropy of the error vector ${\varvec{e}}$, the distribution in the decisional problem is statistically close to uniform.

Lemma 3.4

If $\ell = 1$ and $h \ge r + s$, then $\mathsf {DRSD}_{r,h,\ell }$ is statistically hard, with distinguishing probability $2^{-s}$.

Proof

Suppose $\ell =1$ and $h \ge r + s$, so $m=2h$. For a vector ${\varvec{e}}= ({\varvec{e}}_1\Vert \cdots \Vert {\varvec{e}}_h) \in R_{m,h}$, we can write each of the weight-1 vectors ${\varvec{e}}_i \in \{0,1\}^2$ as $(e_i', 1-e_i')$. An $\mathsf {RSD}$ sample ${\mathbf {H}},{\varvec{y}}= {\mathbf {H}}{\varvec{e}}$ therefore defines a system of r linear equations in the h variables $\{e_i'\}_i$, and it can be shown that this simplifies to the form ${\varvec{y}}= {\mathbf {H}}'{\varvec{e}}' + {\varvec{c}}$, where ${\varvec{e}}' = (e_1',\ldots ,e_h')$, by defining the j-th column of ${\mathbf {H}}' \in {\mathbb {F}}_2^{r \times h}$ to be the sum of columns $2j-1$ and 2j from ${\mathbf {H}}$, and ${\varvec{c}}$ to be the sum of all even-indexed columns in ${\mathbf {H}}$. Note that ${\mathbf {H}}'$ is uniformly random because ${\mathbf {H}}$ is, and it is easy to show (e.g. [63, Lemma 1]) that the probability that ${\mathbf {H}}' \leftarrow {\mathbb {F}}_2^{r \times h}$ is not full rank is no more than $2^{-s}$ when $h \ge r + s$. Assuming that ${\mathbf {H}}'$ has full rank and $h \ge r$, ${\varvec{y}}= {\mathbf {H}}'{\varvec{e}}' + {\varvec{c}}$ must be uniformly random because ${\varvec{e}}'$ is. $\square$

For the general case of $\ell$-bit keys, we use the following form of the leftover hash lemma.

Lemma 3.5

(Leftover Hash Lemma [47]) Let ${\mathbf {H}}\leftarrow {\mathbb {F}}_2^{r \times m}$ and ${\varvec{e}}\leftarrow \chi$, where $\chi$ is a distribution over ${\mathbb {F}}_2^m$ with min-entropy at least k. If $r \le k - 2s$, then

$$\begin{aligned} \varDelta _{SD}(({\mathbf {H}}, {\mathbf {H}}{\varvec{e}}), ({\mathbf {H}}, {\varvec{u}})) \le 2^{-s} \end{aligned}$$

where ${\varvec{u}}\leftarrow {\mathbb {F}}_2^r$ and $\varDelta _{SD}$ is the statistical distance.

Note that if ${\varvec{e}}\leftarrow R_{m,h}$, then we have $H_\infty ({\varvec{e}}) = h \ell$. Applying Lemma 3.5 with $k=h\ell$, we obtain the following.

Corollary 3.6

If $h \ge (r + 2s)/\ell$, then $\mathsf {DRSD}_{r,h,\ell }$ is statistically hard, with distinguishing probability $2^{-s}$.

3.3 Search-to-Decision Reduction

For all parameter choices of $\mathsf {DRSD}$, there is a simple reduction to the search version of the regular syndrome decoding problem with the same parameters.

Lemma 3.7

Any efficient distinguisher for the $\mathsf {DRSD}_{r,h,\ell }$ problem can be used to efficiently solve $\mathsf {RSD}_{r,h,\ell }$.

The proof (inspired by a similar result for LPN [5]) is a simplified version of previous reductions for syndrome decoding.

We first recall the Goldreich–Levin hardcore-bit theorem.

Theorem 3.8

[38] Let f be a one-way function. Then, given (r, f(x)) for uniformly random r and x, the inner product $\langle x,r \rangle$ over ${\mathbb {F}}_2$ is unpredictable.

Proof

(of Lemma 3.7) Suppose ${\mathcal {A}}$ distinguishes between $({\mathbf {H}}, {\mathbf {H}}{\varvec{e}})$ and $({\mathbf {H}}, U_r)$ with noticeable advantage $\delta$. We construct an adversary ${\mathcal {A}}'$ that breaks the Goldreich–Levin hardcore bit of $f({\varvec{e}}) = ({\mathbf {H}}, {\mathbf {H}}{\varvec{e}})$ by guessing the inner product $\langle {\varvec{e}},{\varvec{s}} \rangle$ for some vector ${\varvec{s}}\in {\mathbb {F}}_2^m$. On input $({\mathbf {H}}, {\varvec{y}}={\mathbf {H}}{\varvec{e}}, {\varvec{s}})$, algorithm ${\mathcal {A}}'$ proceeds as follows:

• 1. Sample ${\varvec{t}}\leftarrow \{0,1\}^r$

• 2. Compute ${\mathbf {H}}' = {\mathbf {H}}- {\varvec{t}}\cdot {\varvec{s}}^\top$

• 3. Run ${\mathcal {A}}$ on input $({\mathbf {H}}', {\varvec{y}})$

• 4. Output the same as ${\mathcal {A}}$

First, notice that because ${\mathbf {H}}$ is uniformly random, ${\mathbf {H}}'$ is also. Secondly, ${\varvec{y}}= {\mathbf {H}}{\varvec{e}}= ({\mathbf {H}}' + {\varvec{t}}\cdot {\varvec{s}}^\top ) {\varvec{e}}= {\mathbf {H}}' {\varvec{e}}+ {\varvec{t}}\cdot \langle {\varvec{s}},{\varvec{e}} \rangle$. So, if $\langle {\varvec{s}},{\varvec{e}} \rangle =0$, then the input to ${\mathcal {A}}$ is a correct sample $({\mathbf {H}}', {\mathbf {H}}' {\varvec{e}})$, whereas if $\langle {\varvec{s}},{\varvec{e}} \rangle = 1$, then the input is uniformly random. Therefore, it holds that:

$$\begin{aligned} \begin{aligned} \Pr [{\mathcal {A}}'({\mathbf {H}}, {\mathbf {H}}{\varvec{e}}, {\varvec{r}}) = \langle {\varvec{e}},{\varvec{r}} \rangle ]&= \Pr [{\mathcal {A}}'({\mathbf {H}}, {\mathbf {H}}{\varvec{e}}, {\varvec{r}}) = 0 | \langle {\varvec{e}},{\varvec{r}} \rangle =0] \cdot \Pr [\langle {\varvec{e}},{\varvec{r}} \rangle =0] \\&\quad + \Pr [{\mathcal {A}}'({\mathbf {H}}, {\mathbf {H}}{\varvec{e}}, {\varvec{r}}) = 1 | \langle {\varvec{e}},{\varvec{r}} \rangle =1] \cdot \Pr [\langle {\varvec{e}},{\varvec{r}} \rangle =1] \\&= \frac{1}{2} \cdot (\Pr [{\mathcal {A}}({\mathbf {H}}', {\mathbf {H}}'{\varvec{e}})=0] + (1 - \Pr [{\mathcal {A}}({\mathbf {H}}', U_r)=0])) \\&\ge \frac{1}{2} + \frac{\delta }{2}. \end{aligned} \end{aligned}$$

$\square$

3.4 Multi-Secret RSD

We now consider a variant of DRSD with multiple sets of secrets, where the matrix ${\mathbf {H}}$ is fixed for each sample. We then reduce this to the standard DRSD problem with the same parameters, with a security loss of the number of secrets.

Definition 3.9

(Multi-Secret DRSD) Let ${\mathbf {H}}\leftarrow {\mathbb {F}}_2^{r \times m}$ and ${\varvec{e}}_1, \ldots , {\varvec{e}}_q \leftarrow R_{m,h}$ (as in Definition 3.2). The q-$\mathsf {DRSD}_{r,h,\ell }$ problem is to distinguish between a tuple $({\mathbf {H}}, {\mathbf {H}}{\varvec{e}}_1, \ldots , {\mathbf {H}}{\varvec{e}}_q)$ and $({\mathbf {H}}, U_r^q)$ with noticeable advantage.

Lemma 3.10

q-$\mathsf {DRSD}_{r,h,\ell }$ is reducible to $\mathsf {DRSD}_{r,h,\ell }$, where the reduction loses a tightness factor of q.

Proof

The proof is based on a standard hybrid argument with a sequence of $q+1$ hybrid distributions, where each pair of neighbouring hybrids is indistinguishable based on $\mathsf {DRSD}$.

The first hybrid, $H_0$, outputs $({\mathbf {H}}, u_1, \ldots , u_q)$, where ${\mathbf {H}}\leftarrow {\mathbb {F}}_2^{r \times m}$ and $u_i \leftarrow \{0,1\}^r$, which is exactly the uniform distribution used in q-$\mathsf {DRSD}$. In hybrid $H_i$, for $i = 1, \ldots , q$, we sample regular secrets ${\varvec{e}}_1, \ldots , {\varvec{e}}_i$ and output $({\mathbf {H}}, {\mathbf {H}}{\varvec{e}}_1, \ldots , {\mathbf {H}}{\varvec{e}}_i, u_{i+1},\ldots ,u_q)$. Note that $H_q$ is the same as the real distribution in the q-$\mathsf {DRSD}$ problem. Any adversary ${\mathcal {A}}$ who distinguishes between $H_i$ and $H_{i+1}$ can be used to break $\mathsf {DRSD}_{r,h,\ell }$, as follows. The distinguisher ${\mathcal {D}}$ receives a $\mathsf {DRSD}$ challenge $({\mathbf {H}}, {\varvec{y}})$, then samples ${\varvec{e}}_1, \ldots , {\varvec{e}}_i$ from the error distribution and random strings $u_{i+2}, \ldots , u_q \leftarrow \{0,1\}^r$. It then outputs ${\mathcal {A}}({\mathbf {H}}, {\mathbf {H}}{\varvec{e}}_1, \ldots , {\mathbf {H}}{\varvec{e}}_i, {\varvec{y}}, u_{i+2}, \ldots , u_q)$. The advantage of ${\mathcal {D}}$ against the $\mathsf {DRSD}$ problem is identical to that of ${\mathcal {A}}$. A standard argument then implies that any adversary who distinguishes $H_0$ and $H_q$ with advantage $\delta$ can solve $\mathsf {DRSD}_{r,h,\ell }$ with advantage at least $\delta /q$. $\square$

3.5 Extended Double-Key RSD

In our final variant of RSD—used in the security proof of our BMR-style online phase—we consider multiple sets of secrets and also give the adversary two challenges for each secret which captures the double use of each key in the garbling procedure. This means we cannot preserve the RSD parameters and must reduce to 2-$\mathsf {DRSD}_{2r, h,\ell }$. We also make a conceptual change and specify the problem using a random hash function ${\mathsf {H}}$ with small domain (which can be modelled as a random oracle, or a random lookup table given as a common random string) instead of matrices and vectors. We switch to this notation in order to capture the computation made by the honest parties when garbling a gate.

Definition 3.11

(Extended Double-Key DRSD) The extended double-key decisional-RSD problem states that, for every fixed subset $S \subset [n]$ of size h, it holds that

$$\begin{aligned} \left( {\mathsf {H}}, \bigoplus _{i \in S} {\mathsf {H}}(i,0, k_{i}), \bigoplus _{i \in S} {\mathsf {H}}(i,0, k_{i}'), \bigoplus _{i \in S} {\mathsf {H}}(i,1, k_{i}), \bigoplus _{i \in S} {\mathsf {H}}(i,1, k_{i}')\right) \quad {\mathop {\approx }\limits ^{\mathrm{c}}}\quad \left( {\mathsf {H}},U_{4r}\right) , \end{aligned}$$

where ${\mathsf {H}}: [n] \times \{0,1\}\times \{0,1\}^\ell \rightarrow \{0,1\}^r$ is a randomly sampled function, and $k_{i}, k_{i}' \leftarrow \{0,1\}^\ell$ for $i \in S$.

Lemma 3.12

The extended double-key decisional-RSD problem with parameters $(r,h,\ell )$ is reducible to 2-$\mathsf {DRSD}(2r,h,\ell )$.

Proof

Suppose there exists a set $S \subset [n]$ for which an adversary ${\mathcal {A}}$ distinguishes the above two distributions with noticeable advantage. We use ${\mathcal {A}}$ to construct a distinguisher ${\mathcal {D}}$ for the 2-$\mathsf {DRSD}(2r,h,\ell )$ problem. ${\mathcal {D}}$ receives a challenge $({\mathbf {H}}, {\varvec{y}}_0,{\varvec{y}}_1)$, where ${\mathbf {H}}\in {\mathbb {F}}_2^{2r \times m}$, $m=h\cdot 2^\ell$ and ${\varvec{y}}_0,{\varvec{y}}_1 \in {\mathbb {F}}_2^{2r}$. Write ${\mathbf {H}}= \left( {\begin{matrix}{\mathbf {H}}_0 \\ {\mathbf {H}}_1\end{matrix}}\right)$ and ${\varvec{y}}_j = \left( {\begin{matrix}{\varvec{z}}_j \\ {\varvec{z}}_j'\end{matrix}}\right)$. Define the hash function ${\mathsf {H}}: [n] \times \{0,1\}\times \{0,1\}^\ell \rightarrow \{0,1\}^r$ so that ${\mathsf {H}}(i,b,k)$ is equal to column $2^\ell i + k$ (viewing k also as an integer in $[2^\ell ]$) of the matrix ${\mathbf {H}}_{b}$, for each $i \in S$ and $b \in \{0,1\}$. For $i \in [n] \setminus S$, let the output of ${\mathsf {H}}(i, \cdot , \cdot )$ be uniformly random. The distinguisher then runs ${\mathcal {A}}$ with input

$$\begin{aligned} \left( {\mathsf {H}}, {\varvec{z}}_0, {\varvec{z}}'_{0}, {\varvec{z}}_1, {\varvec{z}}_{1}'\right) , \end{aligned}$$

and outputs the same as ${\mathcal {A}}$. Notice that if the $\mathsf {DRSD}$ challenge is random, then the input to ${\mathcal {A}}$ is random, whereas if the challenge is computed as ${\varvec{y}}_j = {\mathbf {H}}{\varvec{e}}_j$ for some regular error ${\varvec{e}}_j$ and $j \in \{0,1\}$, then we have ${\varvec{z}}_j = {\mathbf {H}}_0 {\varvec{e}}_j$ and ${\varvec{z}}_j' = {\mathbf {H}}_1 {\varvec{e}}_j$, and by the definition of ${\mathsf {H}}$, these values are equal to the sum of hash function outputs under some secret keys corresponding to ${\varvec{e}}_j$. It follows that the distinguishing advantage of ${\mathcal {D}}$ is the same as that of ${\mathcal {A}}$. $\square$

4 GMW-Style MPC with Short Keys

In this section, we design a protocol for generating multiplication triples over ${\mathbb {F}}_2$ using short secret keys, with reduced communication complexity as the number of honest parties increases. More concretely, we first design a leaky protocol for secret-shared two-party bit multiplication, based on correlated OT and OT extension techniques with short keys. This protocol is not fully secure, and we precisely define the leakage, which is obtained by the receiver. We next show how to use the leaky protocol to produce multiplication triples, removing the leakage by rerandomizing the parties’ shares with shares of zero, and using the $\mathsf {DRSD}$ assumption. Finally, this protocol can be used with Beaver’s multiplication triple technique [9] to obtain MPC for binary circuits with an amortized communication complexity of $O(nt\ell )$ bits per triple, where t is the threshold and $\ell$ is the secret key length. In some cases, we can use short keys without relying on $\mathsf {DRSD}$, obtaining either $\ell =1$ when the number of honest parties is large enough, or $\ell =\log n$ otherwise.

Fig. 2

Functionality for oblivious transfer on random, correlated strings

4.1 Leaky Two-Party Secret-Shared Multiplication

We first present our protocol for two-party secret-shared bit multiplication. We modify the IKNP protocol for OT extension to use short keys, where by ‘IKNP’ we refer to the optimized variant by Asharov et al. [7], which we summarized in Sect. 2.3. With short keys, we cannot hope for computational security based on standard symmetric primitives, because an adversary can search every possible key in polynomial time. Our goal, therefore, is to define the precise leakage that occurs when using short keys, in order to remove this leakage at a later stage.

4.1.1 OT Extension and Correlated OT

Recall that the main observation of the IKNP protocol for extending oblivious transfer [46] is that correlated OT is symmetric, so that $\kappa$ correlated OTs on r-bit strings can be locally converted into r correlated OTs on $\kappa$-bit strings. Secondly, a $\kappa$-bit correlated OT can be used to obtain an OT on chosen strings with computational security. The first stage of this process is abstracted away by the functionality ${\mathcal {F}}_{\scriptstyle \mathrm {\varDelta -ROT}}$ in Fig. 2 and is implemented by the first two phases of IKNP as described in Sect. 2.3.

Using IKNP to multiply an input bit $x_k$ from the sender, $P_A$, with an input bit $y_k$ from $P_B$, the receiver, $P_B$ sends $y_k$ as its choice bit to ${\mathcal {F}}_{\scriptstyle \mathrm {\varDelta -ROT}}$ and learns ${\varvec{t}}_k = {\varvec{q}}_k \oplus y_k \cdot \varDelta$. The sender $P_A$ obtains ${\varvec{q}}_k$ and then, sends

$$\begin{aligned} d_k = {\mathsf {H}}({\varvec{q}}_k) \oplus {\mathsf {H}}({\varvec{q}}_k \oplus \varDelta ) \oplus x_k, \end{aligned}$$

where ${\mathsf {H}}$ is a 1-bit output hash function. This allows the parties to compute an additive sharing of $x_k \cdot y_k$ as follows: $P_A$ defines the share ${\mathsf {H}}({\varvec{q}}_k)$, and $P_B$ computes ${\mathsf {H}}({\varvec{t}}_k) \oplus y_k \cdot d_k$. This can be repeated many times with the same $\varDelta$ to perform a large batch of $\mathsf {poly}(\kappa )$ secret-shared multiplications, because the randomness in $\varDelta$ serves to computationally mask each x with the hash values (under a suitable correlation robustness assumption for ${\mathsf {H}}$). The downside of this is that for $\varDelta \in \{0,1\}^\kappa$, the communication cost is $O(\kappa )$ bits per two-party bit multiplication, to perform the correlated OTs.

4.1.2 Variant with Short Keys

We adapt this protocol to use short keys by performing the correlated OTs on $\ell$-bit strings, instead of $\kappa$-bit, for some small key length $\ell = O(\log \kappa )$ (we could have $\ell$ as small as 1). This allows ${\mathcal {F}}_{\scriptstyle \mathrm {\varDelta -ROT}}$ to be implemented with only $O(\ell )$ bits of communication per OT instead of $O(\kappa )$.

Our protocol, shown in Fig. 4, performs a batch of r multiplications at once. First, the parties create r correlated OTs on $\ell$-bit strings using ${\mathcal {F}}_{\scriptstyle \mathrm {\varDelta -ROT}}$. Next, the parties hash the output strings of the correlated OTs, and $P_A$ sends over the correction values $d_k$, which are used by $P_B$ to convert the random OTs into a secret-shared bit multiplication. Finally, we require the parties to add a random value (from ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}$, shown in Fig. 1) to their outputs, which ensures that they have a uniform distribution.

Note that if $\ell \in O(\log \kappa )$, then the hash function ${\mathsf {H}}_{AB}$ has a polynomial-sized domain, so can be described as a lookup table provided as a common input to the protocol by both parties. At this stage, we do not make any assumptions about ${\mathsf {H}}_{AB}$; this means that the leakage in the protocol will depend on the hash function, so its description is also passed to the functionality ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ (Fig. 3). We require ${\mathsf {H}}_{AB}$ to take as additional input an index $k \in [r]$ and a bit in $\{0,1\}$, to provide independence between different uses, and our later protocols require the function to be different in protocol instances between different pairs of parties (we use the notation ${\mathsf {H}}_{AB}$ to emphasize this).

Fig. 3

Ideal functionality for leaky secret-shared two-party bit multiplication

4.1.3 Leakage

We now analyse the exact security of the protocol in Fig. 4 when using short keys and explain how this is specified in the functionality ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ (Fig. 3). Since a random share of zero is added to the outputs, note that the output distribution is uniformly random. Also, like IKNP, the protocol is perfectly secure against a corrupt $P_A$ (or sender), so we only need to be concerned with leakage to a corrupt $P_B$ who also sees the intermediate values of the protocol.

The leakage is different for each k, depending on whether $y_k=0$ or $y_k=1$, so we consider the two cases separately. Within each case, there are two potential sources of leakage: firstly, the corrupt $P_B$’s knowledge of ${\varvec{t}}_k$ and $\rho _k$ may cause leakage (where $\rho _k$ is a random share of zero), since these values are used to define $P_A$’s output. Secondly, the $d_k$ values seen by $P_B$, which equal

$$\begin{aligned} d_k = {\mathsf {H}}_{AB}(k,y_k,{\varvec{t}}_k) \oplus {\mathsf {H}}_{AB}(k,1\oplus y_k,{\varvec{t}}_k \oplus \varDelta ) \oplus x_k, \end{aligned}$$

(1)

may leak information on $P_A$’s inputs $x_k$.

Case 1 $(y_k=1)$.

In this case, there is only leakage from the values ${\varvec{t}}_k$ and $\rho _k$, which are used to define $P_A$’s output. Since $z_k^A = {\mathsf {H}}_{AB}(k,0,{\varvec{t}}_k \oplus \varDelta ) \oplus \rho _k$, all of $P_A$’s outputs (and hence, also inputs) where $y_k=1$ effectively have only $\ell$ bits of min-entropy in the view of $P_B$, corresponding to the random choice of $\varDelta$. In this case, $P_B$’s output is $z_k^B = z_k^A \oplus x_k = {\mathsf {H}}_{AB}(k,0,{\varvec{t}}_k \oplus \varDelta ) \oplus \rho _k \oplus x_k$. To ensure that $P_B$’s view is simulable, the functionality needs to sample a random string $\varDelta \leftarrow \{0,1\}^\ell$ and leak ${\mathsf {H}}_{AB}(k, 0, {\varvec{t}}_k \oplus \varDelta ) \oplus x_k$ to a corrupt $P_B$.

Concerning the $d_k$ values, notice that when $y_k=1$ $P_B$ can compute ${\mathsf {H}}_{AB}(k,1,{\varvec{t}}_k)$ and use (1) to recover ${\mathsf {H}}_{AB}(k,0,{\varvec{q}}_k) + x_k$, which equals $z^A_k + \rho _k + x_k$. However, this is not a problem, because in this case we have $z^B_k = z^A_k + x_k$, so $d_k$ can be simulated given $P_B$’s output.

Case 2 $(y_k=0)$.

Here, the $d_k$ values seen by $P_B$ cause leakage on $P_A$’s inputs, because $\varDelta$ is short. Looking at (1), $d_k$ leaks information on $x_k$ because $\varDelta \leftarrow \{0,1\}^\ell$ is the only unknown in the equation and is fixed for every k. Similarly to the previous case, this means that all of $P_A$’s inputs where $y_k=0$ have only $\ell$ bits of min-entropy in the view of an adversary who corrupts $P_B$. We can again handle this leakage, by defining ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ to leak ${\mathsf {H}}_{AB}(k, 1, {\varvec{t}}_k \oplus \varDelta ) + x_k$ to a corrupt $P_B$.

Note that there is no leakage from the ${\varvec{t}}_k$ values when $y_k=0$, because then ${\varvec{t}}_k={\varvec{q}}_k$, so these messages are independent of $\varDelta$ and the inputs of $P_A$.

In the functionality ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$, we actually modify the above slightly so that the leakage is defined in terms of linear algebra, instead of the hash function ${\mathsf {H}}_{AB}$, to simplify the translation to the $\mathsf {DRSD}$ problem later on. Therefore, ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ defines a matrix ${\mathbf {H}}\in {\mathbb {F}}_2^{r \times 2^\ell }$, which contains the $2^\ell$ values $\{{\mathsf {H}}_{AB}(k,1\oplus y_k,{\varvec{t}}_k\oplus \varDelta )\}_{\varDelta \in \{0,1\}^\ell }$ in row k, where each ${\varvec{t}}_k$ is uniformly random. Given ${\mathbf {H}}$, the leakage from the protocol can then be described by sampling a random unit vector ${\varvec{e}}\in {\mathbb {F}}_2^{2^\ell }$ (which corresponds to $\varDelta \in \{0,1\}^\ell$ in the protocol) and leaking ${\varvec{u}}= {\mathbf {H}}{\varvec{e}}+ {\varvec{x}}$ to a corrupt $P_B$.

Fig. 4

Leaky secret-shared two-party bit multiplication protocol

We remark that this leakage reveals a lot of information about $P_A$’s input ${\varvec{x}}$, and in particular, if a corrupt $P_B$ knows something about the distribution of ${\varvec{x}}$ then it might leverage this to learn $\varDelta$ and thus all of ${\varvec{x}}$. This illustrates the challenge of using leaky multiplication to build a secure MPC protocol, which we overcome in the next section.

Theorem 4.1

Protocol $\varPi _{\scriptstyle \mathrm {Leaky-2-Mult}}^{r,\ell }$ securely implements the functionality ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}^{r,\ell }$ with perfect security in the $({\mathcal {F}}_{\scriptstyle \mathrm {\varDelta -ROT}},{\mathcal {F}}_{\scriptstyle \mathrm {Zero}})$-hybrid model in the presence of static honest-but-curious adversaries.

Proof

The main challenge in the proof consists of showing that the leakage to $P_B$ in the functionality can be translated directly to the leakage introduced in the protocol in the view of $P_B$. More formally, for the two cases of a corrupt $P_A$, and a corrupt $P_B$, we define a simulator who obtains the corrupted party’s inputs and the output of ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$, and simulates the view of the corrupted party during a protocol execution.

4.1.4 No Corruptions

Here, no simulation is necessary because all communication is over private channels, so we just need to show that the outputs of an honest execution are distributed identically to the functionality. By inspection, the protocol is correct. Observe that the outputs of $P_A$ are uniformly random, because $\rho _k$ is uniformly random. Since $P_B$’s outputs are fixed by the inputs and $P_A$’s outputs, we are done.

4.1.5 Corrupt $P_A$

This is the simpler of the remaining two cases. The simulator ${\mathcal {S}}_A$ receives $P_A$’s inputs $x_1,\ldots ,x_r \in {\mathbb {F}}_2$, as well as the outputs $z_1^A,\ldots ,z_r^A$ from ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$. It completes the view of $P_A$ by sampling the $q_1,\ldots ,q_r \leftarrow \{0,1\}^\ell$ $P_A$ receives from ${\mathcal {F}}_{\scriptstyle \mathrm {\varDelta -ROT}}$ and then, sends $\rho _k = z_k^A - {\mathsf {H}}_{AB}(k,0,q_k)$ to simulate $P_A$’s outputs from ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}$.

It is easy to see that the views in the two executions are identically distributed, since no messages are sent to $P_A$ during the protocol, and the definition of $\rho _k$ in the simulation ensures that $\rho _k$ is uniformly random (because $z_k^A$ is) and also consistent with $P_A$’s output and the hash function, as in the protocol.

4.1.6 Corrupt $P_B$

We define a simulator ${\mathcal {S}}_B$, who receives the inputs $y_1,\ldots ,y_r \in \{0,1\}$ and then, obtains the values $z^B_1,\ldots ,z^B_r, {\mathbf {H}}, {\varvec{u}}= (u_1,\ldots ,u_r)$ from the functionality.

Let ${\mathcal {S}}_B$ sample values $t_1,\ldots ,t_r \in \{0,1\}^\ell$ at random, subject to the constraint that for every $k \in [r]$ and $k' \in \{0,1\}^\ell$, ${\mathsf {H}}_{AB}(k,1\oplus y_k, t_k \oplus k')$ is equal to entry $(k,k')$ of ${\mathbf {H}}$ (viewing $k'$ also as an integer in $[2^\ell ]$). Note that because of the way ${\mathbf {H}}$ is defined in ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$, such a $t_k$ is guaranteed to exist and can be found by searching all $2^{2\ell } = \mathsf {poly}(\kappa )$ possibilities of $k'$ and $t_k$. This also ensures it will be identically distributed to the $t_k$ sampled by the functionality. ${\mathcal {S}}_B$ sends these values $t_k$ as the outputs of ${\mathcal {F}}_{\scriptstyle \mathrm {\varDelta -ROT}}$ to $P_B$.

For all $k \in [r]$, ${\mathcal {S}}_B$ then emulates the output of ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}$ to $P_B$ as follows:

• 1. If $y_k=0$, send $\rho _k = z^B_k + {\mathsf {H}}_{AB}(k,0,t_k)$.

• 2. If $y_k=1$, send $\rho _k = z^B_k + u_k$.

Finally, for $k \in [r]$, ${\mathcal {S}}_B$ sends $d_k = u_k + {\mathsf {H}}_{AB}(k,y_k,t_k)$ to $P_B$. This completes the simulation of $P_B$’s view.

Regarding indistinguishability, first note that the $t_k$ values are identically distributed as a uniformly random value in both executions, since in the real world ${\varvec{t}}_k = {\varvec{q}}_k \oplus y_k \cdot \varDelta$ and ${\varvec{q}}_k \leftarrow \{0,1\}^\ell$. Now, considering the case when $y_k=0$, we have:

$$\begin{aligned} z_k^B + {\mathsf {H}}_{AB}(k,0,t_k) + \rho _k = 0, \end{aligned}$$

from the definition of $\rho _k$. Since in both worlds $z_k^B, t_k$ and $\rho _k$ are all uniformly random, subject to the above, this means that these values are identically distributed in both worlds. Also, it is easy to see that the simulated $d_k$ values are computed exactly as in the protocol, because of the way ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ computes $u_k$.

When $y_k=1$, we have:

$$\begin{aligned} z_k^B + {\mathsf {H}}_{AB}(k,1,t_k) + d_k + \rho _k = 0 \iff&(\rho _k + u_k) + {\mathsf {H}}_{AB}(k,1,t_k) + \rho _k = d_k\\ \iff&{\mathsf {H}}_{AB}(k,0, t_k \oplus \tilde{\varDelta }) + {\mathsf {H}}_{AB}(k,1,t_k) + x_k = d_k, \end{aligned}$$

where $\tilde{\varDelta } \in [2^\ell ]$ denotes the position of the 1 in ${\varvec{e}}$ sampled by ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ to compute ${\varvec{u}}$, so is identically distributed to $\varDelta \in \{0,1\}^\ell$ in the real protocol. Therefore, the last equation above holds, which implies that $z_k^B$, $\rho _k$ and $d_k$ are all distributed identically to the values in the real protocol.

4.1.7 Communication Complexity

The cost of computing r secret-shared products is that of $\ell$ random, correlated OTs on r-bit strings, and a further r bits of communication. Using OT extension [7, 46] with a correlation-robust hash function to implement the correlated OTs, the amortized cost is $\ell (r + \kappa )$ bits for computational security $\kappa$. This gives a total cost of $\ell (r + \kappa ) + r$ bits.

4.2 MPC for Binary Circuits From Leaky OT

We now show how to use the leaky OT protocol to compute multiplication triples over ${\mathbb {F}}_2$, using a GMW-style protocol [39, 40] optimized for the case of at least h honest parties. This can then be used to obtain a general MPC protocol for binary circuits using Beaver’s method [9].

4.2.1 Triple Generation

We implement the triple generation functionality over ${\mathbb {F}}_2$, shown in Fig. 5. Recall that to create a triple using the GMW method, first each party locally samples shares $x^i,y^i \leftarrow {\mathbb {F}}_2$. Next, the parties compute shares of the product based on the fact that:

$$\begin{aligned} \left( \sum _{i=1}^n x^i\right) \cdot \left( \sum _{i=1}^n y^i\right) = \sum _{i=1}^n x^iy^i + \sum _{i=1}^n \sum _{j \ne i} x^i y^j. \end{aligned}$$

where $x^i$ denotes $P_i$’s share of $x = \sum _i x^i$.

Since each party can compute $x^iy^i$ on its own, in order to obtain additive shares of $z = x y$ it suffices for the parties to obtain additive shares of $x^i y^j$ for every pair $i \ne j$. This can be done using oblivious transfer between $P_i$ and $P_j$, since a 1-out-of-2 OT implies two-party secret-shared bit multiplication. To improve efficiency, we actually realize a slight variation of this functionality where two (possibly overlapping) subsets ${{\mathcal {P}}}_{(h)},{{\mathcal {P}}}_{(1)}$ such that ${{\mathcal {P}}}_{(h)}$ has at least h honest parties and ${{\mathcal {P}}}_{(1)}$ has at least one honest party, choose the respective shares of x and y.

Fig. 5

Multiplication triple generation functionality

If we plug in our leaky two-party batch multiplication protocol to GMW, this naive approach fails to give a secure protocol, because the leakage in ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ allows a corrupt $P_B$ to guess $P_A$’s inputs with probability $2^{-\ell }$. When obtaining shares of the pairwise products, $P_A$ does a secret-shared multiplication using the same input shares with every other party, which introduces further leakage on $P_A$’s shares for every corrupt party, increasing the success probability further. If the number of corrupted parties is not too small, then this gives the adversary a significant chance of successfully guessing the shares of every honest party, completely breaking security.

To avoid this issue, we require $P_A$ to randomize the shares used as input to ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$, in such a way that we still preserve correctness of the protocol. To do this, the parties will use ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}$ to generate random zero shares $s^{i,j}\in {\mathbb {F}}_2$ (held by $P_i$), satisfying $\sum _i s^{i,j} = 0$ for all $j \in [n]$, and then $P_i$ and $P_j$ will multiply $x^i + s^{i,j}$ and $y^j$. This means that all parties end up computing shares of:

$$\begin{aligned} \sum _{i=1}^n \sum _{j=1}^n (x^i + s^{i,j}) y^j = \sum _{j=1}^n y^j \sum _{i=1}^n (x^i + s^{i,j}) = xy, \end{aligned}$$

so still obtain a correct triple.

Finally, to ensure that the output shares are uniformly random, fresh shares of zero will be added to each party’s share of xy.

Note that masking each $x^i$ input to ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ means that it does not matter if the individual shares are leaked to the adversary, as long as it is still hard to guess the sum of all shares. This means that we only need to be concerned with the sum of the leakage from ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$. Recall that each individual instance leaks the input of an honest party $P_i$ masked by ${\mathbf {H}}_i{\varvec{e}}_i$, where ${\mathbf {H}}_i$ is a random matrix and ${\varvec{e}}_i \in {\mathbb {F}}_2^{2^\ell }$ is a random unit vector. Summing up all the leakage from h honest parties, we get

$$\begin{aligned} \sum _{i=1}^h {\mathbf {H}}_i {\varvec{e}}_i = ({\mathbf {H}}_1 \Vert \cdots \Vert {\mathbf {H}}_h) \begin{pmatrix}{\varvec{e}}_1 \\ \vdots \\ {\varvec{e}}_h \\ \end{pmatrix} \end{aligned}$$

This is exactly an instance of the $\mathsf {DRSD}_{r,h,\ell }$ problem, so is pseudorandom for an appropriate choice of parameters.

We remark that the number of triples generated, r, affects the hardness of $\mathsf {DRSD}$. However, we can create an arbitrary number of triples without changing the assumption by repeating the protocol for a fixed r. Note that each invocation of $\varPi _{\scriptstyle \mathrm {Leaky-2-Mult}}^{r,\ell }$ samples a different value $\varDelta$.

4.2.2 Reducing the Number of OT Channels

The above approach reduces communication of GMW by a factor $\kappa /\ell$, for $\ell$-bit keys, but still requires a complete network of $n(n-1)$ OT and communication channels between the parties. We can reduce this further by again taking advantage of the fact that there are at least h honest parties. We observe that when using our two-party secret-shared multiplication protocol to generate triples, information is only leaked on the $x^i$ shares, and not the $y^i$ shares of each triple. This means that $h-1$ parties can choose their shares of y to be zero, and y will still be uniformly random to an adversary who corrupts up to $t=n-h$ parties. This reduces the number of OT channels needed from $n(n-1)$ to $(t+1)(n-1)$.

When the number of parties is large enough, we can do even better using random committees. We randomly choose two committees, ${{\mathcal {P}}}_{(h)}$ and ${{\mathcal {P}}}_{(1)}$, such that except with negligible probability, ${{\mathcal {P}}}_{(h)}$ has at least h honest parties and ${{\mathcal {P}}}_{(1)}$ has at least one honest party. Only the parties in ${{\mathcal {P}}}_{(h)}$ choose nonzero shares of x, and parties in ${{\mathcal {P}}}_{(1)}$ choose nonzero shares of y; all other parties do not take part in any OT instances, and just output random sharings of zero. We remark that it can be useful to choose the parameter h lower than the actual number of honest parties, to enable a smaller committee size (at the cost of potentially larger keys). When the total number of parties, n, is large enough, this means the number of interacting parties can be independent of n. The complete protocol, described for two fixed committees satisfying our requirements, is shown in Fig. 6.

Fig. 6

Secret-shared triple generation using leaky two-party multiplication

4.2.3 Communication Complexity

Recall from the analysis in Sect. 4.1 that the cost of r multiplications with $\varPi _{\scriptstyle \mathrm {Leaky-2-Mult}}$ is that of $\ell$ random, correlated OTs on r-bit strings, and a further r bits of communication. Using OT extension, this gives a cost of $\ell (r + \kappa ) + r$ bits between every pair of parties in ${{\mathcal {P}}}_{(h)}\times {{\mathcal {P}}}_{(1)}$ (ignoring ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}$ and the seed OTs for OT extension, since their communication cost is independent of the number of triples). If the two committees ${{\mathcal {P}}}_{(h)},{{\mathcal {P}}}_{(1)}$ have sizes $n_h \le n$ and $n_1 \le t+1$, then we have the following theorem

Theorem 4.2

Protocol $\varPi _{\scriptstyle \mathrm {Triple}}$ securely realizes ${\mathcal {F}}_{\scriptstyle \mathrm {Triple}}^r$ in the $({\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}^{r,\ell },{\mathcal {F}}_{\scriptstyle \mathrm {Zero}}^{(n+1)r})$-hybrid model, based on the $\mathsf {DRSD}_{r,h,\ell }$ assumption, where h is the number of honest parties in ${{\mathcal {P}}}_{(h)}$. The amortized communication cost is $\le n_h n_1(\ell + \ell \kappa /r + 1)$ bits per triple, using OT extension based on a correlation-robust function.

Proof

The claimed communication complexity follows from the previous analysis. Security relies on the fact that $P_i \in {{\mathcal {P}}}_{(h)}$’s input to ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ is always of the form $x^i + s^{i,j}$, where $s^{i,j}$ is a fresh, random sharing of zero. This means that any leakage on $P_i$’s input from ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ is perfectly masked by $s^{i,j}$, and we only need to consider the sum of the leakage from all honest parties in ${{\mathcal {P}}}_{(h)}$.

Recall that we have two committees ${{\mathcal {P}}}_{(h)}$ and ${{\mathcal {P}}}_{(1)}$ of sizes $n_h$ and $n_1$, with at least h and 1 honest parties, respectively. Let ${\mathcal {A}}$ be an adversary corrupting a set of parties A. Throughout the proof, we will write $x_1,\ldots ,x_r$ to denote the components of a vector ${\varvec{x}}\in {\mathbb {F}}_2^r$.

We construct a simulator, ${\mathcal {S}}$, which interacts with ${\mathcal {A}}$ as follows:

• 1. Simulate the CRS with $n_h$ randomly sampled functions ${\mathsf {H}}_i : [r] \times \{0,1\}\times \{0,1\}^\ell \rightarrow \{0,1\}$.

• 2. Call ${\mathcal {F}}_{\scriptstyle \mathrm {Triple}}^r$ to receive the corrupted parties’ outputs, $(x^i_k,y^i_k,z^i_k)_{i \in A \cap ({{\mathcal {P}}}_{(h)}\cup {{\mathcal {P}}}_{(1)}), k \in [r]}$.

• 3. For each $i \in {{\mathcal {P}}}_{(h)}\cap A$, sample ${\varvec{s}}^{i,j} \leftarrow {\mathbb {F}}_2^r$, for $j \in [n_1]$, and send these to ${\mathcal {A}}$ as the shares output by ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}$.

• 4. Let $P_i \in {{\mathcal {P}}}_{(h)}, P_j \in {{\mathcal {P}}}_{(1)}$. Compute the messages that would be sent by ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ to the adversary as follows:

  • (a) $P_i,P_j \in A$: Using both parties’ inputs, generate their random output shares as ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ would do and send these to ${\mathcal {A}}$. Explicitly, the simulator samples shares ${\varvec{a}}^{i,j},{\varvec{b}}^{j,i}$ that sum to $({\varvec{x}}^i + {\varvec{s}}^{i,j}) * {\varvec{y}}^j$, and the leakage $({\mathbf {H}}^{i,j},{\varvec{u}}^{i,j})$ on ${\varvec{x}}^i+{\varvec{s}}^{i,j}$ (just as ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ would do).

  • (b) $P_i \in A, P_j \notin A$: Emulate the corrupt $P_i$’s view honestly, by sampling ${\varvec{a}}^{i,j} \leftarrow {\mathbb {F}}_2^r$.

  • (c) $P_i \notin A, P_j \in A$: Sample uniform values ${\varvec{b}}^{j,i},{\varvec{u}}^{i,j} \leftarrow {\mathbb {F}}_2^r$, and sample ${\mathbf {H}}^{i,j} \in {\mathbb {F}}_2^{m \times 2^\ell }$ exactly as ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ would do, using knowledge of ${\mathsf {H}}_i$ and ${\varvec{y}}^j$.

• 5. For $i \in A \cap ({{\mathcal {P}}}_{(h)}\cup {{\mathcal {P}}}_{(1)})$, compute ${\varvec{\rho }}^i = {\varvec{z}}^i + ({\varvec{x}}^i + {\varvec{s}}^{i,i}) * {\varvec{y}}^i + \sum _{j \ne i} ({\varvec{a}}^{i,j} + {\varvec{b}}^{i,j})$ and send this as the $\rho ^i_k$ share from ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}$.

• 6. Send to ${\mathcal {A}}$ the values $\{{\varvec{a}}^{i,j}\}_{i \in {{\mathcal {P}}}_{(h)}\cap A, j \in {{\mathcal {P}}}_{(1)}} \cup \{{\varvec{b}}^{j,i},{\mathbf {H}}^{i,j},{\varvec{u}}^{i,j}\}_{i \in {{\mathcal {P}}}_{(h)},j \in {{\mathcal {P}}}_{(1)}\cap A}$ as defined above, to simulate the outputs of ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$.

$\square$

We first consider the distribution of the parties’ outputs.

Claim 4.3

The outputs of the protocol are distributed identically to outputs of the functionality.

Proof

We need to show that, in the real protocol, $\{z^i_k\}_{i,k}$ are uniformly random subject to $\sum _i z^i_k = \sum _i x^i_k \cdot \sum _i y^i_k$. Firstly, the correctness constraint holds because

$$\begin{aligned} \sum _{i=1}^n z^i_k= & {} \sum _{i=1}^n \left( (x^i_k + s^{i,i}_k)\cdot y^i_k + \sum _{j \ne i} (a^{i,j}_k + b^{i,j}_k) + \rho ^i_k \right) \\= & {} \sum _{i=1}^n x^i_k\cdot y^i_k + \sum _{i=1}^n \left( y^i_k \cdot s^{i,i}_k + \sum _{j \ne i} (a^{i,j}_k + b^{j,i}_k) \right) \\= & {} \sum _{i=1}^n x^i_k\cdot y^i_k + \sum _{i=1}^n \left( y^i_k \cdot s^{i,i}_k + \sum _{j \ne i} y^i_k \cdot (x^j_k + s^{j,i}_k) \right) \\= & {} x_k \cdot y_k + \sum _{i=1}^n y^i_k \cdot \sum _{j=1}^n s^{j,i}_k \\= & {} x_k \cdot y_k \end{aligned}$$

where the second line above holds because $\sum _i \rho ^i_k = 0$, and the final line uses $\sum _j s^{j,i}_k = 0$.

Now, to see that $(z^i_k)_i$ are uniformly random, subject to the above, notice that the masks $(\rho ^i_k)_{i=1}^{n-1}$ are uniformly random in the protocol, so the same is true of $(z^i_k)_{i=1}^{n-1}$. This completes the claim. $\square$

We next consider the entire view of the environment ${\mathcal {Z}}$, which is the joint distribution of all parties’ inputs and outputs, and the messages received by the adversary during the protocol. Using vector notation, this is:

$$\begin{aligned}&({\varvec{x}}^i,{\varvec{y}}^j,{\varvec{z}}^i, {\varvec{z}}^j)_{i \in {{\mathcal {P}}}_{(h)}, j \in {{\mathcal {P}}}_{(1)}}, ({\varvec{\rho }}^i, {\varvec{s}}^{i,j}, {\varvec{a}}^{i,j})_{i \in A \cap {{\mathcal {P}}}_{(h)}, j \in {{\mathcal {P}}}_{(1)}},\\&({\varvec{\rho }}^j, {\varvec{b}}^{j,i}, {\varvec{u}}^{i,j}, {\mathbf {H}}^{i,j})_{i \in {{\mathcal {P}}}_{(h)}, j \in {{\mathcal {P}}}_{(1)}\cap A} \end{aligned}$$

First note that the ${\varvec{\rho }}^\tau , \tau \in {{\mathcal {P}}}_{(h)}\cup {{\mathcal {P}}}_{(1)}$ and ${\varvec{s}}^{i,j}$ shares, for $i \in {{\mathcal {P}}}_{(h)}\cap A, j \in {{\mathcal {P}}}_{(1)}\setminus A$, are uniformly random in both executions, since the environment never sees the honest parties’ shares. Secondly, recall that in the simulation, ${\varvec{a}}^{i,j}$ for corrupt $P_i$ and honest $P_j$) and ${\varvec{b}}^{j,i}$ (for corrupt $P_j$ and honest $P_i$) are computed uniformly at random, and this is identically distributed to the values in the protocol sampled by ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$, because the outputs of the honest party in that instance are not seen by ${\mathcal {Z}}$. Also, notice that when $P_j$ is corrupt, ${\mathcal {S}}$ computes ${\mathbf {H}}^{i,j}$ exactly as in the real protocol, because ${\mathcal {S}}$ knows $P_j$’s input ${\varvec{y}}^j$.

This leaves the $\{{\varvec{u}}^{i,j}\}_{i \in {{\mathcal {P}}}_{(h)}\setminus A,j \in {{\mathcal {P}}}_{(1)}\cap A}$ values, which are the main challenge, because the simulation computes these with random values, whilst the real execution uses the honest $P_i$’s inputs, computing ${\varvec{u}}^{i,j} = {\mathbf {H}}^{i,j}{\varvec{e}}^{i,j} + {\varvec{x}}^i + {\varvec{s}}^{i,j}$ for a random unit vector ${\varvec{e}}^{i,j}$. Let $P_{i_1}, \ldots , P_{i_h}$ be the honest parties in ${{\mathcal {P}}}_{(h)}$. Because the ${\varvec{s}}^{i,j}$ values are random shares of zero, it holds that the partial views containing the entire transcript except for $({\varvec{u}}^{i_1,j})_{j \in {{\mathcal {P}}}_{(1)}\cap A}$ are identically distributed. This is because for $P_j \in {{\mathcal {P}}}_{(1)}\cap A$, the masks ${\varvec{s}}^{i_2,j}, \ldots , {\varvec{s}}^{i_h,j}$ in the protocol are random and independent of the view of ${\mathcal {Z}}$, which makes the corresponding ${\varvec{u}}^{i_2,j}, \ldots , {\varvec{s}}^{i_h,j}$ values distributed the same as in the simulation.

Once we include ${\varvec{u}}^{i_1,j}$, however, these values are no longer independent because $\sum _{i \in {{\mathcal {P}}}_{(h)}}^n {\varvec{s}}^{i,j} = 0$. We therefore look at the distribution of $\sum _{k=1}^h {\varvec{u}}^{i_k,j}$, for some fixed $j \in {{\mathcal {P}}}_{(1)}\cap A$. In the protocol, we have

$$\begin{aligned} \begin{aligned} \sum _{i \in {{\mathcal {P}}}_{(h)}\setminus A} {\varvec{u}}^{i,j}&= \sum _{i \in {{\mathcal {P}}}_{(h)}\setminus A} ({\varvec{x}}^{i} + {\varvec{s}}^{i,j} + {\mathbf {H}}^{i,j}{\varvec{e}}^{i,j}) \\ \end{aligned} \end{aligned}$$

for some random, weight-1 vector ${\varvec{e}}^{i,j}$. In the simulation, all of the ${\varvec{u}}^{i,j}$’s are uniformly random.

Since ${\mathcal {Z}}$ can compute $\sum _{i \in {{\mathcal {P}}}_{(h)}\setminus A}({\varvec{x}}^{i} + {\varvec{s}}^{i,j})$ with the information it already has, it follows that distinguishing the two executions requires distinguishing

$$\begin{aligned} {\mathbf {H}}_i {\varvec{e}}_i := \big ( {\mathbf {H}}^{i_1,j} \Vert {\mathbf {H}}^{i_2,j} \Vert \cdots \Vert {\mathbf {H}}^{i_h,j} \big ) \begin{pmatrix} {\varvec{e}}^{i_1,j} \\ {\varvec{e}}^{i_2,j} \\ \vdots \\ {\varvec{e}}^{i_h,j} \\ \end{pmatrix} \end{aligned}$$

and the uniform distribution on r bits (given ${\mathbf {H}}_i$).

We claim that this corresponds exactly to solving the $\mathsf {DRSD}_{r,h,\ell }$ problem, because ${\mathbf {H}}_i$ is uniformly distributed in ${\mathbb {F}}_2^{r \times 2^\ell h}$ and ${\varvec{e}}_i$ is a uniformly random, 1-regular error vector of weight h.

Lemma 4.4

Any environment distinguishing the real and ideal executions with advantage $\delta$ can be used to break $\mathsf {DRSD}_{r,h,\ell }$ with advantage at least $\delta /t$ (where $t = |{{\mathcal {P}}}_{(1)}\cap A |$).

Proof

Assume w.l.o.g. that the corrupted parties in ${{\mathcal {P}}}_{(1)}$ are indexed $P_1,\ldots ,P_t$. We construct a sequence of hybrid executions, ${\mathbf {HYB}}_0,\ldots ,{\mathbf {HYB}}_t$, where hybrid ${\mathbf {HYB}}_0$ is identical to the simulation. In hybrid ${\mathbf {HYB}}_{j'}$, instead of the simulator sampling ${\varvec{u}}^{i,j}$ (for $j \le j', i \in {{\mathcal {P}}}_{(h)}\setminus A$) at random, we replace this with the real ${\varvec{u}}^{i,j}$ generated using $P_i$’s inputs as in the protocol. The final hybrid ${\mathbf {HYB}}_t$ is therefore identically distributed to the real execution.

Let ${\mathcal {A}}$ be an adversary for which the environment ${\mathcal {Z}}$ distinguishes between ${\mathbf {HYB}}_{j'}$ and ${\mathbf {HYB}}_{j'+1}$ with advantage $\delta$, for some index $j' < t$. We construct a distinguisher $\mathcal{D}$ for $\mathsf {DRSD}_{r,h,\ell }$ as follows. $\mathcal{D}$ receives a $\mathsf {DRSD}$ challenge ${\mathbf {H}}_{j'} \in {\mathbb {F}}_2^{r \times h2^\ell }, {\varvec{c}}^{j'} \in {\mathbb {F}}_2^r$. Write ${\mathbf {H}}_{j'} = ({\mathbf {H}}^{i_1, j'} \Vert {\mathbf {H}}^{i_2, j'} \Vert \cdots \Vert {\mathbf {H}}^{i_h,j'})$, where each ${\mathbf {H}}^{i_k,j'} \in {\mathbb {F}}_2^{r \times 2^\ell }$. Now, $\mathcal{D}$ simulates an execution of $\varPi _{\scriptstyle \mathrm {Triple}}$ with ${\mathcal {A}}$ as ${\mathcal {S}}$ would, with the following differences.

• $\mathcal{D}$ samples a set of honest parties’ shares, $({\varvec{x}}^i,{\varvec{y}}^i,{\varvec{z}}^i)_{i \notin A}$ which, together with the corrupt parties’ shares known to $\mathcal{D}$, form correct triples.

• Instead of sampling the function ${\mathsf {H}}_{i}$ in the CRS at random, sample it such that for every $k \in [h]$, the matrix ${\mathbf {H}}^{i_k,j'}$, sent later to the corrupt $P_{j'}$, is equal to the challenge matrix ${\mathbf {H}}^{i_k,j'}$. (The remainder of the CRS is sampled at random.)

• Instead of sampling the leakage terms ${\varvec{u}}^{i_k,j'}$ (for $k \in [h]$) uniformly and independently, sample them at random such that $\sum _{i \in {{\mathcal {P}}}_{(h)}} ({\varvec{u}}^{i,j'} + {\varvec{x}}^{i}) = {\varvec{c}}^{j'}$.

• For each $j < j'$, instead of sampling ${\varvec{u}}^{i_k,j'}$ uniformly, compute them as in the real protocol using the honest parties’ shares and shares of zero.

To conclude, $\mathcal{D}$ sends all the output shares to ${\mathcal {Z}}$ and outputs the same as ${\mathcal {Z}}$.

If the challenge $({\mathbf {H}}_{j'},{\varvec{c}}^{j'})$ comes from the $\mathsf {DRSD}$ distribution, then the ${\varvec{u}}^{i_k,j'}$ values are distributed as in a real execution, so we are in hybrid ${\mathbf {HYB}}_{j'+1}$. On the other hand, if ${\varvec{c}}^{j'}$ is uniformly random, then so are the ${\varvec{u}}^{i_k,j'}$, so we are in ${\mathbf {HYB}}_{j'}$. Therefore, the advantage of $\mathcal{D}$ is $\delta$, the same as that of ${\mathcal {Z}}$. A standard hybrid argument then shows that there exists a distinguisher for ${\mathbf {HYB}}_0$ and ${\mathbf {HYB}}_t$, which has advantage at least $\delta /t$. $\square$

4.2.4 Parameters for Unconditional Security

Recall from Lemma 3.4 and Corollary 3.6 that if $\ell =1$ and $h \ge r + s$, or if $h \ge (r+2s)/\ell$ for any $\ell$, then $\mathsf {DRSD}_{r,h,\ell }$ is statistically hard, with statistical security $2^{-s}$. This means when h is large enough, we can use 1-bit keys, and every pair of parties who communicates only needs to send $2 + \kappa /r$ bits over the network.²

4.2.5 MPC Using Multiplication Triples

Our protocol for multiplication triples can be used to construct a semi-honest MPC protocol for binary circuits using Beaver’s approach [9]. The parties first secret-share their inputs between all other parties. Then, XOR gates can be evaluated locally on the shares, whilst an AND gate requires consuming a multiplication triple, and two openings with Beaver’s method. Each opening can be done with $2(n-1)$ bits of communication as follows: all parties send their shares to $P_1$, who sums the shares together and sends the result back to every other party.

In the 1-bit key case mentioned above, using two (deterministic) committees of sizes n and $t+1$ and setting, for instance, $r = \kappa$ implies the following corollary. Note that the number of communication channels is $(t+1)(n-1)$ and not $(t+1)n$, because in the deterministic case ${{\mathcal {P}}}_{(1)}$ is contained in ${{\mathcal {P}}}_{(h)}$, so $t+1$ sets of the shared cross-products can be computed locally.

Corollary 4.5

Assuming OT and a correlation-robust function, there is a semi-honest MPC protocol for binary circuits with an amortized communication complexity of no more than $3(t+1)(n-1) + 4(n-1)$ bits per AND gate, if there are at least $\kappa + s$ honest parties.

Remark 4.6

We can obtain a feasibility result from OWF instead of a correlation-robust function, by using standard OT instead of OT extension. This comes at the cost of replacing $\kappa$ with the communication complexity of the OT protocol.

4.3 Optimization with Vandermonde Matrices

In this section, we show how to optimize our triple generation protocol using Vandermonde matrices. As we will see in Sect. 6, this approach is particularly convenient when the number of honest parties is small and allows to avoid relying on the DRSD assumption.

The high level idea is to replace the random choice of hash functions used in the previous protocol with deterministically chosen functions based on Vandermonde matrices. We show that the variant of regular syndrome decoding induced by this choice is perfectly secure, so we can plug the new functions directly into protocol $\varPi _{\scriptstyle \mathrm {Triple}}$ (Fig. 6) and improve the efficiency.

We redefine the functions ${\mathsf {H}}_i$, as follows. Let $\ell \ge \log n$ and $v_1,\ldots , v_n$ be distinct points in ${\mathbb {F}}_{2^\ell }$. Let $r = \ell \cdot h$, and let ${\mathbf {V}}\in {\mathbb {F}}_{2^\ell }^{n \times h}$ be the Vandermonde matrix given by

$$\begin{aligned} {\mathbf {V}}= \begin{pmatrix} 1 &{} v_1 &{} \cdots &{} v_1^{h-1} \\ 1 &{} v_2 &{} \cdots &{} v_2^{h-1} \\ \vdots &{} \ddots &{} \ddots &{} \vdots \\ 1 &{} v_n &{} \cdots &{} v_n^{h-1} \\ \end{pmatrix} \end{aligned}$$

and let ${\varvec{v}}_i$ be the i-th row of ${\mathbf {V}}$.

Define the hash functions ${\mathsf {H}}_i : [r] \times \{0,1\}^\ell \rightarrow \{0,1\}$, for $i=1,\ldots , n$, so that ${\mathsf {H}}_i(j, x)$ outputs the j-th bit of $x \cdot {\varvec{v}}_i \in {\mathbb {F}}_{2^\ell }^h$, where we expand $x \cdot {\varvec{v}}_i$ into a vector in ${\mathbb {F}}_2^{\ell \times h}$.

The following lemma implies perfect security of the variant of the RSD problem, where the $(r \times h2^\ell )$ matrix ${\mathbf {H}}$ contains ${\mathsf {H}}_i(j, k)$ in entry $(j, i\cdot 2^\ell + k)$.

Lemma 4.7

Let ${\mathcal {H}}$ be a size-h subset of [n]. For $\varDelta _i \leftarrow \{0,1\}^\ell$, $i \in [n]$, the distribution of

$$\begin{aligned} U = \sum _{i \in {\mathcal {H}}} ({\mathsf {H}}_i(1, \varDelta _i), \ldots , {\mathsf {H}}_i(r, \varDelta _i)) \end{aligned}$$

is uniform in $\{0,1\}^r$.

Proof

From the definition of ${\mathsf {H}}_i$, we have

$$\begin{aligned} U = \sum _{i \in {\mathcal {H}}} \varDelta _i \cdot {\varvec{v}}_i = (\varDelta _1, \ldots , \varDelta _n) \cdot {\mathbf {V}}_{{\mathcal {H}}} \end{aligned}$$

where ${\mathbf {V}}_{{\mathcal {H}}}$ denotes the restriction of ${\mathbf {V}}$ to rows with indices in ${\mathcal {H}}$. Since ${\mathbf {V}}$ is a Vandermonde matrix, any square matrix formed by taking h rows of ${\mathbf {V}}$ is invertible. Hence, U is uniformly distributed since ${\mathbf {V}}_{{\mathcal {H}}}$ is a bijection. $\square$

With this technique, we can use $\ell$-bit keys to produce $r = \ell \cdot h$ triples in one go. Just as with the DRSD-based protocol, the cost of producing the initial correlated OTs is $\ell (r + \kappa )$ bits of communication per pair of parties, with a further r bits for the leaky OT protocol. Using two committees of size $n_1$ and $n_2$, the overall communication cost per triple (from Theorem 4.2) is no more than

$$\begin{aligned} n_1 n_2 (\ell + \ell \kappa /r + 1) = n_1 n_2(\ell + \kappa /h + 1) \end{aligned}$$

Recall that the only constraint on the above parameters is that $\ell \ge \log n$, since we need $|{\mathbb {F}}_{2^\ell } | \ge n$ for the Vandermonde matrix to exist. Therefore, choosing $\ell = \log n$ we obtain the following.

Theorem 4.8

Assuming OT and a correlation-robust hash function, there is a semi-honest MPC protocol for binary circuits with an amortized communication complexity of no more than $(t+1)(n-1)(\log n + \kappa /(n - t) + 1) + 4(n-1)$ bits per AND gate.

When h is very large, this is not as efficient as the previous case where we could have $\ell =1$, but for more reasonable sizes of h we can achieve much smaller keys than previously, as we show in Sect. 6.

5 Multi-Party Garbled Circuits with Short Keys

In this section, we present our second contribution: a constant-round MPC protocol based on garbled circuits with short keys. The protocol has two phases, a preprocessing phase independent of the parties’ actual inputs where the garbled circuit is mutually generated by all parties, and an online phase where the computation is performed. We first abstractly discuss the details of our garbling method and then, turn to the two protocols for generating and evaluating the garbled circuit.

Fig. 7

Multi-party garbling functionality

5.1 The Multi-Party Garbling Scheme

Our garbling method is defined by the functionality ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ (Fig. 7), which creates a garbled circuit that is given to all the parties. It can be seen as a variant of the multi-party garbling technique by Beaver, Micali and Rogaway [20], known as BMR, which has been used and improved in a recent sequence of works [14, 45, 54, 55].

The main idea behind BMR is that every party $P_i$ contributes a pair of keys $k^i_{w,0}, k^i_{w,1} \in \{0,1\}^\kappa$ and a share of a wire mask $\lambda _w^i \in \{0,1\}$ for each wire w in the circuit. To garble a gate, the corresponding output wire key from every party is encrypted under the combination of all parties’ input wire keys, using a PRF or PRG, so that no single party knows all the keys for a gate. In addition, the free-XOR property can be supported by having each party choose their keys such that $k^i_{w,0} \oplus k^i_{w,1} = \varDelta ^i$, where $\varDelta ^i$ is a global fixed random string known to $P_i$.

The main difference between our work and recent related protocols is that we use short keys of length ${\ell _{\scriptscriptstyle \mathrm {BMR}}}$ instead of $\kappa$, and then garble gates using a random, expanding function ${\mathsf {H}}: [n] \times \{0,1\}\times \{0,1\}^{{\ell _{\scriptscriptstyle \mathrm {BMR}}}} \rightarrow \{0,1\}^{n{\ell _{\scriptscriptstyle \mathrm {BMR}}}+1}$. Instead of basing security on a PRF or PRG, we then reduce the security of the protocol to the pseudorandomness of the sum of ${\mathsf {H}}$ when applied to each of the honest parties’ keys, which is implied by the DRSD problem from Sect. 3. We also use ${\mathsf {H}}'$ to denote ${\mathsf {H}}$ with the least significant output bit dropped, which we use for garbling splitter gates.

To garble an AND gate g with input wires u, v and output wire w, each of the 4 garbled rows ${\tilde{g}}_{a,b}$, for $(a,b) \in \{0,1\}^2$, is computed as:

$$\begin{aligned} {\tilde{g}}_{a,b} = \left( \bigoplus _{i=1}^n {\mathsf {H}}(i,b,k^i_{u,a}) \oplus {\mathsf {H}}(i,a,k^i_{v,b}) \right) \oplus (c, k^1_{w,c}, \ldots , k^n_{w,c}), \end{aligned}$$

(2)

where $c= (a \oplus \lambda _u) \cdot (b \oplus \lambda _v) \oplus \lambda _w$ and $\lambda _u, \lambda _v, \lambda _w$ are the secret-shared wire masks. Each row can be seen as an encryption of the correct n output wire keys under the corresponding input wire keys of all parties. Note that, for each wire, $P_i$ holds the keys $k^i_{u,0},k^i_{u,1}$ and an additive share $\lambda _u^i$ of the wire mask. The extra bit value that ${\mathsf {H}}$ takes as input is added to securely increase the stretch of ${\mathsf {H}}$ when using the same input key twice, preventing a ‘mix-and-match’ attack on the rows of a garbled gate. Namely, when mixing the rows of a garbled gate which implies that an incorrect output key is decrypted. The output of ${\mathsf {H}}$ is also extended by an extra bit, to allow encryption of the output wire mask c.³

5.1.1 Splitter Gates

When relying on the DRSD problem, the reuse of a key in multiple gates degrades parameters and makes the problem easier (as the parameter r grows, the key length must be increased), so we cannot handle circuits with arbitrary fan-out. For this reason, we restrict our exposition of the garbling to fan-out-one circuits with so-called splitter gates. This type of gate takes as input a single wire w and provides two output wires u, v, each of them with fresh, independent keys representing the same value carried by the input wire. Converting an arbitrary circuit to use splitter gates incurs a cost of roughly a factor of two in the circuit size (see below)

Splitter gates were previously introduced in [69] as a fix for a similar issue in the original BMR paper [20], where the wire “keys” were used as seeds for a PRG in order to garble the gates, so that when a wire was used as input to multiple gates, their garbled versions did not use independent pseudorandom masks. Other recent BMR-style papers avoid this issue by applying the PRF over the gate identifier as well, which produces distinct, independent PRF evaluations for each gate.

5.1.2 Free-XOR

The Free-XOR [51] optimization results in an improvement in both computation and communication for XOR gates where a global fixed random $\varDelta _i$ is chosen by each party $P_i$ and the input keys are locally XORed, yielding the output key of this gate. We cannot use the standard free-XOR technique [14, 51] for the same reason discussed above: reusing a single offset across multiple gates would make the DRSD problem easier and not be secure. We therefore introduce a new free-XOR technique (inspired by FleXOR [50]) which, combined with our use of splitter gates, allows garbling XOR gates for free without additional assumptions. For each arbitrary fan-in XOR gate g, each party chooses a different offset $\varDelta _g^i$, allowing for a free-XOR computation for wires using keys with that offset. For general circuits, this would normally introduce the problem that the input wires may not have the correct offset, requiring some ‘translation’ to $\varDelta _g$. However, because we restrict to gates with fan-out-one and splitter gates, we know that each input wire to g is not an input wire to any other gate, so we can always ensure the keys use the correct offset without any further changes.

5.1.3 Compiling to Fan-out-one Circuits with Splitter Gates

Let $C_f$ be an arbitrary fan-out circuit, with A AND gates and X XOR gates, both with fan-in-two. Let $I_{C_f}$ and $O_{C_f}$ be the number of circuit-input and circuit-output wires, respectively. We will now compute the number S of splitter gates that the compiled circuit needs. First, note that each time a wire w is used as input to another gate or as a circuit-output wire, w’s fan-out is increased by one. Each of the AND, XOR gates in the pre-compiled circuit provides a fresh output wire to be used in $C_f$, while using for its inputs two pre-existing wires in the circuit. Output wires also use one pre-existing wire each, while input wires use no pre-existing wires. This means that, to compile $C_f$ to be a fan-out-one circuit, we need to add up to $(2\cdot X + 2 \cdot A + O_{C_f}) - (A + X + I_{C_f})$ wires. Each of these missing wires, however, can be created by using a splitter gate in the compiled circuit, since each of these gates uses one wire to generate two fresh new wires. So, putting all the pieces together, the compiled circuit requires $S \le X + A + O_{C_f} - I_{C_f}$ splitter gates. This gives a close upper bound, as if w is a circuit output wire and an input wire of another gate, then it is being counted twice rather than once in the formula.

5.2 The Preprocessing Protocol

Our protocol for generating the garbled circuit is shown in Fig. 10. We use two functionalities ${\mathcal {F}}_{\scriptstyle \mathrm {Bit \times Bit}}$ (Fig. 8) and ${\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}(P_j)$ (Fig. 9) for multiplying two additively shared bits, and multiplying an additively shared bit with a string held by $P_j$, respectively. ${\mathcal {F}}_{\scriptstyle \mathrm {Bit \times Bit}}$ can be easily implemented using a multiplication triple from ${\mathcal {F}}_{\scriptstyle \mathrm {Triple}}$ in the previous section, whilst ${\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}$ uses a variant of the $\varPi _{\scriptstyle \mathrm {Triple}}$ protocol optimized for this task. We provide more details on how to best implement the latter functionality in Sect. 5.3.

Fig. 8

Secret-shared bit multiplication functionality

Fig. 9

Secret-shared bit/string multiplication functionality

Most of the preprocessing protocol is similar to previous works [14, 45], where first each party samples their sets of wire keys and shares of wire masks, and then, the parties interact to obtain shares of the garbled gates. It is the second stage where our protocol differs, so we focus here on the details of the gate garbling procedures (Fig. 10).

Fig. 10

The preprocessing protocol that realizes ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$

5.2.1 The Gate Garbling Protocol

Fig. 11

The gate garbling sub-protocol

We describe the details of the sub-protocol $\varPi _{\scriptstyle \mathrm {Gate Garbling}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ (Fig. 11), implementing the gate garbling phase of ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$. Creating garbled AND gates is done similarly to the OT-based protocol [14], with the exception that we use short wire keys of length ${\ell _{\scriptscriptstyle \mathrm {BMR}}}$ instead of $\kappa$. We also show how to create sharings of garbled splitter gates without any interaction, so these are much cheaper than AND gates.

Suppose that for an AND gate g, each $P_i$ holds the wire mask share $\lambda _v^i$ and keys $k^i_{v,0}, k^i_{v,1} \leftarrow \{0,1\}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$. $P_i$ defines $R^i_g=k^i_{w,0} \oplus k^i_{w,1}$. After that all parties call ${\mathcal {F}}_{\scriptstyle \mathrm {Bit \times Bit}}$ once to compute additive shares of $\lambda _{uv}= \lambda _u \cdot \lambda _v \in \{0,1\}$, which are then used to locally compute shares of $\chi _{g,a,b} = (a \oplus \lambda _u) \cdot (b \oplus \lambda _v) \oplus \lambda _w$, for each $(a,b) \in \{0,1\}^2$. Each $P_i$ obtains $\chi _{g,a,b}^i$ such that $\chi _{g,a,b} = \oplus _{i \in [n]} \chi ^i_{g,a,b}$. To compute shares of the products $\chi _{g,a,b} \cdot R_g^i$, the parties call ${\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}^{{\ell _{\scriptscriptstyle \mathrm {BMR}}}}(P_i)$ three times, for each $i \in [n]$, to multiply $R_g^i$ with each of the bits $\lambda _u, \lambda _v, (\lambda _{uv}\oplus \lambda _w)$. These can then be used for each $P_j$ to locally obtain the shares $(\chi _{g,a,b} \cdot R_g^i)^j$, for all $(a,b) \in \{0,1\}^2$ (just as in [14]).

After computing the bit/string products, $P_j$ then computes for each $(a,b) \in \{0,1\}^2$:

$$\begin{aligned} \rho _{i,a,b}^j = {\left\{ \begin{array}{ll} (\chi _{g,a,b} \cdot R_g^i)^j \quad \quad &{}j \ne i\\ k^i_{w,0} \oplus (\chi _{g,a,b} \cdot R^i_g)^i \quad \quad &{}j=i. \end{array}\right. } \end{aligned}$$

These values define shares of $\chi _{g,a,b} \cdot R_g^i \oplus k^i_{w,0}$. Finally, each party’s share of the garbled AND gate is obtained as:

$$\begin{aligned} \tilde{g}_{a,b}^i = {\mathsf {H}}(i,b,k^i_{u,a}) \oplus {\mathsf {H}}(i,a,k^i_{v,b}) \oplus (\chi _{g,a,b}^i,\rho _{1,a,b}^i,\ldots ,\rho _{n,a,b}^i), \quad a, b \in \{0,1\}\end{aligned}$$

Summing up these values, we obtain:

$$\begin{aligned} \bigoplus _i \tilde{g}_{a,b}^i&= \bigoplus _i {\mathsf {H}}(i,b,k^i_{u,a}) \oplus {\mathsf {H}}(i,a,k^i_{v,b}) \oplus (\chi _{g,a,b}^i,\rho _{1,a,b}^i,\ldots ,\rho _{n,a,b}^i)\\&= \bigoplus _{i=1}^n ({\mathsf {H}}(i,b,k^i_{u,a}) \oplus {\mathsf {H}}(i,a,k^i_{v,b}) ) \oplus (c, k^1_{w,c}, \ldots , k^n_{w,c}), \end{aligned}$$

where $c= \chi _{g,a,b}$, as required.

To garble a splitter gate, we observe that here there is no need for any secure multiplications within MPC, and the parties can produce shares of the garbled gate without any interaction. This is because the two output wire values are the same as the input wire value, so to obtain a share of the encryption of the two output keys on wires u, v with input wire w, party $P_i$ just computes:

$$\begin{aligned} ({\mathsf {H}}'(i,0,k^i_{w,c}),{\mathsf {H}}'(i,1,k^i_{w,c})) \oplus (0, \ldots , k^i_{u,c}, 0, \ldots , k^i_{v,c}, 0, \ldots , 0) \end{aligned}$$

for $c \in \{0,1\}$, where the right-hand vector contains $P_i$’s keys in positions i and $n+i$. The parties then re-randomize this sharing with a share of zero from ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}$, so that opening the shares does not leak information on the individual keys.⁴

5.3 Protocols for Bit/String Multiplication

Even though we could implement ${\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}(P_j)$ using ${\mathcal {F}}_{\scriptstyle \mathrm {Triple}}$, there are more efficient ways to do so: One by building directly from ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$, and another using correlated OT [7], as we are going to describe.

• Using ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$, we give protocol $\varPi _{\scriptstyle \mathrm {Bit\times String}}^{r,{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ in Fig. 13. Here, we multiply each bit of the length-${\ell _{\scriptscriptstyle \mathrm {BMR}}}$ string with every share using leaky-OT. This is similar to our triple generation protocol $\varPi _{\scriptstyle \mathrm {Triple}}$ (Sect. 4), except that since the ${\ell _{\scriptscriptstyle \mathrm {BMR}}}$-string is not secret-shared but known to one party, we only need to perform ${\ell _{\scriptscriptstyle \mathrm {BMR}}}(n-1)$ invocations of ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$ in order to multiply it with a secret-shared bit $x = x^1 + \cdots + x^n$. The protocol uses random shares of zero to mask the inputs and outputs of ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$, similarly to $\varPi _{\scriptstyle \mathrm {Triple}}$. Note that this does not directly implement the functionality ${\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}(P_j)$ shown in Fig. 9, because $\varPi _{\scriptstyle \mathrm {Bit\times String}}^{r,{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ performs a batch of r independent multiplications in parallel. However, in the protocol $\varPi _{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ all the gates can be garbled in parallel, so a batch version of the functionality (as described in Fig. 12) suffices.

• Alternatively, we can do the secret-shared multiplication using $n-1$ (non-leaky) correlated OTs of length ${\ell _{\scriptscriptstyle \mathrm {BMR}}}$ (one between $P_j$ and every other party), for example using the protocol from [7].

Fig. 12

Batch secret-shared bit/string multiplication between $P_j$ and all parties

Fig. 13

n-party secret-shared bit/string multiplication using leaky 2-party multiplication

5.3.1 Communication Complexity

First, we consider the communication complexity of $\varPi _{\scriptstyle \mathrm {Bit\times String}}^{r,{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ described in Fig. 13. We note that in this case the communication complexity is exactly that of $(n-1){\ell _{\scriptscriptstyle \mathrm {BMR}}}$ instances of ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}^{r,{\ell _{\scriptscriptstyle \mathrm {OT}}}}$, where ${\ell _{\scriptscriptstyle \mathrm {OT}}}$ is the leakage parameter used in the protocol $\varPi _{\scriptstyle \mathrm {Leaky-2-Mult}}^{r,{\ell _{\scriptscriptstyle \mathrm {OT}}}}$. Note that ${\ell _{\scriptscriptstyle \mathrm {OT}}}$ is independent of ${\ell _{\scriptscriptstyle \mathrm {BMR}}}$ used in the bit/string protocol, but affects the security and cost of realising ${\mathcal {F}}_{\scriptstyle \mathrm {Leaky-2-Mult}}$. The total complexity is then $(n-1){\ell _{\scriptscriptstyle \mathrm {BMR}}}({\ell _{\scriptscriptstyle \mathrm {OT}}}(r + \kappa ) + r)$ bits, or an amortized cost of $(n-1){\ell _{\scriptscriptstyle \mathrm {BMR}}}({\ell _{\scriptscriptstyle \mathrm {OT}}}+ {\ell _{\scriptscriptstyle \mathrm {OT}}}\kappa /r + 1)$ bits per multiplication, as discussed in Sects. 4.1 and 4.2.

The alternative instantiation of ${\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}(P_j)$ using (non-leaky) correlated OTs requires to invoke them $n-1$ times. With the protocol from [7], each correlated OT has an amortized communication complexity of $\kappa +{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ bits. Hence, the amortized communication complexity of this approach is $(n-1)(\kappa + {\ell _{\scriptscriptstyle \mathrm {BMR}}})$ bits.

Which of the two proposed implementations is more efficient depends on the key lengths ${\ell _{\scriptscriptstyle \mathrm {BMR}}}$ and ${\ell _{\scriptscriptstyle \mathrm {OT}}}$.

Theorem 5.1

Protocol $\varPi _{\scriptstyle \mathrm {Bit\times String}}^{r,{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ UC-securely realizes ${\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}^{r,{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ in the ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}^{2r}$-hybrid in the presence of static honest-but-curious adversaries, under the $\mathsf {DRSD}_{r,h,{\ell _{\scriptscriptstyle \mathrm {OT}}}}$ assumption.

The proof is a direct extension of the proof of Theorem 4.2.

5.4 Security and Complexity

The above approach reduces size of the garbled circuit by a factor $\kappa /{\ell _{\scriptscriptstyle \mathrm {BMR}}}$, for ${\ell _{\scriptscriptstyle \mathrm {BMR}}}$-bit keys, but still requires n keys for every row in the garbled gates. Similarly to Sect. 4, when n is large we can reduce this by using a (random) committee ${{\mathcal {P}}}_{(h)}$ of size $n_h$ that has at least h honest parties. $\varPi _{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ and $\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ are then run as if called only by the parties in ${{\mathcal {P}}}_{(h)}$. For circuit-input wires w where parties in $\mathcal{P}\setminus {{\mathcal {P}}}_{(h)}$ provide input, they are sent the masks $\lambda _w$ in $\varPi _{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$, so in $\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ (Fig. 14) they can then broadcast $\varLambda _w=\rho ^i_{w} \oplus \lambda _w$ in the same way as parties in ${{\mathcal {P}}}_{(h)}$.

This reduces the size of the garbled circuit by an additional factor of $n / n_h$. Finally, the same committee ${{\mathcal {P}}}_{(h)}$ can be combined with a (random) committee ${{\mathcal {P}}}_{(1)}$ with a single honest party in order to optimize the bit multiplications needed to compute the $\chi _{g,a,b}$ values, as is described in Sect. 4.

In Sect. 6, we give some examples of committee sizes and key lengths that ensure security and compare this with the naive approach of running the preprocessing phase of BMR in ${{\mathcal {P}}}_{(1)}$ only.

Theorem 5.2

Protocol $\varPi _{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ UC-securely realizes the functionality ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ with perfect security in the $({\mathcal {F}}_{\scriptstyle \mathrm {Bit \times Bit}}, {\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}^{{\ell _{\scriptscriptstyle \mathrm {BMR}}}},{\mathcal {F}}_{\scriptstyle \mathrm {Zero}}^{2n{\ell _{\scriptscriptstyle \mathrm {BMR}}}})$-hybrid model in the presence of static honest-but-curious adversaries.

Proof

Let ${\mathcal {A}}$ denote a PPT adversary corrupting a subset of parties $A \subset [n]$, then we prove that there exists a PPT simulator $\mathcal{S}$ that simulates the adversary’s view. In the following, we denote by ${\bar{A}}$ the set of honest parties. When we say that the simulator is given some value, we mean that it receives it from ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$.

5.4.1 The Description of the Simulation

Denote by W and $O_{C_f}$, respectively, the set of wires and the set of circuit-output wires of a Boolean circuit $C_f$. Denote by $I_{C_f, S}$ the set of circuit-input wires of a circuit where a subset of parties $S \subset [n]$ provides input to the circuit. We assume w.l.o.g. that ${\mathcal {A}}$ is a deterministic adversary, which receives as additional input a random tape that determines its internal coin tosses. Upon receiving ${\mathcal {A}}$’s input $(1^\kappa ,A,C_f)$ and output $(\{\lambda _w\}_{w\in O_{C_f}},\{k_{v,0}^j, k_{v,1}^j\}_{j\in A, v\in W}, \{\lambda _u\}_{u\in I_{C_f,A}})$, $\mathcal{S}$ incorporates $\mathcal{A}$ and internally emulates an execution of the honest parties running $\varPi _{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ with the adversary $\mathcal{A}$.

• 1. Circuit-input wires’ masks and keys: For every circuit-input wire u and for $j \in A$, $\mathcal{S}$ samples from $P_j$’s random tape the wire mask shares $\lambda _u^j$ and the keys $k^j_{u,0}, k^j_{u,1}$ that party is meant to obtain from ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$. If a corrupted $P_j$ provides input to the circuit on a given wire u, $\mathcal{S}$ samples $\{\lambda _u^i\}_{i \notin A}$ such that $\bigoplus _{i \notin A}\lambda _u^i = \lambda _u \oplus \bigoplus _{j \in A}\lambda _u^j$, where the value $\lambda _u$ was received from ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$. If it is a honest party providing input on u, $\mathcal{S}$ samples $\{\lambda _u^i\}_{i \notin A}$ uniformly at random.

• 2. Intermediate wires’ masks and keys: Passing topologically through the gates g of the circuit:

  • For $j \in A$: If $g \in \mathsf {AND}$, $\mathcal{S}$ samples $\lambda _w^j \in \{0,1\}$ from $P_j$’s random tape. If $g \in \mathsf {SPLIT}$, it sets $\lambda _x^j = \lambda _w^j$ for both output wires $x = u, v$. If $g \in \mathsf {XOR}$, it sets $\lambda _w^j=\bigoplus _{x \in I} \lambda _x^j$.

  • For $j \notin A$: If $g \in \mathsf {AND}$, $\mathcal{S}$ samples $\lambda _w^i$. If $g \in \mathsf {SPLIT}$, it sets $\lambda _x^i = \lambda _w^i$ for both output wires $x = u, v$. If $g \in \mathsf {XOR}$, it sets $\lambda _w^i=\bigoplus _{x \in I} \lambda _x^i$.

  • If x is a circuit-output wire, the simulator adjusts the value $\lambda _x \in \{0,1\}$ that ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ sends to the parties to be $\lambda _x = \bigoplus _{i \notin A}\lambda _x^i \oplus \bigoplus _{j \in A}\lambda _x^j$.

• 3. Garble gates: For each $g \in \mathsf {AND}\cup \mathsf {SPLIT}$:

  • If $g \in \mathsf {AND}$, let $u_g, v_g$ be its input wires and $w_g$ its output wire. $\mathcal{S}$ emulates ${\mathcal {F}}_{\scriptstyle \mathrm {Bit \times Bit}}$ by sampling shares $z_g^j$ from $P_j$’s random tape, for $j \in A$, and setting random $z_g^i$ for $i \notin A$ such that $\sum _{i \in [n]} z^i_g = \lambda _{u_g} \cdot \lambda _{v_g}$, where $\lambda _{u_g}, \lambda _{v_g}$ were obtained from ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$. $\mathcal{S}$ has now all the values to compute shares of $\chi _{g,a,b}$ as $\chi ^i_{g,a,b} = a \cdot b \oplus b \cdot \lambda ^i_{u_g} \oplus a \cdot \lambda ^i_{v_g} \oplus z_g^i \oplus \lambda ^i_{w_g}$ for $i \in [n]$. For $j\in [n]$, $\mathcal{S}$ emulates three calls to ${\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}^{{\ell _{\scriptscriptstyle \mathrm {BMR}}}}(P_j)$ with inputs $\{\chi ^i_{g,0,0}, \chi ^i_{g,0,1}, \chi ^i_{g,1,0}\}$ from every $P_i$ and additional input $R_g^j$ from $P_j$, where $R_g^j = k_{w_g,0}^j \oplus k_{w_g,1}^j$. In each of these emulated calls and for $i \in A$, it computes the corrupted parties’ output shares from $P_i$’s random tape, while for $i \notin A$ it samples random shares that sum to each of the values $R_g^j \cdot \chi _{g,0,0}$, $R_g^j \cdot \chi _{g,0,1}$ and $R_g^j \cdot \chi _{g,1,0}$ as required.

  • If $g \in \mathsf {SPLIT}$, $\mathcal{S}$ emulates twice ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}^{2n{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ by computing shares $s_0^i, s_1^i$ from $P_i$’s random tape for $i \in A$ and setting $s_0^j, s_1^j$ for $j \notin A$ such that $\bigoplus _{i\in [n]}s_c^i = 0$ for $c \in \{0,1\}$.

  Setting the $\rho$ and $\tilde{g}$ values is local computation.

• 4. Reveal input/output wires’ masks: For every circuit-output wire w, $\mathcal{S}$ adds values $\lambda _w^i$, $i \notin A$ (previously computed in Step 2) to the view of each $P_j$, $j \in A$. For every circuit-input wire u on which a $P_j$, $j \in A$, provides input, $\mathcal{S}$ adds the $\{\lambda _u^i\}_{i \notin A}$ values it previously computed in Step 1 to $P_j$’s view.

• 5. Open Garbling: Using the adversary’s output $\{\tilde{g}\}_{g \in \mathsf {AND}\cup \mathsf {SPLIT}}$, $\mathcal{S}$ proceeds as follows: If $1 \in A$, it plays the role of each $P_j$, for $j \notin A$, and sends to $P_1$ the shares $\{\tilde{g}^j\}_{g \in \mathsf {AND}\cup \mathsf {SPLIT}}$ that it previously computed. Otherwise, the simulator plays the role of $P_1$ by sending $\{\tilde{g}\}_{g \in \mathsf {AND}\cup \mathsf {SPLIT}}$ to each $P_i, i \in A$.

5.4.2 Indistinguishability

The wire keys and the (circuit-input and circuit-output) wire masks output by the functionality ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ are i.i.d. uniformly random variables in the real world too. In both worlds and for the additional simulated values, the corrupted parties’ shares for the wire masks, the bit products (${\mathcal {F}}_{\scriptstyle \mathrm {Bit \times Bit}}$ functionality) and bit/string products (${\mathcal {F}}_{\scriptstyle \mathrm {Bit\times String}}^{{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ functionality) needed to garble AND gates are fixed by ${\mathcal {A}}$’s random tape, while the honest parties’ shares of the same values are uniformly random additive shares. In particular, this implies that shares $\tilde{g}^i_{a,b}$ of garbled AND gates are uniformly random additive shares in both executions. The same applies to shares of garbled splitter gates, due to the use of the ${\mathcal {F}}_{\scriptstyle \mathrm {Zero}}^{2n{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ functionality in the real world. Regarding the Open Garbling step, if $1 \notin A$ the reconstructed garbled circuit is identically distributed in both worlds. Else, if $1 \in A$, the adversary gets additive shares of the garbled circuit both in the real and simulated executions, as we argued.

Finally, the distribution of the variables corresponding to additive shares, on the one hand, and that of the i.i.d. variables, on the other hand, guarantees that the joint output of all parties, together with the simulated/real view of corrupted parties, are identically distributed in both worlds. More formally, let $\texttt {output}^\pi ({\varvec{x}},\kappa )$ (resp. $f({\varvec{x}})$) be the output of $\varPi _{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ (resp. ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$) on input ${\varvec{x}}\in \{0,1\}^*$ from all parties and security parameter $\kappa$. Let $\texttt {view}_A^\pi ({\varvec{x}},\kappa )$ (resp. $f_A({\varvec{x}})$) be the restriction of these outputs to the set of corrupted parties A. We just proved that:

$$\begin{aligned} \{(\mathcal{S}(1^\kappa ,{\varvec{x}},f_A({\varvec{x}})),f({\varvec{x}}))\}_{{\varvec{x}},\kappa ,A} \approx \{(\texttt {view}_A^\pi ({\varvec{x}},\kappa ),\texttt {output}^\pi ({\varvec{x}},\kappa ))\}_{{\varvec{x}},\kappa ,A}. \end{aligned}$$

$\square$

5.5 The Online Phase

Fig. 14

Online phase of the constant-round MPC protocol

We present the online phase of our protocol for multi-party garbled circuits with short keys in Fig. 14. Given the previous description of the garbling phase, the online phase is quite straightforward, where upon reconstructing the garbled circuit and obtaining all input keys, the evaluation process is similar to [20]. As in that work, all parties run the evaluation algorithm, which in our case involves each party computing just 2n hash evaluations per gate. During evaluation, the parties only see the randomly masked wire values, which we call “public values”, and cannot determine the actual values being computed. Upon completion, the parties obtain the actual output using the output wire masks revealed from ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$. The security of the protocol reduces to the $\mathsf {DRSD}_{r,h,{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ problem, where ${\ell _{\scriptscriptstyle \mathrm {BMR}}}$ is the key length, h is the number of honest parties, and r is twice the output length of the function ${\mathsf {H}}$ (sampled by the CRS).

We remark that in practice, we may want to implement the random function ${\mathsf {H}}$ in the CRS using fixed-key AES in the ideal cipher model, as is common for garbling schemes based on free-XOR. In Appendix C.2, we show that this reduces the number of AES calls from $O(n^2)$ in previous BMR protocols to $O(n^2 {\ell _{\scriptscriptstyle \mathrm {BMR}}}/ \kappa )$.

We conclude with the following theorem

Theorem 5.3

Let f be an n-party functionality $\{0,1\}^{n\kappa }\mapsto \{0,1\}^\kappa$ and assume that the $\mathsf {DRSD}_{2r,h,{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ assumption (cf. Definition 3.3) holds, where $r=n{\ell _{\scriptscriptstyle \mathrm {BMR}}}+ 1$. Then, Protocol $\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ from Fig. 14 UC-securely computes f in the presence of a static honest-but-curious adversary corrupting $t=n-h$ parties in the ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$-hybrid model.

Proof

We reduce security of the protocol to the extended double-key decisional-RSD problem (Definition 3.11) with parameters $(r,h,\ell )$, where $r := n{\ell _{\scriptscriptstyle \mathrm {BMR}}}+1$. By Lemma 3.12, this is reducible to $\mathsf {DRSD}_{2r,h,\ell }$.

Let $\mathcal{A}$ be a PPT adversary corrupting a subset of parties $A\subset [n]$ such that $|A | = n - h$. We prove that there exists a PPT simulator $\mathcal{S}$, with access to an ideal functionality $\mathcal{F}$ that implements f, which simulates the adversary’s view. The simulator fixes the CRS as a random $2n\cdot 2^{\ell _{\scriptscriptstyle \mathrm {BMR}}}\times 2^{n{\ell _{\scriptscriptstyle \mathrm {BMR}}}+1}$ matrix. A key $k_w$ for wire w is denoted as an active key if it is observed by the adversary upon evaluating the garbled circuit. The remaining hidden key is denoted as an inactive key. An active path is the set of all active keys that are observed throughout the garbled circuit evaluation.

Denoting the set of honest parties by ${\bar{A}}$, our simulator $\mathcal{S}$ is defined below.

5.5.1 The Description of the Simulation

• 1. Initialization. Upon receiving the adversary’s input $(1^\kappa ,A,{\varvec{x}}_A)$ and output ${\varvec{y}}$, $\mathcal{S}$ samples a i.i.d uniformly random tapes $r_i$ for each $i \in A$, incorporates $\mathcal{A}$ and internally emulates an execution of the honest parties running $\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ with the adversary $\mathcal{A}$. When we say that $\mathcal{S}$ chooses a value for some corrupted party, we mean that it samples the value from that party’s random tape $r_i$.

• 2. Preprocessing. $\mathcal{S}$ obtains the adversary’s input $C_f$ which is a Boolean circuit that computes f with a set of wires W and a set of G gates, and emulates ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$, as follows:

  • For every XOR gate g and $i \in A$, the simulator samples $\varDelta _g^i \in \{0,1\}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$.

  • For every input wire u, the simulator chooses a random bit $\varLambda _u \in \{0,1\}$ and, for every $i\in {\bar{A}}$, an active key $k^i_{u,\varLambda _u}\in \{0,1\}^{{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$. Additionally, it chooses a key $k^i_{u,0}\in \{0,1\}^{{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$ for every $i\in A$. Finally, and also for $i\in A$, if u is input to a XOR gate $g'$ it sets $k^i_{u,1} = k^i_{u,0} \oplus \varDelta _{g'}^i$, otherwise it samples $k^i_{u,1}\in \{0,1\}^{{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$.

  The simulator continues the emulation of the garbling phase by computing an active path of the garbled circuit that corresponds to the sequence of keys which will be observed by the adversary. Importantly, $\mathcal{S}$ never samples the inactive keys $k^i_{u,{\bar{\varLambda }}_u},k^i_{v,{\bar{\varLambda }}_v}$ and $k^i_{w,{\bar{\varLambda }}_w}$ for $i\in {\bar{A}}$ in order to generate the garbled circuit.

  • Active path generation of XOR gates. For every XOR gate g with input a set of wires I and an output wire w,

    • ${\mathcal {S}}$ sets $\varLambda _w = \bigoplus _{x \in I} \varLambda _{x}$.

    • Next, for $i\in A$ it sets $k^i_{w,0} = \bigoplus _{x \in I} k^i_{x,0}$ and $k^i_{w,1} = k^i_{w,0} \oplus \varDelta _g^i$.

    • Finally, for $i\in \bar{A}$ the simulator sets $k^i_{w,\varLambda _w} = \bigoplus _{x \in I} k^i_{x,\varLambda _x}$.

  • Active path generation of AND gates. For every AND gate g with input wires $I=\{u,v\}$ and an output wire w, ${\mathcal {S}}$ samples a random $\varLambda _w\in \{0,1\}$ and honestly generates the entry in row $(\varLambda _u,\varLambda _v)$, where $\varLambda _u$ (resp. $\varLambda _v$) is the public value associated with the left (resp. right) input wire to g. Namely, the simulator computes

    $$\begin{aligned} {\tilde{g}}_{\varLambda _u,\varLambda _v} = \left( \bigoplus _{i=1}^n {\mathsf {H}}(i,\varLambda _v,k^i_{u,\varLambda _u})\oplus {\mathsf {H}}(i,\varLambda _u,k^i_{v,\varLambda _v})\right) \oplus (\varLambda _w, k^1_{w,\varLambda _w},\ldots , k^n_{w,\varLambda _w}). \end{aligned}$$

    The remaining three rows are sampled uniformly at random from $\{0,1\}^{n{\ell _{\scriptscriptstyle \mathrm {BMR}}}+1}$.

  • Active path generation of splitter gates. For every splitter gate g with an input wire $I=\{w\}$ and output wires $O=\{u,v\}$, ${\mathcal {S}}$ sets $\varLambda _x=\varLambda _w$ for every $x\in O$ and honestly generates the entry in row $\varLambda _w$, where $\varLambda _w$ is the public value associated with the input wire to g. Namely, the simulator computes

    $$\begin{aligned} {\tilde{g}}_{\varLambda _w}= & {} \left( \bigoplus _{i=1}^n {\mathsf {H}}'(i,0,k^i_{w,\varLambda _w}), \bigoplus _{i=1}^n {\mathsf {H}}'(i,1,k^i_{w,\varLambda _w})\right) \\&\oplus \left( k^1_{u,\varLambda _u}, \ldots , k^n_{u,\varLambda _u}, k^1_{v,\varLambda _v}, \ldots , k^n_{v,\varLambda _v}\right) . \end{aligned}$$

    The remaining row is sampled uniformly at random from $\{0,1\}^{2n{\ell _{\scriptscriptstyle \mathrm {BMR}}}}$.

  • Setting the translation table. For every output wire $w\in W$ returning the ith bit of ${\varvec{y}}$, the simulator sets $\lambda _w=\varLambda _w\oplus y_i$. For all input wires $w \in W''$ that are associated with the ith bit of ${\varvec{x}}_A$ (the adversary’s input), the simulator sets $\lambda _w=\varLambda _w\oplus {\varvec{x}}_{A,i}$. The simulator forwards the adversary the $\lambda _w$ value for every output wire $w\in W$ and every circuit-input wire $w \in W''$ associated with a corrupted party. It completes the emulation of ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ by adding the complete garbled circuit to the view of each corrupted party.

• 3. Online computation. In the online computation, the simulator adds to the view of every corrupted parity the public values $\{\varLambda _w\}_{w\in W'}$ that are associated with the honest parties’ input wires $W'$. The simulator adds the honest parties’ input keys $\{k^i_{w,\varLambda _w}\}_{i\in {\bar{A}}, w\in W'}$ to the view of each corrupted party.

This concludes the description of the simulation. Note that the difference between the simulated and the real executions is regarding the way the garbled circuit is generated. More concretely, the simulated garbled gates include a single row that is properly produced, whereas the remaining three rows are picked at random. Let ${\mathbf {HYB}}^{{\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}}_{\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}},\mathcal{A},\mathcal{Z}}(1^\kappa ,z)$ denote the output distribution of the adversary $\mathcal{A}$ and honest parties in a real execution using $\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ with adversary $\mathcal{A}$. Moreover, let $\mathbf {IDEAL}_{\mathcal{F},\mathcal{S},\mathcal{Z}}(1^\kappa ,z)$ denote the output distribution of $\mathcal{S}$ and the honest parties in an ideal execution.

We prove that the ideal and real executions are indistinguishable. $\square$

Lemma 5.4

The following two distributions are computationally indistinguishable:

• $\{{\mathbf {HYB}}^{{\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}}_{\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}},\mathcal{A},\mathcal{Z}}(1^\kappa ,z)\}_{\kappa \in {\mathbb {N}},z \in \{0,1\}^*}$

• $\{\mathbf {IDEAL}_{\mathcal{F},\mathcal{S},\mathcal{Z}}(1^\kappa ,z)\}_{\kappa \in {\mathbb {N}},z \in \{0,1\}^*}$

Proof

We begin by defining a slightly modified simulated execution $\widetilde{\mathbf {HYB}}$, where the generation of the garbled circuit is modified so that upon receiving the parties’ inputs $\{\delta ^i\}_{i\in [n]}$ the simulator $\widetilde{{\mathcal {S}}}$ first evaluates the circuit $C_f$, computing the actual bit $\delta _w$ to be transferred via wire w for all $w\in W$, where W is the set of wires of $C_f$. It then chooses wire mask shares and wire keys as in the description of functionality ${\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$ from Fig. 7. Finally, $\widetilde{{\mathcal {S}}}$ fixes the active key for each wire $w\in W$ to be $(k_{w,\delta _w\oplus \lambda _w}^1,\ldots ,k_{w,\delta _w\oplus \lambda _w}^n)$. The rest of this hybrid is identical to the simulation. This hybrid execution is needed in order to construct a distinguisher for the Extended Double-Key RSD assumption.

Let $\widetilde{\mathbf {HYB}}^{{\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}}_{\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}},\mathcal{A}}(1^\kappa ,z)$ denote the output distribution of the adversary $\mathcal{A}$ and honest parties in this game. It is simple to verify that the adversary’s views in $\widetilde{\mathbf {HYB}}$ and $\mathbf {IDEAL}$ are identical, as in both cases the garbling of each gate includes just a single row that is correctly garbled and the public value associated with each wire w is independent of ${\ell _{\scriptscriptstyle \mathrm {BMR}}}_w$.

Our proof of the lemma follows by a reduction to the Extended Double-Key RSD hardness assumption (cf. Definition 3.11). Assume by contradiction the existence of an environment $\mathcal{Z}$, an adversary $\mathcal{A}$ and a non-negligible function $p(\cdot )$ such that

$$\begin{aligned} \big |\Pr [\mathcal{Z}({\mathbf {HYB}}^{{\mathcal {F}}_{\scriptstyle \mathrm {Preprocessing}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}}_{\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}},\mathcal{A},\mathcal{Z}}(1^\kappa ,z))=1] - \Pr [\mathcal{Z}(\widetilde{\mathbf {HYB}}_{\varPi _{\scriptstyle \mathrm {BMR}}^{\ell _{\scriptscriptstyle \mathrm {BMR}}},\mathcal{A},\mathcal{Z}}(1^\kappa ,z))=1] \big |\ge \frac{1}{p(\kappa )} \end{aligned}$$

for infinitely many $\kappa$’s where the probability is taken over the randomness of $\mathcal{Z}$ as well as the randomness for choosing the $\varLambda$ values and the keys. Then, we construct a PPT distinguisher $\mathcal{D}$ for the Extended Double-Key RSD assumption that distinguishes between an instance of the form

$$\begin{aligned} \left( {\mathsf {H}}, \bigoplus _{i \in {\bar{A}}} {\mathsf {H}}(i,0, k_{i}), \bigoplus _{i \in {\bar{A}}} {\mathsf {H}}(i,0, k_{i}'), \bigoplus _{i \in {\bar{A}}} {\mathsf {H}}(i,1, k_{i}), \bigoplus _{i \in {\bar{A}}} {\mathsf {H}}(i,1, k_{i}')\right) \end{aligned}$$

and five random elements, for some subset ${\bar{A}}$ of [n] of size h (that corresponds to the set of honest parties) with probability at least $\frac{1}{p(\kappa )\cdot |C|}$ via a sequence of hybrid games $\{{\mathbf {HYB}}_i\}_{i\in [|C|]}$, where $C = \mathsf {SPLIT}\cup \mathsf {AND}$. In more details, we define hybrid ${\mathbf {HYB}}_i$ as a hybrid execution with a simulator $\mathcal{S}_i$ that garbles the circuit as follows. The first i gates in the topological order are garbled as in the simulation, whereas the remaining $|C|-i$ gates are garbled as in the real execution. Note that ${\mathbf {HYB}}_0$ is distributed as hybrid ${\mathbf {HYB}}$ and that ${\mathbf {HYB}}_{|C|}$ is distributed as $\widetilde{\mathbf {HYB}}$. Therefore, if ${\mathbf {HYB}}$ and $\widetilde{\mathbf {HYB}}$ are distinguishable with probability $\frac{1}{p(\kappa )}$, then there exists $\tau \in [|C|]$ such that hybrids ${\mathbf {HYB}}_{\tau -1}$ and ${\mathbf {HYB}}_{\tau }$ are distinguishable with probability at least $\frac{1}{p(\kappa )\cdot |C|}$. Next, we formally describe our reduction to the Extended Double-Key RSD hardness assumption. Upon receiving a tuple $({\mathsf {H}},\widetilde{{\mathsf {H}}}_0,\widetilde{{\mathsf {H}}}'_0,\widetilde{{\mathsf {H}}}_1,\widetilde{{\mathsf {H}}}'_1)$ that is distributed according to the first or the second distribution, a subset ${\bar{A}}$ of [n] that denotes the set of honest parties, an index $\tau$ and the environment’s input z, distinguisher $\mathcal{D}$ internally invokes $\mathcal{Z}$ and simulator $\mathcal{S}$. In more details,

• $\mathcal{D}$ internally invokes $\mathcal{Z}$ that fixes the honest parties’ inputs $\varvec{\rho }$.

• $\mathcal{D}$ emulates the communication with the adversary (controlled by $\mathcal{Z}$) in the initialization, preprocessing and garbling steps as in the simulation with $\mathcal{S}$.

• For each wire u, let $\delta _u\in \{0,1\}$ be the actual value on wire u. Note that these values, as well as the output of the computation y, can be determined since $\mathcal{D}$ knows the actual input of all parties to the circuit.

• For each wire u in the circuit and $i\in A$, $\mathcal{D}$ chooses a pair of keys $k_{u,0}^i,k_{u,1}^i\in \{0,1\}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$, whereas for all $i\in {\bar{A}}$ it samples a random key $k_{u,\varLambda _u}^i\in \{0,1\}^{\ell _{\scriptscriptstyle \mathrm {BMR}}}$. $\mathcal{D}$ further fixes the public value $\varLambda _u=\lambda _u\oplus \delta _u$.

• $\mathcal{D}$ then garbles the circuit as follows.

  • For every $g_j\in \mathsf {AND}$ with input wires u and v and output wire w, $\mathcal{D}$ continues as follows. If $j<\tau$, then $\mathcal{D}$ garbles $g_j$ exactly as in the simulation with $\widetilde{{\mathcal {S}}}$. If $j=\tau$, then $\mathcal{D}$ first honestly computes the $(\varLambda _u,\varLambda _v)$-th row by fixing

    $$\begin{aligned} \begin{aligned} {\tilde{g}}_{\varLambda _u,\varLambda _v} =&\left( \bigoplus _{i=1}^n {\mathsf {H}}(i,\varLambda _v,k^i_{u,\varLambda _u}) \oplus {\mathsf {H}}(i,\varLambda _u,k^i_{v,\varLambda _v}) \right) \oplus (c, k^1_{w,\varLambda _w}, \ldots , k^n_{w,\varLambda _w}) \end{aligned} \end{aligned}$$

    where $c = \varLambda _w$.

    Next, $\mathcal{D}$ samples an inactive key $k_{w,{\bar{\varLambda }}_w}^i$ for all $i\in {\bar{A}}$ and fixes the remaining three rows as follows.

    $$\begin{aligned} \begin{aligned} {\tilde{g}}_{\varLambda _u,{\bar{\varLambda }}_v} =&\left( \bigoplus _{i=1}^n{\mathsf {H}}(i,{\bar{\varLambda }}_v,k^i_{u,\varLambda _u})\oplus \bigg (\bigoplus _{i\in A} {\mathsf {H}}(i,\varLambda _u,k^i_{v,{\bar{\varLambda }}_v})\bigg )\oplus \widetilde{{\mathsf {H}}}'_{\varLambda _u} \right) \\&\oplus (c, k^1_{w,c}, \ldots , k^n_{w,c}), \quad \text { where } \ c = \varLambda _u \cdot {\bar{\varLambda }}_v \oplus \varLambda _w \oplus \delta _w \\ {\tilde{g}}_{ {\bar{\varLambda }}_u,\varLambda _v} =&\left( \bigoplus _{i\in A} {\mathsf {H}}(i,\varLambda _{v},k^i_{u, {\bar{\varLambda }}_u}) \oplus \widetilde{{\mathsf {H}}}_{\varLambda _v} \oplus \bigg (\bigoplus _{i=1}^n{\mathsf {H}}(i, {\bar{\varLambda }}_u,k^i_{v,\varLambda _v})\bigg )\right) \\&\oplus (c, k^1_{w,c}, \ldots , k^n_{w,c}), \quad \text { where } \ c = {\bar{\varLambda }}_u \cdot \varLambda _v \oplus \varLambda _w \oplus \delta _w\\ {\tilde{g}}_{ {\bar{\varLambda }}_u,{ {\bar{\varLambda }}_v}} =&\left( \bigoplus _{i\in A} {\mathsf {H}}(i, {\bar{\varLambda }}_{v},k^i_{u, {\bar{\varLambda }}_u})\oplus \widetilde{{\mathsf {H}}}_{ {\bar{\varLambda }}_v} \oplus \bigg (\bigoplus _{i\in A} {\mathsf {H}}(i, {\bar{\varLambda }}_u,k^i_{v, {\bar{\varLambda }}_v})\bigg ) \oplus \widetilde{{\mathsf {H}}}'_{ {\bar{\varLambda }}_u} \right) \\&\oplus (c, k^1_{w,c}, \ldots , k^n_{w,c}), \quad \text { where } \ c = {\bar{\varLambda }}_u \cdot {\bar{\varLambda }}_v \oplus \varLambda _w \oplus \delta _w. \end{aligned} \end{aligned}$$

    Finally, if $j>\tau$, then $\mathcal{D}$ garbles $g_j$ exactly as in hybrid ${\mathbf {HYB}}$. For that, $\mathcal{D}$ needs to know both active and inactive keys. It therefore chooses the inactive keys that are associated with the input and output wires of this gate for $i \in \bar{A}$, in order to be able to complete the garbling. Recall that the circuit is with fan-out 1. Therefore, the distinguisher can choose the inactive key for the input wire of this gate (as it was not used as an input wire to gate $g_\tau$).

  • For every $g_j\in \mathsf {SPLIT}$ with input wire w and output wires u, v, $\mathcal{D}$ completes the garbling as follows. If $j<\tau$, then $\mathcal{D}$ garbles $g_j$ exactly as in the simulation with $\widetilde{{\mathcal {S}}}$. If $j=\tau$, then $\mathcal{D}$ first honestly computes the $\varLambda _w$th row by fixing

    $$\begin{aligned} \begin{aligned} {\tilde{g}}_{\varLambda _w} =&\left( \bigoplus _{i=1}^n {\mathsf {H}}(i,0,k^i_{w,\varLambda _w}) \oplus {\mathsf {H}}(i,1,k^i_{w,\varLambda _w}) \right) \oplus (k^1_{u,\varLambda _u}, \ldots , k^n_{v,\varLambda _v}). \end{aligned} \end{aligned}$$

    Next, it samples inactive keys $k_{u,{\bar{\varLambda }}{\bar{\varLambda }}_u}^i,k_{v,{\bar{\varLambda }}_v}^i$ for all $i\in {\bar{A}}$ and fixes the remaining row as follows.

    $$\begin{aligned} \begin{aligned} {\tilde{g}}_{{\bar{\varLambda }}_w} =&\left( \bigoplus _{i\in A} {\mathsf {H}}(i,0,k^i_{w,{\bar{\varLambda }}_w}) \oplus \widetilde{{\mathsf {H}}}_0 \oplus \bigoplus _{i\in A} {\mathsf {H}}(i,1,k^i_{w,{\bar{\varLambda }}_w}) \oplus \widetilde{{\mathsf {H}}}_1\right) \oplus (k^1_{u,{\bar{\varLambda }}_u}, \ldots , k^n_{v,{\bar{\varLambda }}_v}).\\ \end{aligned} \end{aligned}$$

    If $j>\tau$, then $\mathcal{D}$ garbles $g_j$ as in hybrid ${\mathbf {HYB}}$ using a similar process as for the case of an AND gate.

• This concludes the description of the reduction. Note that the set $\mathsf {XOR}$ need not be part of these hybrids since we do not send any garbling information for this set of gates. $\mathcal{D}$ hands the adversary the complete description of the garbled circuit and concludes the execution as in the simulation with $\widetilde{{\mathcal {S}}}$.

• $\mathcal{D}$ outputs whatever $\mathcal{Z}$ does.

Note first that if $(\widetilde{{\mathsf {H}}}_0,\widetilde{{\mathsf {H}}}'_0,\widetilde{{\mathsf {H}}}_1,\widetilde{{\mathsf {H}}}'_1)$ are truly uniform, then the view generated by $\mathcal{D}$ is distributed as in ${\mathbf {HYB}}_\tau$. This is because only the active path is created as in the real execution, whereas the remaining rows are sampled uniformly at random from the appropriate domain. On the other hand, if this tuple is generated according to the following distribution

$$\begin{aligned} \left( {\mathsf {H}}, \bigoplus _{i \in A} {\mathsf {H}}(i,0, k_{i}), \bigoplus _{i \in A} {\mathsf {H}}(i,0, k_{i}'), \bigoplus _{i \in A} {\mathsf {H}}(i,1, k_{i}), \bigoplus _{i \in A} {\mathsf {H}}(i,1, k_{i}')\right) \quad \end{aligned}$$

then this emulates game ${\mathbf {HYB}}_{\tau -1}$, since each tuple element emulates an evaluation of the hash values for the honest parties on the secret keys.

This completes the proof. $\square$

6 Complexity Analysis and Implementation Results

We now compare the complexity of the most relevant aspects of our approach to the state-of-the-art prior results in semi-honest MPC protocols with dishonest majority. To demonstrate the practicality of our approach, we also present implementation results for the online evaluation phase of our BMR-based protocol.

6.1 Threshold Variants of Full-Threshold Protocols

Since the standard GMW and BMR-based protocols allow for up to $n-1$ corruptions, we also show how to modify previous protocols to support some threshold t and compare our protocols with these variants. The method is very simple (and similar to the use of committees in our protocols), but does not seem to have been explicitly mentioned in the previous literature. To evaluate a circuit C, all parties first secret-share their inputs to an arbitrarily chosen committee $\mathcal {P'}$, of size $t+1$. Committee $\mathcal {P'}$ runs the full-threshold protocol for a modified circuit $C'$, which takes all the shares as input, and first XORs them together so that it computes the same function as C. The committee $\mathcal {P'}$ then sends the output to all parties in ${\mathcal {P}}$. The complexity of the threshold-t variant of a full-threshold protocol, $\varPi$, is then essentially the same as running $\varPi$ between $t+1$ parties instead of n.

6.2 Concrete Hardness of RSD and Our Choice of Parameters

In this section, we give an overview of how we select the key length $\ell$ in our protocols according to n, h, r, so that the corresponding $\mathsf {RSD}_{r,h,\ell }$ instance is hard enough. See “Appendix B” for a more detailed survey of known attacks and the techniques involved. As discussed in Sect. 3, RSD is similar to the (standard) syndrome decoding problem, where each component of the error vector is 0 or 1 with some constant probability, which is equivalent to the problem of learning parity with noise (LPN).

The most efficient attacks on RSD are Information Set Decoding (ISD), introduced by Prange in 1962 [64], Wagner’s Generalised Birthday Attack (GBA) [71], and the Linearization Attack (LA) by Bellare et al. [18] and Saarinen [65]. We stress that the goal of our analysis is to find a reasonable estimation of the complexity of these attacks; giving a complete description of all possible decoding techniques and a precise evaluation of their cost is out of the scope of this paper. In our analysis, we intentionally underestimate the complexity of all the attacks, resulting in a conservative estimate of the security of our protocols.

When considering the hardness of RSD instances, we need to distinguish the case where the solution to the problem is unique and the case of multiple solutions. In the first case, which always occurs for our BMR-style protocols, GBA essentially reduces to the classical birthday attack and the most efficient attack is ISD. Classical information set decoding algorithms do not take into account the possibility that the solution is regular. In practice, when we estimate the cost of this attack, we consider the cost of both a tailored regular variant of ISD, augmented with the Stern [67] and Finiasz and Sendrier [36] techniques, and the more recent non-regular variant due to Becker et al. [12], and then, we take the minimum of the two. We have also analysed more recent variants of ISD [19, 57]. More precisely, the values in the tables are obtained by considering all the cost analysis performed in Sect. B and computing the key-values corresponding to the most efficient attack according to Eqs. 3, 5, 7, 9 and 10.

In Table 1, we provide an estimation of the minimal key-length $\ell$ for our BMR-style protocols to achieve more than 128 bits of security for different values of n, h and $r=2\ell n +2$. Note that we only consider $\ell \le 32$, so when in the table we have that $\ell$ should be larger than 32, it means that ISD cost less than $2^{128}$ for that set of parameters. We also give an estimation of minimal key-length respect to the plain ISD attack to RSD by Prange.

Table 1 Min key-length for BMR-style MPC with 128 bits of security for different n and h when $r=2\ell n+2$

When an RSD instance has more than one solution—this is sometimes the case for our GMW-style protocol—we need to consider also GBA and LA. Notice that since there are many solutions, attacking regular SD with classical ISD is more difficult than attacking non-regular SD and an adversary needs to run the attack repeatedly until the output is regular, increasing the cost of the attack. To estimate the complexity of GBA and LA, we take the same conservative approach we use for ISD. Since LA is particularly effective for larger h, especially when $h > r/4$, we always set up $r > 2h +1$.

Table 2 Min key-length for GMW-style MPC with 128 bits of security for different n and h

Table 3 Amortized communication cost (in kbit) of producing a single triple in GMW for different values of n and h

In Table 2, we propose a set of parameters for our GMW-style protocols for different values of h (and irrespective to the total number of parties n), such that the estimated complexity of the most efficient decoding algorithms is more than $2^{128}$.

6.3 GMW-Style Protocol

Recall that the relevant parameters are the key-length $\ell$, the number of honest parties h, and the parameter r which is the batch size when producing triples; we fix the computational and statistical security parameters to $\kappa =128$ and $s=40$. We instantiate our protocol with two variants, depending on how the hash functions ${\mathsf {H}}_i$ are defined:

• “DRSD” variant (Sect. 4.2): ${\mathsf {H}}_i$ are uniformly random. Security is either based on the DRSD assumption, with $\ell$ and r taken from Table 2, or statistically secure when $h \ge r + s$ with $\ell =1$.

• “Vandermonde” variant (Sect. 4.3): ${\mathsf {H}}_i$ come from a Vandermonde matrix. Perfect security, key length $\ell = \log _2 n$, and $r = \ell \cdot h$.

In both cases, the communication complexity is $n_1 \cdot n_2 \cdot (\ell + \ell \kappa /r +1)$ bits per triple.

For comparison, we use the best-known instantiation of standard GMW, namely a variant based on 1-out-of-4 OT to generate triples, optimized by [31] in the 2-party setting. This easily extends to the multi-party case with communication complexity $O(n^2\kappa /\log {\kappa })$ bits per AND gate, so we consider both full-threshold and threshold-t (§6.1) variants.

Table 3 and Fig. 15 show the amortized communication complexity for triple production using deterministic committees for different values of n and honest parties h. We can see that the Vandermonde approach always wins for small values of (n, h); when $n > 80$ and $h > 30$, then the DRSD technique performs better. Our protocol starts to beat the best-known GMW protocol for producing multiplication triples when there are just 4 honest parties. For example, with 15 parties and 6 corruptions, the communication cost of our protocol is roughly 35% lower than threshold-6 GMW, and 82% lower than the cost of standard, full threshold GMW. As the number of parties (and honest parties) grows, our improvements become even greater, and when the number of honest parties is more than 80, we can use 1-bit keys and improve upon the threshold variant of GMW by more than 13 times.

Fig. 15

Amortized communication cost (in kbit) for producing triples in GMW for $n=20,50,80,100,150,400$ and deterministic committees

Table 4 Amortized communication cost (in kbit) of producing a single triple in GMW using random committees

Table 5 Communication complexity for garbling, and size of garbled gates, in BMR-style protocols in kbit

In Sect. 4, we mentioned the possibility, when n and h are large enough, of using random committees ${{\mathcal {P}}}_{(h)}$ and ${{\mathcal {P}}}_{(1)}$, such that except with negligible probability ${{\mathcal {P}}}_{(h)}$ has at least $h' \le h$ honest parties and ${{\mathcal {P}}}_{(1)}$ has at least one honest party. In order to estimate the communication complexity of our protocol, we consider the probability $p_{(1)}$ of ${{\mathcal {P}}}_{(1)}$ not having a single honest party and the probability $p_{(h)}$ of ${{\mathcal {P}}}_{(h)}$ of having less than $h'$ honest parties. Let $n_1=|{{\mathcal {P}}}_{(1)} |$ and $n_h=|{{\mathcal {P}}}_{(h)} |$, we have that

$$\begin{aligned} p_{(1)}= \frac{\left( {\begin{array}{c}n-h\\ n_1\end{array}}\right) }{\left( {\begin{array}{c}n\\ n_1\end{array}}\right) } \quad {\text { and }} \quad p_{(h)}= \frac{\sum _{j=1}^{\min (h',h'-v)} \left( {\begin{array}{c}n-h\\ n_h-h'+j\end{array}}\right) \cdot \left( {\begin{array}{c}h\\ h'-j\end{array}}\right) }{\left( {\begin{array}{c}n\\ n_h\end{array}}\right) },\end{aligned}$$

where $v = n_h-(n-h) < h'$. We fix the parameters $n,h,h'$ and compute the minimum values $n_h, n_1$ such that $p_{(h)}$ and $p_{(1)}$ are less than $2^{-s}$. Table 4 compares our protocol with random committees and GMW with a single random committee of size $n_1$, i.e. having at least one honest party with overwhelming probability, when $s=40$. Even if the communication complexity reduces in both protocols, our approach is always at least 50% more efficient compared to GMW.

6.4 BMR-Style Protocol

6.4.1 Communication Complexity

To show the efficiency of our constant-round garbling protocol from Sect. 5.5, we provide Table 5, which has two parts. First, it compares the amortized communication complexity incurred for garbling an AND gate with [14]. We recall that this is the dominating cost for BMR-style protocols using free-XOR, and that we incur no communication for creating shares of garbled splitter gates. Note that in the first setting of $n=20,t=10$, although our communication costs are around 3 times lower than [14], we do not improve upon the threshold-t variant of that protocol, described earlier. Once we get to 50 parties, though, we start to improve upon [14], with a reduction in communication going up to $7{\times }$ for 400 parties and $10{\times }$ for 1000 parties.

The second half of the table shows the size of the garbled circuit in terms of the total number of AND, XOR and splitter gates. Garbled circuit size only has a slight impact on communication complexity, when opening the garbled circuit, which is much lower than the communication in the rest of the garbling phase. However, if an implementation needs to store the entire garbled circuit in memory (either for evaluation, or storage for later use), then it is also important to optimize its size. Here, we also compare with [15], which recently showed how to construct a compact multi-party garbled circuit based on key-homomorphic PRFs. The size of their garbled circuit is constant and grows with $O(\kappa )$ per gate, with security proven in the presence of $n-1$ corrupted parties. On the other hand, their construction requires much more expensive operations based on the Decisional Diffie–Hellman or Ring-LWE assumptions, and these also lead to fairly large keys—with a 3072-bit discrete log prime (equivalent to 128-bit security) the size of a garbled AND gate only beats our protocol at around 400 parties. Additionally, their construction does not support free-XOR, and the concrete efficiency of the offline garbling phase is not clear: garbling an AND gate requires O(n) secret-shared field multiplications, which seems likely to be much higher than the offline cost of our protocol or [14], but their paper does not give concrete numbers. In Fig. 16, we show the communication complexity of garbling when $n=100, 500$ and for different number of honest parties.

We conclude by remarking that known GC-based protocols in the malicious setting naturally incur in much higher communication costs, even if the online running times are overall comparable with those reported in [14]. The most efficient maliciously-secure multiparty GC-based protocol [74] requires roughly $\kappa \cdot A \cdot (4n-6)$ and $7\kappa \cdot A \cdot (n-1)$ bits per party for the garbling and the function independent step, respectively (as in Table 5, A denotes the number of AND gates and $\kappa$ the security parameter).

Fig. 16

Communication complexity cost (in kbit) for garbling when $n=100$ and $n=500$

6.4.2 Garbling Implementation

In Fig. 17, we present running times for evaluating the garbled circuit in our protocol and compare with times for [14] running on the same machine.

Fig. 17

Online time for evaluating various circuits with $n=30,50,100,300$. The corresponding numbers of honest parties are $h=14,21,38,105$, respectively. Times for [14] are for a full-threshold implementation

The implementation runs on a single machine,⁵ to allow testing just the local computation in the online phase (note that there is very little interaction in the online phase). We took as benchmarks the AES circuit (6800 AND gates, 31,796 Splitters), the SHA-256 circuit (90,825 AND gates, 132,586 Splitters), a binary multiplier for 32-bit numbers (5926 AND gates, 6994 Splitters) and a randomly generated circuit with 100,000 AND gates and 99,510 Splitters (as used in [15], for comparison). The CRS ${\mathsf {H}}$ was implemented with fixed-key AES in counter mode using AES-NI instructions, which is a random function under the assumption that AES behaves like a random permutation (see Appendix C). We also tried precomputing every output of ${\mathsf {H}}$ and storing this as a lookup-table, but in practice this did not perform well as the table size was usually much larger than the CPU cache. Recall that the standard BMR online phase requires each party to perform $O(n^2)$ AES operations per AND gate, whereas our online phase reduces this to $O(n^2 {\ell _{\scriptscriptstyle \mathrm {BMR}}}/\kappa )$, with some extra cost for evaluating splitter gates. The results show that for the random circuit our protocol starts to pay off from around 50 parties, when the corruption threshold is between 20–40%, reaching a $3.3{\times }$ improvement for $n=300,h=105$. On the other hand, for AES, which has a relatively large proportion of splitter gates, the crossover point is closer to 150 parties, and the greatest improvement factor is $1.3{\times }$ over [14] for $n=300,h=105$.

This shows that the performance improvements of our garbled circuit-based protocol very much depend on the specific circuit being evaluated, but further improvements may be possible by modifying secure computation compilers to produce circuits more suitable for our protocol. It also seems likely that implementing our GMW-based protocol would show much more significant gains, based on the communication costs presented earlier.

Appendices

Universal Composability

We prove security of our protocols in the universal composability (UC) framework [24] (see also [28] for a simplified version of UC). This framework is based on the real/ideal paradigm, where all the entities (including the parties and the adversary) are modeled as interactive Turing machines. The goal of a protocol is defined by an ideal functionality, which can be seen as a trusted party sending the desired results to the parties. To prove security of a protocol, we aim to show that any adversary attacking the real protocol can be used to construct a corresponding ideal adversary, called the simulator, that runs in the ideal world, interacting only with the functionality $\mathcal{F}$ and the real adversary, such that the distributions of messages seen in the real world and ideal world executions are indistinguishable. The UC framework additionally defines a powerful entity called the environment, which is the interactive machine trying to distinguish the two worlds. The environment has total control over the adversary and can choose the inputs, and see the outputs, of all parties.

We denote by $\mathbf {REAL}_{\pi ,\mathcal{A},{\mathcal {Z}}}(1^\kappa ,z)$ the output distribution of the environment ${\mathcal {Z}}$ in the real-world execution of protocol $\pi$, with n parties and an adversary ${\mathcal {A}}$, where $\kappa$ is the security parameter and z is the auxiliary input to ${\mathcal {Z}}$. The output distribution of ${\mathcal {Z}}$ in the ideal world is denoted by $\mathbf {IDEAL}_{\mathcal{F},\mathcal{S},{\mathcal {Z}}}(1^\kappa ,z)$, where $\mathcal{F}$ is the ideal functionality to be realized and $\mathcal{S}$ is the simulator. Additionally, we denote the hybrid execution of a protocol $\pi$, which is given access to an ideal functionality $\mathcal{G}$, by ${\mathbf {HYB}}^{{\mathcal {G}}}_{\pi ,\mathcal{A},{\mathcal {Z}}}(1^\kappa ,z)$. This is defined similarly to the real execution and is known as the $\mathcal{G}$-hybrid model. Security of a protocol is then defined as follows.

Definition A.1

A protocol $\pi$ UC-securely computes an ideal functionality $\mathcal{F}$ in the $\mathcal{G}$-hybrid model if for any PPT adversary ${\mathcal {A}}$, there exists a PPT simulator ${\mathcal {S}}$ such that for any PPT environment ${\mathcal {Z}}$, it holds that:

$$\begin{aligned} {\mathbf {HYB}}^{\mathcal{G}}_{\pi ,\mathcal{A},{\mathcal {Z}}} {\mathop {\approx }\limits ^{\mathrm{c}}}\mathbf {IDEAL}_{\mathcal{F},\mathcal{S},{\mathcal {Z}}}. \end{aligned}$$

The composition theorem provides security guarantees when protocols are composed together. This means that if $\rho$ is a UC-secure protocol for $\mathcal{G}$, then the protocol $\pi$ in the $\mathcal{G}$-hybrid model can be replaced by the composition $\pi \circ \rho$. Informally, the composition theorem then guarantees that $\mathbf {REAL}_{\pi \circ \rho , \mathcal{A}, {\mathcal {Z}}}$ is indistinguishable from ${\mathbf {HYB}}^{\mathcal{G}}_{\pi ,\mathcal{A},{\mathcal {Z}}}$.

Cryptanalysis

In this section, we give a concrete analysis of the hardness of the Syndrome Decoding Problem (SD) and Regular Syndrome Decoding Problem (RSD) described in Sect. 3, in order to justify the parameters selection for our protocols. Let us start by providing useful notation on coding theory. For ease of presentation, all vectors are intended to be column vectors.

A binary $[m,k,d]_2$ linear code C is a k-dimensional subspace of ${\mathbb {F}}_2^m$, where m is the length of the code, k is its dimension as a vector subspace and d is its distance, i.e. the minimal nonzero Hamming distance between any two codewords. Equivalently, C can be defined as the kernel of a full-rank matrix ${\mathbf {H}}\in {\mathbb {F}}_2^{( m-k) \times m}$, called a parity-check matrix of C. Given a vector ${\varvec{r}}= {\varvec{c}}+ {\varvec{e}}\in {\mathbb {F}}_2^m$, where ${\varvec{c}}\in C$ is a codeword and ${\varvec{e}}$ an error vector, the syndrome corresponding to ${\varvec{c}}$ is the vector ${\varvec{s}}= {\mathbf {H}}\cdot {\varvec{r}}= {\mathbf {H}}\cdot {\varvec{c}}+ {\mathbf {H}}\cdot {\varvec{e}}= {\mathbf {H}}\cdot {\varvec{e}}\in {\mathbb {F}}_2^{m-k}$. Hence, the syndrome does not depend on the codeword, but only on the error vector. When the Hamming weight of ${\varvec{e}}$ is smaller than the error correction capability of C, that is $\mathsf {wt}({\varvec{e}}) \le \lfloor \frac{d-1}{2} \rfloor$, ${\varvec{s}}$ is called correctable syndrome and ${\varvec{r}}$ can be uniquely decoded to ${\varvec{c}}$. More formally, we can define a mapping

$$\begin{aligned} \mathsf {Syn}: {\mathbb {F}}_2^m&\longrightarrow {\mathbb {F}}_2^r (r = m-k)\\ {\varvec{e}}&\longmapsto {\mathbf {H}}\cdot {\varvec{e}}(= {\varvec{s}}). \end{aligned}$$

When the domain of $\mathsf {Syn}$ is restricted to vectors of upper bounded Hamming weight, inverting $\mathsf {Syn}$ is strictly related to the problem of decoding the $[m,k,d]_2$ linear code with parity-check matrix ${\mathbf {H}}$, and this problem is equivalent to the average-case hardness of the following computational problem.

Definition B.1

(Syndrome Decoding Problem (SD)) Let $r, h, m \in {\mathbb {N}}$. Sample ${\mathbf {H}}\leftarrow {\mathbb {F}}_2^{r \times m}$ and ${\varvec{e}}\leftarrow {\mathbb {F}}_2^m$ such that $\mathsf {wt}({\varvec{e}}) = h$, where $\mathsf {wt}({\varvec{e}})$ denotes the Hamming weight of ${\varvec{e}}$. Given $({\mathbf {H}}, {\mathbf {H}}\cdot {\varvec{e}})$, the $\mathsf {SD}_{r, m, h}$ problem is to recover ${\varvec{e}}$ with noticeable probability.

Notice SD can be seen as a purely combinatorial problem and the most näive algorithm could simply enumerate all the $\left( {\begin{array}{c}m\\ h\end{array}}\right)$ possible solutions.

We denote by $W_{m,h}$ the set of all the binary vectors in ${\mathbb {F}}_2^m$ of weight exactly h and by $R_{m,h} \subset W_{m,h}$ the set of all the binary (m, h)-regular vectors. We recall that a binary (m, h)-regular vector is a vector in ${\mathbb {F}}_2^m$ such that, if we divide it into h blocks of equal length, each of them has Hamming weight exactly 1. When SD is restricted to vectors in $R_{m,h}$, we have the following.

Definition B.2

(Regular Syndrome Decoding (RSD)) Let $r, h,\ell \in {\mathbb {N}}$ and $m = h \cdot 2^\ell$. Sample ${\mathbf {H}}\leftarrow {\mathbb {F}}_2^{r \times m}$ and ${\varvec{e}}\leftarrow R_{m,h}$. Given $({\mathbf {H}}, {\mathbf {H}}\cdot {\varvec{e}})$, the $\mathsf {RSD}_{r,h,\ell }$ problem is to recover ${\varvec{e}}$ with noticeable probability.

This problem was introduced in 2003 by Augot et al. [4], who used it for the SHA-3 candidate FSB (Fast Syndrome-Based) hash function. As for SD, RSD can be seen as a combinatorial problem and solved by enumerating all the $(m/h)^h$ possible solutions. The most efficient attacks against SD and RSD are Information Set Decoding (ISD), Generalised Birthday Attack (GBA) and Linearization Attack (LA). To establish which attack is the most efficient, we need to distinguish different cases depending on the choice of h. Clearly, the number of errors affect the practical security of SD and RSD. In coding theory, the values of h usually considered are those corresponding to a single solution of the problem, which happens with high probability if the number of errors h is smaller than the Gilbert–Varshamov distance $d_{GV}$.⁶ In cryptography, there is no restriction on h as long as SD or RSD remain hard. In practice, when $h \le d_{GV}$, ISD is always the most efficient attack and has roughly the same cost when considering SD and RSD; when $h > d_{GV}$ the best attack is either ISD or GBA. Furthermore, when considering the regular case, the intuition is that if the solution to the problem is not unique, attacking RSD is even harder than attacking SD: having a smaller set of inputs decreases the number of possible solutions and thus increases the cost of the attacks. Finally, when h is larger, say $h > r/4$, the best attack is linearization.

In the rest of this section, we analyse all the most efficient attacks to SD and RSD.

1.1 Linearization Attack

This attack was described in [65] and is a generalisation of [18, Appendix A]. It is very efficient for h large, namely when $h > r/4$, and consists in finding linear relations between h columns of ${\mathbf {H}}$.

A description of this attack is given in Algorithm 1. As we are considering the RSD problem, we can assume that the matrix ${\mathbf {H}}$ consists of h blocks of $2^\ell$ columns, i.e. ${\mathbf {H}}=[{\mathbf {H}}_1 \mid \cdots \mid {\mathbf {H}}_h]$. The adversary chooses a parameter $\lambda \le r /h$ and h columns of ${\mathbf {H}}$, say ${\varvec{h}}^{a^0_1}, \ldots , {\varvec{h}}^{a^0_h}$, in such a way that only one column for each of the h blocks is chosen. Then, they compute $\varDelta = \sum _i {\varvec{h}}^{a^0_i} + {\varvec{s}}$ and, for each $j \in [\lambda ]$, choose a different set of h columns, ${\varvec{h}}^{a^j_1}, \ldots , {\varvec{h}}^{a^j_h}$, of ${\mathbf {H}}$. After that, using linear algebra, they look for linear relations $\sum _{i=1}^h \sum _{j=1}^{\lambda } \epsilon _i^j \cdot {\varvec{\delta }}_i^j = \varDelta$, with $\epsilon _i^i \in \{0,1\}$. As $\lambda \le r/w$, all the possible linear combinations of the elements in $\{{\varvec{\delta }}_i^j\}_{(i,j) \in [h]\times [\lambda ]}$ form a vector space of dimension $h \cdot \lambda \le r$ at most. Hence, the desired linear relation exists with probability $2^{h \lambda } / 2^r$. A relation is useful only with probability $((\lambda +1)/2^\lambda )^h$, as for each $i \in [h]$ it should involve at most one of the ${\varvec{\delta }}_i^j$ values. More concretely and for a fixed i, as each $\epsilon _i^j$ is set i.i.d. with probability 1/2, only $\lambda +1$ cases satisfy the restriction on the ${\varvec{\delta }}_i^j$ values, each of those cases having probability $1/2^\lambda$. Overall, this means that the expected number of iterations to find a useful relation is slightly above $\frac{2^r}{(\lambda +1)^{h}}$. When $h \le r/2\lambda$, it is possible to consider $2 \lambda$ generators, so that, using the same arguments as above, the probability of a useful relation is $(\lambda +1)^{2h}/2^r$. Summing up:

$$\begin{aligned} {\mathsf {C}}_{\mathsf {LA}} \ge {\left\{ \begin{array}{ll} \frac{2^r}{(\lambda +1)^h} \quad {\text { if }} \quad h \le r/\lambda \\ \frac{2^r}{(\lambda +1)^{2h}} \quad {\text { if }} \quad h \le r/2\lambda \end{array}\right. } \end{aligned}$$

(3)

1.2 Generalised Birthday Attack

This attack is named after the famous birthday paradox which permits to find collisions between two random lists much faster than checking every possible combinations. GBA improves the standard birthday paradox by looking for specific solutions and discarding the others, so it does not apply when a single solution to SD/RSD exists.

Formally, the Generalised Birthday Problem (GBP) can be stated as follows: given t lists $L_1, \ldots , L_{t}$, containing uniform random elements from ${\mathbb {F}}_2^r$, find exactly one element ${\varvec{h}}^i$ in each list $L_i$, $i \in [t]$, such that $\sum _{i \in [t]} {\varvec{h}}^i = 0$.

Note that in this definition the number of available vectors is unbounded, but when one considers $\mathsf {SD}_{r,m,h}$ or $\mathsf {RSD}_{r,h,\ell }$, only m different r-bit strings are available, that is the m columns of ${\mathbf {H}}$. Also, when the syndrome ${\varvec{s}}\ne 0$, we can simply subtract ${\varvec{s}}$ from each element of one list, say $L_1$, and proceed to find a combination of elements that sum up to zero as in GBP.

To solve GBP, Wagner proposed the so-called k-tree algorithm. It consists in a divide and conquer approach: at each step, it uses only two lists at time, performing a simple collision search. This procedure requires a large number of inputs and therefore more memory than the classic birthday algorithm. Minder et al. [59] extended the k-tree algorithm offering a solution which allows to balance time and memory efficiency of the attack. This technique was firstly applied to decoding problems by Coron and Joux [29] and then improved by [13, 48, 60].

For ease of exposition, we only consider the case $t=2^a$, however, the attack still works if this is not the case, only with a slight loss of efficiency. In Algorithm 2, we give a more detailed description of the algorithm, as described by Wagner. The algorithm starts by building $2^a$ lists of size $S=2^{\frac{r}{a+1}}$ and consists of a steps. Each element in a list is a vector in ${\mathbb {F}}_2^r$ and can be seen as a concatenation of $a+1$ elements in ${\mathbb {F}}_2^{\frac{r}{a+1}}$, so that each element ${\varvec{h}}$ in a list can be visualised as

$$\begin{aligned} \left( h_1,\ldots , h_{\frac{r}{a+1}} \Vert h_{\frac{r}{a+1}+1}, \ldots , h_{\frac{2r}{a+1}} \Vert h_{\frac{ar}{r+1}+1}, \ldots , h_{r}\right) . \end{aligned}$$

At each step, elements in these lists are pairwise merged so that the number of lists is halved. More precisely, at level 0, we start with $t=2^a$ lists $L_{0,0}, \ldots , L_{0,2^a-1}$ and from these we obtain $L_{1,0}, \ldots , L_{1,2^a-2}$ by computing $L_{1,j}= L_{0,2j}+L_{0,2j+1}$ and considering only sums of vectors with the first block of $\frac{r}{a+1}$ coordinates equal to zero. Clearly, with this condition some possible solutions will be discarded, but it permits to maintain the size of the lists equal to S on average. Moreover, those zero coordinates are not considered in the next level. This operation is repeated until only 2 lists remain and a standard birthday technique can be applied to find a solution. Since this solution is the sum of $2^a$ elements from the original lists, it is also a solution for the GBP.

A first observation is that the last step, i.e. the standard birthday technique, will be successful as long as the size S of the lists satisfies $S^2 \ge 2^{r-(a-1)\log _2 S}$, that is $S \ge 2^{\frac{r}{a+1}}$. Therefore, if it is possible to build lists of size $S=2^{\frac{r}{a+1}}$, then the complexity of the algorithm can be lower bounded by $O(S \cdot \log _2 S)$. Now, if we use GBA to solve $\mathsf {SD}_{r,m,h}$ or $\mathsf {RSD}_{r,h,\ell }$, the size of the starting lists is bounded by the number of columns m of ${\mathbf {H}}$. As said above, the size S of these lists needs to verify $S \ge 2^{\frac{r}{a+1}}$, hence, assuming that the starting lists contain sums of $\frac{h}{2^a}$ columns of ${\mathbf {H}}$, we need:

$$\begin{aligned} \left( {\begin{array}{c}m\\ \frac{h}{2^a}\end{array}}\right) \ge 2^{\frac{r}{a+1}}. \end{aligned}$$

Moreover, we need the lists to contain different values, so it should be

$$\begin{aligned} \left( {\begin{array}{c}S\\ 2^a\end{array}}\right) \le \left( {\begin{array}{c}m\\ h\end{array}}\right) , \end{aligned}$$

from which we obtain:

$$\begin{aligned} \frac{2^a}{a+1} \le \frac{\log _2(\left( {\begin{array}{c}m\\ h\end{array}}\right) )}{r}. \end{aligned}$$

(4)

When the solutions are regular, each list is associated with $h/2^a$ blocks, each of weight 1, of ${\mathbf {H}}$ and S cannot be larger than the number of words of weight $h/2^a$. Since in each block there are m/h words of weight 1, then we need

$$\begin{aligned} S \le \Bigl (\frac{m}{h}\Bigr )^{h/2^{a}} \end{aligned}$$

and (4) becomes

$$\begin{aligned} \frac{2^a}{a+1} \le \frac{h}{r} \log _2\Bigl (\frac{m}{h}\Bigr ). \end{aligned}$$

(5)

When we consider security against GBA, we also take into account improvements due to Niebuhr et al. [60], Bernstein et al. [13] and Kirchner [48].

1.3 Information Set Decoding Attacks

Information Set Decoding (ISD) can be seen as a class of generic algorithms for solving SD for random linear codes. Here, we assume an SD (respectively, an RSD) instance with parameters (r, m, h), associated with the $[m,k=m-r]_2$ binary linear code with parity-check matrix ${\mathbf {H}}$. This decoding technique was introduced by Prange in 1962 [64] and later improved, by a polynomial factor, by Lee and Bricknell [52] and Leon [53]. In 1988, Stern [67] proposed an exponential improvement, followed by further improvements by Dumer [34], Finiasz and Sendrier [36] and Bernstein et al. [17]. In this section, we describe a common framework for different variants of ISD and analyse their complexity. We consider the Stern–Dumer variant, with the optimisation due to Finiasz and Sendrier [36], and also we take into account more recent variants, more precisely, those described by May et al. [56], Becker et al. [12] and May et al. [57].

The high level idea of these algorithms is to transform the original SD instance with parameters (r, m, h) into a related instance with smaller parameters $(r',m',h')$ and then try to find a solution of the original problem from a solution of the easier instance. ISD essentially applies linear algebra transformations to the parity-check matrix ${\mathbf {H}}$ in order to obtain a new structured matrix ${\mathbf {H}}'$, and reduce the space of solutions of the original SD instance. The overall idea of ISD is given in Algorithm 3.

The algorithm consists of three steps:

• 1. First pick a random $m \times m$ permutation matrix ${\mathbf {P}}$ (this is equivalent to choosing a uniform random subset of k columns of ${\mathbf {H}}$) and then performing a Gaussian elimination to get a structured matrix

  $$\begin{aligned} {\mathbf {H}}' = \left[ \begin{array}{c|c} \quad &{} {\mathbf {0}}_{q}\\ \quad {\mathbf {R}}\quad \quad &{} \quad \\ \quad \quad &{} \quad {\mathbf {I}}_{r-q} \quad \\ \end{array} \right] = \left[ \begin{array}{c|c} \quad \quad {\mathbf {R}}_1 \quad \quad \quad &{} \quad {\mathbf {0}}_{q} \quad \\ \hline \\ \quad \quad {\mathbf {R}}_2 \quad \quad \quad &{} \quad {\mathbf {I}}_{r-q} \quad \\ \quad &{} \\ \end{array} \right] , \quad {\mathbf {R}}\in {\mathbb {F}}_2^{r \times (k+q)}. \end{aligned}$$

  ${\mathbf {H}}'$ consists of two blocks of columns ${\mathcal {R}}=[1,k+q]$ and ${\mathcal {I}}=[k+q+1,m]$. Essentially, this step is equivalent to finding an invertible matrix ${\mathbf {U}}\in {\mathbb {F}}_2^{r \times r}$ such that ${\mathbf {H}}'={\mathbf {U}}{\mathbf {H}}{\mathbf {P}}$, and forces a $q \times (r-q)$ zero block in the first q rows in the second block of columns ${\mathcal {I}}$. Notice the multiplication by ${\mathbf {P}}$ permutes the columns of ${\mathbf {H}}$ and hence, the coordinates of ${\varvec{e}}$ so that ${\varvec{e}}' = P \cdot {\varvec{e}}$, and the multiplication by ${\mathbf {U}}$ permutes the coordinates of ${\varvec{s}}$, so that we get ${\varvec{s}}' = {\mathbf {U}}{\varvec{s}}= ({\varvec{s}}_1,{\varvec{s}}_2)$. We denote ${\varvec{e}}'=({\varvec{e}}_1,{\varvec{e}}_2)$, ${\varvec{e}}_1 \in {\mathbb {F}}_2^{k+q}, {\varvec{e}}_2 \in {\mathbb {F}}_2^{r-q}$.

• 2. Next, fix a weight $0 \le p \le h$, and consider the first slice $[{\mathbf {R}}_1 | {\mathbf {0}}_q]$ of ${\mathbf {H}}'$, containing the first q rows. Compute $\mathsf {SM}$, by creating a set of partial solutions E, that is a set of vectors ${\varvec{e}}_1 \in {\mathbb {F}}_2^{k \times q}$ s.t. $\mathsf {wt}({\varvec{e}}_1) = p$ and ${\mathbf {R}}_1 \cdot {\varvec{e}}_1 = {\varvec{s}}_1$.

• 3. Extend partial solutions obtained in the previous step by computing for each ${\varvec{e}}_1 \in E$ the vector ${\varvec{e}}_2={\mathbf {R}}_2 {\varvec{e}}_1 + {\varvec{s}}_2$. If $\mathsf {wt}({\varvec{e}}_2)=h-p$, then return ${\varvec{e}}'=({\varvec{e}}_1,{\varvec{e}}_2)$ and stop.

Note that this algorithm always outputs a correct solution:

$$\begin{aligned} {\mathbf {H}}'{\varvec{e}}' = \left[ \begin{array}{c|c} \quad \quad {\mathbf {R}}_1 \quad \quad \quad &{} \quad {\mathbf {0}}_{q} \quad \\ \hline \\ \quad \quad {\mathbf {R}}_2 \quad \quad \quad &{} \quad {\mathbf {I}}_{r-q} \quad \\ \quad &{} \\ \end{array} \right] \left[ \begin{array}{c} {\varvec{e}}_1\\ \quad \\ {\varvec{e}}_2 \end{array} \right] = \left[ \begin{array}{c} \quad {\mathbf {R}}_1 {\varvec{e}}_1 \quad \\ \quad {\mathbf {R}}_2 {\varvec{e}}_1 + {\varvec{e}}_2 \quad \\ \end{array} \right] =\left[ \begin{array}{c} {\varvec{s}}_1\\ \quad \\ {\varvec{s}}_2 \end{array} \right] = {\varvec{s}}', \end{aligned}$$

where ${\mathbf {H}}' {\varvec{e}}'= {\mathbf {U}}{\mathbf {H}}{\mathbf {P}}{\varvec{e}}' = {\mathbf {U}}{\mathbf {H}}{\varvec{e}}={\varvec{s}}' \Leftrightarrow {\mathbf {H}}{\varvec{e}}= {\mathbf {U}}^{-1}{\varvec{s}}' = {\varvec{s}}$ and $\mathsf {wt}({\varvec{e}})=\mathsf {wt}({\mathbf {P}}{\varvec{e}}')=h$. ISD contains two parameters: p, with $0 \le p \le h$, representing the number of errors in the selected $k+q$ columns, and q, $0 \le q \le r$, representing the coordinates where the error components are zero. The case $p=q=0$ corresponds to the plain information-set decoding algorithm due to Prange.

The main difference among different ISD variants, and also the main computational task of the algorithm, is the second step, where $\mathsf {SM}$ is performed. Here, the main problem is to find p columns of ${\mathbf {R}}_1$ that sum to ${\varvec{s}}_1$. More in particular, let ${\mathbf {R}}_1=[{\varvec{r}}_1^1, \ldots , {\varvec{r}}_1^{k + q}], {\varvec{r}}_1^j \in {\mathbb {F}}_2^q$, we have to find an index set ${\mathcal {J}} \subseteq {\mathcal {R}}$, with $|{\mathcal {J}}|=p$ and $\sum _{j \in {\mathcal {J}}} {\varvec{r}}_1^j = {\varvec{s}}_1$. This problem was called by May et al. [56] the submatrix matching problem (SM).

We are going to examine the cost of ISD depending on how the SM step is instantiated, considering both regular and non-regular syndrome decoding.

1.3.1 Complexity of ISD

We essentially follow and simplify the analysis done in [36, 44, 66, 68], but we also consider in more detail the regular case. We stress that our goal is to find a reasonable estimation of the complexity of recent ISD algorithms and that a detailed analysis of these algorithms and their cost is out of the scope of this paper.

To lower bound the cost, ${\mathsf {C}}_{\mathsf {ISD}}$, of the attack, we need to estimate the number, $\mathsf {NI}$, of iterations needed before the algorithm successfully stops. If we assume that those iterations are independent, then $\mathsf {NI}$ is simply the reciprocal of the success probability ${\mathsf {P}}$ of one iteration. In particular, when $h \le d_{GV}$, that is when the solution of SD/RSD is unique, $\mathsf {NI^{single}}= 1/{\mathsf {P}}$; when $h > d_{GV}$, $\mathsf {NI^{mult}}= 1/({\mathsf {P}}\cdot \mathsf {N\_Sol})$, where $\mathsf {N\_Sol}$ is the expected number of solutions. We have that $\mathsf {N\_Sol}= \frac{\left( {\begin{array}{c}m\\ h\end{array}}\right) }{2^r}$ in the non-regular case and $\mathsf {N\_Sol}^R= \frac{(m/h)^h}{2^r}$ for RSD.

Hence, an attack against SD will succeed if one finds an error $({\varvec{e}}_1,{\varvec{e}}_2)$ such that ${\varvec{e}}_1=p$ and ${\varvec{e}}_2=h-p$, which happens with probability

$$\begin{aligned} {\mathsf {P^{single}}}= \frac{\left( {\begin{array}{c}k+q\\ p\end{array}}\right) \cdot \left( {\begin{array}{c}r-q\\ h-p\end{array}}\right) }{\left( {\begin{array}{c}m\\ h\end{array}}\right) } \quad {\text { and }} \quad \mathsf {P^{mult}}= \frac{\left( {\begin{array}{c}k+q\\ p\end{array}}\right) \cdot \left( {\begin{array}{c}r-q\\ h-p\end{array}}\right) }{2^r}, \end{aligned}$$

where $\mathsf {P^{single}}$ and $\mathsf {P^{mult}}$ denote the success probability of one iteration when $h \le d_{GV}$ and $h > d_{GV}$, respectively.

Each iteration of ISD chooses $r-q$ columns of ${\mathbf {H}}$ and applies Gaussian elimination to obtain $I_{r-q}$. The cost of Gaussian elimination is essentially the same for all the different ISD variants. This cost can be reduced using for example the bit-swapping technique introduced by Omura (see [25]) and used in ISD by vanTilburg [70], Canteaut and Chabaud [26] and Canteaut and Sendrier [30]. A generalisation of bit-swapping is introduced by Bernstein et al. [16] which improves the balance between the cost of Gaussian Elimination and the cost of error-searching. The idea is that of starting a new iteration with the matrix ${\mathbf {H}}'$ from previous iteration and then, instead of choosing a new set of $r-q$ columns, reusing $r-q-t$ out of $r-q$ columns from previous iteration and selecting only t new columns randomly. In this way, only t columns need to be pivoted. However, as observed by Bernestein et al., small values of t introduce a dependence between iterations and require more iterations before the algorithm succeeds.

Analysing the impact of t in the algorithm is very difficult as the iterations are no more independent and the number of errors in the selected r columns is correlated with the number of errors in the columns selected in the next iteration. So, to estimate the cost of the algorithm, we should consider a Markov chain for the number of errors, as in [26]. For this reason, we assume the iterations to be independent and that this step approximately costs $(r-q)^3/\log _2(r-q)$ [1]. Also, we would like to remark that the cost of Gaussian elimination is most of the time negligible compared to other operations.

Next, we need to consider the number of expected iterations of ${\mathsf {Extend}}$. Following the same arguments as in [36, 68], we have that the probability of success is

$$\begin{aligned} \mathsf {P^{single}_{Success}}\approx \frac{2^q \cdot \left( {\begin{array}{c}r-q\\ h-p\end{array}}\right) }{\left( {\begin{array}{c}m\\ h\end{array}}\right) } \quad {\text { and }} \quad \mathsf {P^{mult}_{Success}}\approx \frac{2^q \cdot \left( {\begin{array}{c}r-q\\ h-p\end{array}}\right) }{2^r } \;.\ \end{aligned}$$

(6)

Putting everything together, the average cost of ISD is

$$\begin{aligned} {\mathsf {C}}_{\mathsf {ISD}} \approx \min _{p,q} \left\{ \frac{\min \left\{ 2^r, \left( {\begin{array}{c}m\\ h\end{array}}\right) \right\} }{\left( {\begin{array}{c}r-q\\ h-p\end{array}}\right) } \cdot \left( \frac{K_{\mathsf {Gauss}} + K_{\mathsf {SM}}}{\left( {\begin{array}{c}k+q\\ p\end{array}}\right) } + \frac{K_{\mathsf {Ext}}}{2^q} \right) \right\} , \end{aligned}$$

(7)

where $K_{\mathsf {SM}}$ and $K_{\mathsf {Ext}}$ denote the average cost in elementary binary operations of computing ${\mathsf {SM}}$ and ${\mathsf {Extend}}$, respectively, and both depend on the ISD variant. The impact of $K_{\mathsf {Ext}}$ on the cost of the attack is relative small, it is essentially the cost of testing ${\varvec{e}}_2 = {\mathbf {R}}_2 \cdot {\varvec{e}}_1 +{\varvec{s}}_2$ for ${\varvec{e}}_1 \in E$. If we consider the plain information set decoding described by Prange, we have $p=q=0$ and obtain:

$$\begin{aligned} C^{\mathsf {single}}_{\mathsf {ISD\_Pra}}> \frac{\left( {\begin{array}{c}m\\ h\end{array}}\right) }{\left( {\begin{array}{c}r\\ h\end{array}}\right) } \quad \quad C^{\mathsf {mult}}_{\mathsf {ISD\_Pra}} > \frac{2^r}{\left( {\begin{array}{c}r\\ h\end{array}}\right) } \quad \quad \end{aligned}$$

(8)

In Stern and Dumer’s algorithm, with Finiasz and Sendrier optimization, the submatrix matching problem is solved using a birthday collision search. More precisely, the first block of $k+q$ coordinates ${\mathcal {R}}$ is split in two disjoint sets ${\mathcal {R}}_1 = [1,\frac{k+q}{2}]$ and ${\mathcal {R}}_2 = [\frac{k+q}{2}+1,k+q]$ and then by using a birthday technique, one looks for two sets $I_1 \subset {\mathcal {R}}_1$ and $I_2 \subset {\mathcal {R}}_2$ of cardinality p/2 such that $\sum _{i \in I_1} {\varvec{r}}_2^i = \sum _{i \in I_2 } {\varvec{r}}_2^i + {\varvec{s}}_1$. Roughly, the initial lists have size $\left( {\begin{array}{c}(k+q)/2\\ p/2\end{array}}\right)$, so $K^{\mathsf {SD}}_{\mathsf {SM}} > \left( {\begin{array}{c}(k+q)/2\\ p/2\end{array}}\right)$. In 2012, May et al. [56] exponentially improved ISD by using the representation technique introduced by Howgrave-Graham and Joux [41] in the context of subset sum algorithms. We do not give further details of this ISD variant, but it uses four initial lists of size $\left( {\begin{array}{c}(k+q)/2\\ p/4\end{array}}\right)$, so $K^{\mathsf {ISD\_MMT}}_{\mathsf {SM}} > \left( {\begin{array}{c}(k+q)/4\\ p/4\end{array}}\right)$. In a further work of May et al. [12], the birthday decoding is replaced by an order 3 generalised birthday decoding with 8 initial lists of size larger that $\left( {\begin{array}{c}(k+q)/2\\ p/8\end{array}}\right)$. The algorithm described in a more recent work by May et al. [57] it is slightly different from previous variants. It has the same main loop with the Gaussian Elimination, then it starts the BJMM variants with 8 lists, but in the tree structure the last join is replaced by a “Nearest Neighbours” (NN) search. This technique provides a significant asymptotic advance, but the analysis hides a large factor and it does not lead to a significant practical improvement. Finally, we would like to mention a very recent work by Both and May [19], which uses the same approach of [12] and the power of NN search in each step of the algorithm, and not only in the last join like [57]. However, the practical impact of this new approach is still unclear and it leads to a significant asymptotic improvement compared to previous attacks only when the error rate is high, which is never the case in our protocol.

In practice to analyse the complexity of ISD, we use a lower bound on BJMM, simplifying the analysis done in [44]. Notice that in our construction we are mostly interested in solving $\mathsf {RSD}_{r,h,\ell }$ with $m=2^\ell \cdot h$. To estimate the cost of attacking RSD with ISD, we first consider the case $p=q=0$. In this case, an attacker can choose a different strategy: here, the error ${\varvec{e}}$ is regular, so it can be decomposed in h blocks with m/h components and only one error for each block, hence to maximise the probability of success when choosing the first k coordinates, the adversary should choose the same number of positions k/h from each block. This means that they take k/h coordinates out of m/h. Given that only 1 of these is different from 0, the probability of ending up with an error ${\varvec{e}}' = ({\varvec{e}}_1,{\varvec{e}}_2)$ with $\mathsf {wt}({\varvec{e}}_1) =0$ and $\mathsf {wt}({\varvec{e}}_2) = h$ is:

$$\begin{aligned} {\mathsf {P}}^{0,0,{\mathsf {single}}}=&\Pr (\{{\varvec{e}}=({\varvec{e}}_1,{\varvec{e}}_2) \in R_{m,h} \mid \mathsf {wt}({\varvec{e}}_1)=0, \mathsf {wt}({\varvec{e}}_2)=h\})\\ =&\Biggl (\frac{\left( {\begin{array}{c}(m/h) -1\\ k/h\end{array}}\right) }{\left( {\begin{array}{c}m/h\\ k/h\end{array}}\right) }\Biggr )^h = \Bigl (\frac{r}{m}\Bigr )^h, \end{aligned}$$

which correspond to ${\mathsf {C}}^{R,\mathsf {single}}_{\mathsf {ISD\_Pra}}$, i.e. the cost of Prange’s algorithm for the regular case, and similarly, when the number of solutions is greater than one,

$$\begin{aligned} {\mathsf {P}}^{0,0,{\mathsf {mult}}} = \Bigl (\frac{r}{h}\Bigr )^h\cdot 2^{-r}, \end{aligned}$$

which, as before, correspond to ${\mathsf {C}}^{R,\mathsf {mult}}_{\mathsf {ISD\_Pra}}$ for the regular case. Note that this probability is smaller than for the SD, so finding a solution for RSD is harder. This strategy can be easily generalised to the case p, q different from zero. To solve RSD, the adversary could select the first block of $k+p$ coordinates as follows: take p blocks, i.e. $p \cdot m/h$ coordinates, and then fill the remaining $(k+q) - p \cdot m/h$ coordinates by following the same strategy as before, i.e. take the same number of positions a from each remaining block, where

$$\begin{aligned} a = \frac{(k + q) - p \cdot m/h}{h-p} . \end{aligned}$$

Notice we are assuming $k+q \le p \cdot m/h$ and a integers. There are $h-p$ remaining blocks, each with m/h components of which only one is nonzero; therefore, the above probability becomes

$$\begin{aligned} \mathsf {P^{R,single}}= \left( {\begin{array}{c}h\\ p\end{array}}\right) \cdot \Biggl ( \frac{\left( {\begin{array}{c}(m/h) -1\\ a\end{array}}\right) }{\left( {\begin{array}{c}m/h\\ a\end{array}}\right) }\Biggr )^{h-p} = \left( {\begin{array}{c}h\\ p\end{array}}\right) \cdot \Bigl (\frac{h\cdot (r-q)}{m \cdot (h-p)} \Bigr )^{h-p}. \end{aligned}$$

(9)

and

$$\begin{aligned} \mathsf {P^{R,mult}}=\left( {\begin{array}{c}h\\ p\end{array}}\right) \cdot \Bigl ( \frac{r-q}{h-p} \Bigr )^{h-p} \cdot \Bigl (\frac{m}{h}\Bigr )^p \cdot 2^{-r}. \end{aligned}$$

(10)

Notice these are exactly ${\mathsf {P}}^{0,0}$ when $p=q=0$. Similarly to the case of non-regular SD, we can compute ${\mathsf {C}}^R_{\mathsf {ISD}}$. For our parameters selection, we consider an estimation of the cost of both this regular variant, associated with the Stern [67] and Finiasz and Sendrier [36] techniques, and the more recent non-regular BJMM variant, and then, we take the minimum of the two. It would be very interesting to apply more recent techniques to the regular case, but this is out of the scope of this paper. It is worth noting that all the improved ISD variants come at the price of much larger space complexity, which is usually completely ignored in the cost analysis of these algorithms, but plays a significant role in practical applications. For this reason, Prange’s plain information set decoding still achieves the best time-space complexity product. However, for our parameter selection, as we already said, we consider a lower bound on the cost of BJMM and a special regular-case tailored SD variant, taking into account exclusively the average number of operations and ignoring the memory cost of the algorithm.

Additional Material for Efficiency Analysis

1.1 BMR Preprocessing: Communication Complexity

Here, we detail how we compared our communication complexity with that of the best previous passively secure BMR protocol, namely [14]. To simplify the comparison, we exclude the communication related to input and output wires. Given a circuit $C_f$ with X XOR gates and A AND gates, each of them with fan-in-two and arbitrary fan-out, [14] has the following communication costs:

• 1. One bit multiplication and 3n bit-string multiplications per AND gate, where the strings have length $\kappa$. A bit multiplication requires $n(n-1)$ bit-OTs, each of which involves sending $128+2$ bits if instantiated with [46] or 84 bits if instantiated with [49]. Each of the bit-string multiplication can be computed using $n-1$ correlated OTs, at a cost of $128+128$ bits each.

• 2. Each AND gate has size $4n\kappa$ bits, and each party has a share of it. If the circuit is reconstructed by every party sending her share to $P_1$, and then $P_1$ broadcasting the addition of every share, the cost of putting an AND gate together is $8n(n-1)\kappa$ bits.

This gives a total cost of $(130 + 768 + 8 \kappa ) \cdot n \cdot (n-1) \cdot A = 1922 \cdot n \cdot (n-1) \cdot A$ bits for the [46] instantiation and $(67 + 768 + 8 \kappa ) \cdot n \cdot (n-1) \cdot A = 1876 \cdot n \cdot (n-1) \cdot A$ when using [31] instead. In our work, the costs are:

• 1. One bit multiplication and 3n bit/string multiplications per AND gate, where the strings have length $\ell$. When implemented with our improved GMW protocol with deterministic committees, these cost $(n-h+1)(n-1)({\ell _{\scriptscriptstyle \mathrm {OT}}}+ {\ell _{\scriptscriptstyle \mathrm {OT}}}\kappa /r +1)$ bits and $n(n-1){\ell _{\scriptscriptstyle \mathrm {BMR}}}({\ell _{\scriptscriptstyle \mathrm {OT}}}+ {\ell _{\scriptscriptstyle \mathrm {OT}}}\kappa / r + 1)$ bits, respectively.

• 2. Each AND gate has size $4\cdot (n\ell + 1)$ bits. Each Splitter gate has size $4n\ell$ bits.

1.2 Instantiating the CRS

Our protocols require a CRS, which is a randomly sampled function, ${\mathsf {H}}$. One way of implementing this would be generate the function in a setup phase (e.g. with coin-tossing) and store it as a lookup table. However, when the table grows large this will have a prohibitive impact on performance, as there will likely be many cache misses when reading from ${\mathsf {H}}$ at random locations. A more efficient alternative is to implement ${\mathsf {H}}$ using fixed-key AES, which offers fast performance on modern CPUs with AES hardware instructions. This gives security in the ideal cipher model, where fixed-key AES is modelled as a random permutation.⁷

Depending on which of our two protocols is used, this method works as follows:

• For GMW, ${\mathsf {H}}$ is a 1-bit output hash function, so we can simply truncate the AES output.

• For our BMR-style protocol, we need to expand the input to $n\cdot \ell + 1$ bits. Let $B = \lceil (n\cdot \ell + 1)/128 \rceil$ be the number of AES blocks needed to generate one hash output. The parties first fix a random key $s \leftarrow \{0,1\}^{128}$ and then define:

  $$\begin{aligned} {\mathsf {H}}(i, b, k) = (\mathsf {AES}_s(i \Vert b \Vert k \Vert 0), \ldots , \mathsf {AES}_s(i \Vert b \Vert k \Vert B-1)), \end{aligned}$$

  where the last block is truncated so that the total output length is $n\cdot {\ell _{\scriptscriptstyle \mathrm {BMR}}}+1$ bits.

  The cost of a single call to ${\mathsf {H}}$ is that of B AES operations.