Honest Majority GOD MPC with $O(\textsf{depth}(C))$ Rounds and Low Online Communication

Abstract

In the context of secure multiparty computation (MPC) protocols with guaranteed output delivery (GOD) for the honest majority setting, the state-of-the-art in terms of communication is the work of (Goyal et al. CRYPTO’20), which communicates O(n|C|) field elements, where |C| is the size of the circuit being computed and n is the number of parties. Their round complexity, as usual in secret-sharing based MPC, is proportional to $O(\textsf{depth}(C))$, but only in the optimistic case where there is no cheating. Under attack, the number of rounds can increase to $\varOmega (n^2)$ before honest parties receive output, which is undesired for shallow circuits with $\textsf{depth}(C)\ll n^2$. In contrast, other protocols that only require $O(\textsf{depth}(C))$ rounds even in the worst case exist, but the state-of-the-art from (Choudhury and Patra, Transactions on Information Theory, 2017) still requires $\varOmega (n^4|C|)$ communication in the offline phase, and $\varOmega (n^3|C|)$ in the online (for both point-to-point and broadcast channels). We see there exists a tension between efficient communication and number of rounds. For reference, the recent work of (Abraham et al., EUROCRYPT’23) shows that for perfect security and $t<n/3$, protocols with both linear communication and $O(\textsf{depth}(C))$ rounds exist.

We address this state of affairs by presenting a novel honest majority GOD protocol that maintains $O(\textsf{depth}(C))$ rounds, even under attack, while improving over the communication of the most efficient protocol in this setting by Choudhury and Patra. More precisely, our protocol has point-to-point (P2P) online communication of O(n|C|), accompanied by O(n|C|) broadcasted (BC) elements, while the offline has $O(n^3|C|)$ P2P communication with $O(n^3|C|)$ BC. This improves over the previous best result, and reduces the tension between communication and round complexity. Our protocol is achieved via a careful use of packed secret-sharing in order to improve the communication of existing verifiable secret-sharing approaches, although at the expense of weakening their robust guarantees: reconstruction of shared values may fail, but only if the adversary gives away the identities of many corrupt parties. We show that this less powerful notion is still useful for MPC, and we use this as a core building block in our construction. Using this weaker VSS, we adapt the recent secure-with-abort Turbopack protocol (Escudero et al. CCS’22) to the GOD setting without significantly sacrificing in efficiency.

1 Introduction

Secure multiparty computation, or MPC for short, is a set of tools that enable a set of parties $P_1,\ldots ,P_n$, each $P_i$ holding an input $x_i$, to compute any function $y = f(x_1,\ldots ,x_n)$ while revealing only the output y. This holds even if an adversary corrupts t out of the n parties, and if the protocol is what is known as actively secure, then security holds even if the corrupt parties deviate arbitrarily from the protocol execution. A particularly interesting setting, which is the focus of this work, is the honest majority case where it is assumed that $t<n/2$, that is, the adversary only corrupts a minority of the parties. In this case, the strong property of guaranteed output delivery (G.O.D.) can be achieved, which ensures the honest parties receive the output y in spite of any malicious behavior by the corrupt parties. Furthermore, if one is willing to assume the existence of a broadcast channel, the whole protocol can be made unconditionally secure, meaning it is resistant against unbounded adversaries and it only has a negligible amount of error. This is in contrast to security with abort, which ensures privacy but may not guarantee output provision.

G.O.D. is the strongest security notion for MPC and very important in practice as it removes all problems with deciding who failed if the protocol aborts. Hence, optimizing the efficiency of G.O.D. protocols has been a topic of study in recent literature. First, as usual in MPC, let us model the computation to be carried out as an arithmetic circuit C over a large-enough finite field $\mathbb {F}$. Let us begin by discussing the case in which $t<n/3$, which is weaker than honest majority $t<n/2$ as it tolerates less corruptions. Earlier works such as BGW [7] and (concurrently) [9] show that G.O.D. is possible for $t<n/3$ with perfect security, having a communication complexity (measured in the total number of field elements) of $O(n^4|C|)$. Several follow-up works were devoted to improving the communication. Towards such goal, [19] introduces the player elimination framework, which reduces communication to $O(n^3|C|)$, and building on top of this framework, the works of [6, 17] get linear communication O(n|C|). Unfortunately, the number of rounds—which is also an important metric directly related to end-to-end performance—of protocols based on player elimination is proportional to $O(\textsf{depth}(C))$, but only in the optimistic case where there is no cheating. When the corrupt parties misbehave, the protocol enters a “recovery state” and eventually resumes after a previous “checkpoint”. This process can happen $\varOmega (n)$ times, and overall it adds $\varOmega (n)$ rounds to the round-count, which is particularly impactful when $\textsf{depth}(|C|) = o(n)$. For high latency settings such as wide area networks this can drastically affect the performance of the protocol. Studying the communication of $t<n/3$ MPC with $O(\textsf{depth}(C))$ rounds (independently of n, even in the worst case) has been a topic of study of recent works: [1] achieved $O(n^3|C|)$ communication, and the recent work of [2] lowered it to O(n|C|), matching (asymptotically) that of the previous state-of-the-art [6, 17], but crucially, without paying any additive overhead in n on the number of rounds.

The above discussion is for the $t<n/3$ setting, which is considerably easier than the $n/3<t< n/2$ regime. For $t<n/2$, it is known that G.O.D. is possible assuming a broadcast channel, and the early work by Rabin and Ben-Or [24] achieved $O(\textsf{depth}(C))$ rounds even in the worst case, but it is very expensive in terms of communication. For instance, its communication is higher than that of [11], which is $O(n^5|C|) + O(n^3)\times \textsf{BC}$, where the term multiplying the $\textsf{BC}$ denotes the number of elements sent over the broadcast channel. The work of [11] however has a number of rounds that, in the worst case, can become $O(n\cdot \textsf{depth}(C))$. In the last two decades several subsequent works approached the task of improving communication [5, 8, 18], culminating in the current state-of-the-art by Goyal, Song, and Zhu [18], which has $O(n|C| + O(n^3)\times \textsf{BC})$ communication. All these works require $O(\textsf{depth}(|C|))$ rounds in the optimistic case, but in case of cheating, the “recovery state” adds not only $\varOmega (n)$, but $\varOmega (n^2)$ extra rounds,¹ which is extremely harmful for circuits with $\textsf{depth}(C)\ll n^2$. Currently, and unlike the $t<n/3$, removing this round-count overhead can only be done at the expense of increasing communication. Indeed, the most recent work exploring the task of $O(\textsf{depth}(C))$-round honest majority G.O.D. MPC is [10], which has a communication of $O(n^4|C|) + O(n^4|C|)\times \textsf{BC}$ in total, with an online phase of $O(n^3|C|) + O(n^3|C|)\times \textsf{BC}$.

Towards improving this state of affairs, recent work by Escudero and Fehr [14] presents an honest majority G.O.D. protocol that achieves $O(\textsf{depth}(C))$ rounds, independent of n, and simultaneously has linear communication $O(n|C|) + 0\times \textsf{BC}$. However, this is done in the preprocessing model where the parties are assumed to have certain correlated randomness independent of their inputs available for free. When instantiating this preprocessing with a protocol that has number of rounds independent of n—like the one from [10]—the resulting preprocessing complexity would be $O(|C|n^6) + O(|C|n^6)\times \textsf{BC}$, which is too large. This situation leads to the following interesting and challenging question:

1.1 Our Contribution

In this work we make progress on this question by providing an MPC protocol in the honest majority case $t<n/2$ that has $O(\textsf{depth}(C))$ rounds even in the worst case, while improving over the communication of the state-of-the-art [10] in this regime. We achieve a communication of $O(n|C| + \textsf{depth}(C)n^3) + O(n|C|+\textsf{depth}(C)n^3)\times \textsf{BC}$ in the online phase (a factor of $n^2$ improvement), and for the offline phase our communication is $O(n^3|C|) + O(n^3|C|)\times \textsf{BC}$ (a factor of n improvement). Table 1 presents our communication in relation to the work of [10], as well as the previous works that achieved G.O.D. with an amount of rounds proportional to $\textsf{depth}(C)$, independent of n.

Interestingly, for the online phase, our protocol matches the peer-to-peer communication of the best-known protocol [18], which is linear O(n|C|) (also believed to be optimal [13]).² This constitutes significant progress in the direction of matching the communication of G.O.D. protocols for $t<n/2$ with $O(\textsf {depth}(C))$ rounds, like ours, with protocols that add $O(n^2)$ rounds in the worst case, like [18]. We recall that for $t<n/3$ and perfect security, the task of designing protocols with $O(\textsf{depth}(C))$ rounds whose communication matches that of $O(\textsf{depth}(C) + n)$-round protocols was only recently settled in [2].

Remark 1

(On the term $\textsf{depth}(C)\cdot n^3$). Our online communication is $O(n|C| + \textsf{depth}(C)n^3) + O(n|C|+\textsf{depth}(C)n^3)\times \textsf{BC}$. Note that the term $\textsf{depth}(C)n^3$ is absorbed by |C|n, as long as $|C|/\textsf{depth}(C) = \varOmega (n^2)$, in which case the communication becomes $O(|C|n)+O(|C|n)\times \textsf{BC}$. This can be satisfied for instance if the circuit has uniform width $\varTheta (n^2)$, but this is not strictly necessary: for example, a few layers can have a very small amount of multiplication gates (say o(n)), while some others may have many more gates (say $\approx n^3$), and the property $|C|/\textsf{depth}(C) = \varOmega (n^2)$ may still be satisfied.

Table 1. Works with G.O.D. for $t<n/2$, and $O(\textsf{depth}(C))$ rounds (independent of n, even in the worst case). “N/A” in the offline phase means these works did not consider an offline/online separation. We ignore $\textsf{poly}(n)$ terms that do not depend on C. $^*$ The work of [14] does not instantiate the offline phase. The complexity reported is obtained by calculating the cost of generating their preprocessing using our protocol. For this, we take their preprocessing size, $n^2|C|$, and multiply it by the total communication of our protocol, leading to $O(n^3\cdot n^2|C|)$.

1.2 Other Related Work

We have already discussed the works of [5, 8, 10, 11, 14, 18]—which are the works most related to us—as well as their comparison with respect to our work. We present in the full version a more detailed description of how these protocols work. As other related literature, an important mention is [22], which presents a series of compilers which, among other things, enable “upgrading” secure-with-abort protocols into G.O.D.. Their approach also results in a protocol whose round complexity depends on n, since it consists of identifying corrupt parties and then re-running certain parts of the protocol.

Using information-theoretic randomized encodings [20, 21], it is possible to achieve statistically secure MPC in the $n = 2t + 1$ setting with constant round complexity [3] (i.e. the round complexity is independent of both n and $\textsf{depth}(C)$) where the constant is 4. This is akin to how Garbled Circuits (which are an instance of computationally secure randomized encoding) enable us to achieve constant round complexity in the computational setting. In such protocols, the communication complexity is always proportional to the size of the randomized encoding. With current known techniques, the size of information-theoretic randomized encoding grows exponentially with the circuit depth and reducing this exponential dependency has been a big open problem for the past two decades. Hence, this approach of using randomized encodings to get low round complexity is currently practical only for $\textsf{NC}^1$ circuits.

1.3 Overview of Our Techniques

We discuss at a very high level how our final protocol is achieved. First, to avoid the extra $n^2$ rounds, we must deviate from the dispute-control paradigm used in all communication-efficient works [5, 8, 18]. Instead, let us take as a starting point the protocol from [10, Section VI], which is more communication heavy but removes the round dependency on n. In [10] the authors make use of the verifiable secret-sharing (VSS) ideas from [11, 24], which enable parties to obtain sharings $\left[ s \right]$ of a secret in such a way that the honest parties can always reconstruct the given secret s, using a constant number of rounds. The authors make use of multiplication triples [4], produced in an offline phase. With this preprocessing at hand, the online phase is comprised only of linear combinations and reconstruction of secret-shared data, which is possible thanks to the VSS guarantees. The main contribution of [10] lies in the generation of the multiplication triples. Traditionally, the most efficient approach for triple generation is the first generating so-called double-sharings [12], which can be later used to obtain triples. However, this approach requires more than what VSS can provide: there are certain proofs of correctness that the parties must perform, which ultimately add substantially to the final costs (intuitively, these complexities come from local multiplication increasing the degree from t to 2t). Instead, the work of [10] introduces a novel approach which only relies on the basic properties of VSS, letting each party contribute with triples directly, which are later checked for correctness and “combined” in such a way that truly random triples are produced. Intuitively, this only relies on sharing, linear combinations, and reconstructions, and hence can be handled by the underlying VSS alone. Now, this approach is less communication-efficient than using double-sharings, but it is much more suitable for reducing the number of rounds. From the above, in order to improve the communication complexity of [10], which maintains the number of rounds we are looking for, it is imperative to improve that of the underlying VSS.

Optimizing—But Weakening—Verifiable Secret-Sharing. We start from the VSS used in [10], which is that from [24] in conjunction with the so-called information-checking protocol (ICP) from [11]. Intuitively, these techniques involve distributing Shamir sharings, and additionally, distributing shares of each share to the parties. The shares-of-shares exist so that, when a party announces a share, it can prove to the others this is correct by also showing them the shares of the announced share, which the parties can contrast with the share-of-share they have internally. Now, a corrupt party may complain of a correctly announced share, and to prevent this the ICP machinery is used: that ensures that (1) honest parties can always prove the correctness of their shares, and (2) corrupt parties who modify their shares are identified. The degree of the polynomials is t, which requires $t+1$ shares to be reconstructed. By using the “signatures”, the $\le t+1$ correct shares coming from the honest shares can be identified, which allows for the reconstruction of the secret. Inspired by [1], our approach to improve the complexity of this VSS is to make use of packed secret-sharing [16], which allows for having $\ell \ge 1$ secrets instead of only one, without penalty in the communication costs. However, using packed secret-sharing comes at the expense of increasing the degree of the underlying polynomials from t to $t+(\ell -1)$, and in particular reconstruction now requires more shares than honest parties. This is not a problem in [1], which is set in $t<n/3$, but in our $t<n/2$ regime extra care is needed.

We use packed secret-sharing twice, resulting in packed vectors of dimension $\varTheta (n^2)$. First, we use degree $(t+(\ell -1))$ to secret-share $\ell =\varTheta (n)$ secrets at once (we will specify the exact value of $\ell$), but crucially, we use degree-t for the “shares of shares”, which ensures the $t+1$ honest parties alone still have enough joint information to reconstruct the secrets. Now, each share-of-share is signed using the ICP from [11], which at a high level works by secret-sharing the message to be signed towards the parties, so that later on when this message is revealed, the parties can jointly verify if this is consistent with the shares they hold. In [11] degree-t polynomials are used, but a useful observation from [23] is that this can be improved by using packed secret-sharing, signing multiple messages towards multiple verifiers simultaneously. We adapt their ideas to our setting. This requires a batch of $m=\varTheta (n)$ shares to be signed, each of which corresponds to $\ell = \varTheta (n)$ secrets, so overall our VSS works on vectors of dimension $m\ell = \varTheta (n^2)$.

Finally, an important remark is that our construction does not directly instantiate the notion of VSS. Increasing the degree from t to $t+(\ell -1)$ or, as we will see, $t+2(\ell -1)$ in some cases, comes at the expense of corrupt parties being able to disrupt the reconstruction if they decide to misbehave or abort. However, we still guarantee the crucial property that such corrupt parties are identified. We call this weaker notion detectable secret-sharing (DSS), and one of our core contributions, on top of the formal definition of such primitive as a UC functionality and its efficient instantiation, is showing that this weaker form of VSS can still be useful for our goal of MPC with $O(\textsf{depth}(C))$ rounds. We discuss this below.

1.4 Our MPC Protocol

Since our core secret-sharing primitive operates on vectors instead of individual values, we cannot make direct use of the MPC approach from [10], which follows the standard Beaver triple paradigm [4]. Instead, we adapt the ideas from the recent Turbopack work by Escudero et al. [15], which shows how to efficiently make use of packed secret-sharing, supporting arbitrary circuits without noticeable overhead. The details are provided in Sect. 5, but at a high level, there are two main components required in Turbopack. In the offline phase, the main challenge is generating packed multiplication triples, while in the online phase, the main challenge is reconstructing degree-$(t+2(\ell -1))$ secrets. For the first part, we show how to adapt the triple extraction ideas from [10], which quite surprisingly turn out to also work for the packed secret-sharing regime. The most interesting and challenging part is addressing the degree-$(t+2(\ell -1))$ reconstructions.

Recall that in our DSS, the adversary may completely halt the reconstruction of degree-$(t+2(\ell -1))$ secrets. This is because, even though as in [11, 24] our scheme guarantees that honest parties can convince the others that their announced shares are correct, and also that corrupt parties announcing incorrect shares are identified, given that there are only $t+1$ honest parties, only $t+1$ out of the $t+2(\ell -1)+1$ shares needed for reconstruction are guaranteed to be announced. That is, there could be $2(\ell -1)$ shares missing. Our core observation is the following. If the t corrupt parties collectively send less than these $2(\ell -1)$ shares, hence halting reconstruction, it is because more than $t-2(\ell -1)$ cheaters misbehaved, and crucially, their identities become known due to the properties of our DSS. At this point these parties can be removed, restarting the computation with threshold $t' < t-(t-2(\ell -1))$ and total number of parties $n' < n-(t-2(\ell -1))$. This time, the corruption ratio is $t'/n'$, and it turns out we can upper bounded it by 1/3 as long as we take $\ell \le \frac{n+6}{8}$. The rest of the protocol is now set in the $t'<n'/3$ regime, point in which we can apply any existing work for that threshold to finish the computation. In particular, we can use the recent work of [1], which achieves perfect security but most importantly, requires linear communication and has no overhead in terms of the number of rounds.³ Note that the adversary can only cause an abort-and-restart once, hence keeping the overall number of rounds $O(\textsf{depth}(C))$.

There is a subtle issue when instantiating this novel idea. Restarting the protocol from scratch may allow the parties to change their inputs, which is not secure if in the first run the adversary was able to learn some information about the output. We propose two ways to address this, which perform differently depending on the amount of inputs versus amount of outputs. The first approach is more suitable if there are not many inputs, and consists of having the parties provide sharings of their inputs not only in our DSS scheme—which is packed and does not guarantee reconstruction—but also in the original VSS of [11, 24], while proving these two are consistent. In this way, if there is a restart, the parties can provide shares of the inputs for the $t'<n'/3$ protocol, while proving they hold the same secrets as the initial VSS sharings.

The second approach is more adequate if there are not many outputs. First, we note that it is fine to restart the computation while allowing the parties to change their inputs as long as this happens before the output phase, since in this case no sensitive leakage occurs. Now, we modify the output phase as follows: instead of attempting straight reconstruction of the degree-$(t+2(\ell -1))$ output sharings, the parties first convert the packed sharing of the outputs in the main protocol into a non-packed VSS representation. We design this conversion mechanism so that it does not leak anything about the outputs in case it aborts. This way, there are two potential outcomes: either the conversion succeeds, point in which the outputs are VSS’ed and then can be reconstructed with no abort, or the conversion fails, which does not leak anything and hence it is fine to restart the computation with $t'<n'/3$, even if the parties change their inputs. Details on these protocols are given in the full version.

2 Preliminaries

Let $\kappa$ be a statistical security parameter. We consider a finite field $\mathbb {F}$ with $|\mathbb {F}| = \omega (\texttt{poly}(\kappa ))$, so that $\texttt{poly}(\kappa )/|\mathbb {F}| = \texttt{negl}(\kappa )$. Given two strings x and y, we denote by $x\Vert y$ the concatenation of the two. We denote length-$\ell$ vectors as $\boldsymbol{v}=(v^1,\dots ,v^\ell )^\intercal \in \mathbb {F}^\ell$. Given two vectors $\boldsymbol{u}=(u^1,\dots ,u^\ell )^\intercal ,\boldsymbol{v}=(v^1,\dots ,v^\ell )^\intercal \in \mathbb {F}^\ell$, we define $\boldsymbol{u}*\boldsymbol{v}=(u^1\cdot v^1,\dots ,u^\ell \cdot v^\ell )^\intercal$ as the component-wise multiplication of $\boldsymbol{u}$ and $\boldsymbol{v}$. We denote $m\times n$ matrices as $\boldsymbol{M}\in \mathbb {F}^\ell$. For any given $C\subseteq [n]$, we denote by $\boldsymbol{M}^C$ the sub-matrix of $\boldsymbol{M}$ corresponding to the columns with indices C. We study MPC amongst n parties in the setting where the number of corrupted parties is exactly t with $n=2t+1$. We denote the set of honest parties as $\textsf{Hon}\subseteq [n]$ and the set of corrupted parties as $\textsf{Corr}\subseteq [n]$. We say that a protocol has communication complexity $\textsf{P2P}(M) + N\times \textsf{BC}(L)$ if it sends M field elements in total over the peer-to-peer channels, and it calls the broadcast channel N times with messages containing L field elements. A degree-d univariate polynomial over $\mathbb {F}$ is of the form $f(x)=\sum _{i=0}^d c_i x^i$, where $c_i\in \mathbb {F}$. We say that a collection of field elements $z_{i_1},\dots ,z_{i_m}$ for $m>d$ and unique $i_1,\dots ,i_m\in \mathbb {F}$ is consistent with a degree-d polynomial, if there exists some degree-d polynomial f(x) such that $f(i_j)=z_{i_j}$ for $i_j\in [m]$. A degree-$(d_x, d_y)$ bivariate polynomial over $\mathbb {F}$ is of the form $F(x, y) = \sum _{i = 0}^{d_x} \sum _{j = 0}^{d_y} c_{i, j} x^i y^j$ where $c_{i, j} \in \mathbb {F}$. For $i\in \mathbb {F}$, we can isolate univariate polynomials $f_i(x) = F(x, i)$ and $g_i(y) = F(i, y)$ of degree $d_x$ and $d_y$ respectively. In this paper, we will always assume that $d_x=\max \{d_x,d_y\}$. In the full version, we present some basic lemmas regarding bivariate polynomials.

3 Linear Batched Information-Checking Signatures

In this section, we introduce a crucial building block that will be used in our packed detectable secret sharing scheme: linear batched information-checking signatures (IC signatures). This primitive and its construction are based on that of [23], which in turn are based on that of [11, 24]. A batched IC signature protocol is executed amongst n parties and allows a dealer $D$ to send a “signature” $\sigma$ of a batch To ensure that a corrupt $INT$ (or a corrupt $D$) does not cheat, the n parties, who we call verifiers, each get a “share” of the signature. Importantly, the corrupted parties’ shares should together not reveal anything about $\boldsymbol{s}$. Later, $INT$ can reveal the signature $\sigma$ of $\boldsymbol{s}$ to the n verifiers. Using the shares previously received, the verifiers then decide whether or not to accept the signature. In fact, we allow $D$ to sign many such batches, based on which $INT$ can add their corresponding signatures together, to get a signature of their sum. We also allow $INT$ to compute the signature of a signed batch of secrets component-wise multiplied with some public vector $\boldsymbol{u}\in \mathbb {F}^\ell$, using the signature of the original batch.

3.1 IC Signature Ideal Functionality

We now formally introduce our ideal functionality for linear batched IC signatures. The properties that we want from an IC signature are intuitively as follows: (i) If the dealer $D$ is honest, then with all-but-negligible probability, the honest verifiers will only accept a signature $\sigma$ on the batch $\boldsymbol{s}$ input by $D$; (ii) If the intermediary $INT$ is honest, then after the signing phase, $INT$ knows a signature $\sigma$ on some batch $\boldsymbol{s}$ that the honest verifiers will later accept with all-but-negligible probability; and (iii) If both the dealer $D$ and intermediary $INT$ are honest, then nothing about $\boldsymbol{s}$ is revealed to the corrupt verifiers before the reveal phase. Note that if both the dealer $D$ and intermediary $INT$ are corrupted, we guarantee nothing about the signatures, and in fact, $INT$ can decide to reveal a signature $\sigma$ for any $\boldsymbol{s}$ of the adversary’s choosing.

Furthermore, we require the following linearity properties from our IC signatures: (i) Given a signature $\sigma _1$ on $\boldsymbol{s}_1$ and a signature $\sigma _2$ on $\boldsymbol{s}_2$, we can define a signature $\sigma _3$ on $\boldsymbol{s}_1+\boldsymbol{s}_2$ with the above properties; and (ii) Given a signature $\sigma$ on $\boldsymbol{s}$ and a public vector $\boldsymbol{u}\in \mathbb {F}^\ell$, we can define a signature $\sigma '$ on $\boldsymbol{s}*\boldsymbol{u}$ with the above properties, only if $\sigma$ is a linear combination of other signatures that were not themselves multiplied by a public vector.

This latter property of multiplication with a public vector is our main contribution to IC signatures. We now present the ideal functionality $\mathcal {F}_{\mathsf {batch\text {-} IC}}$, which captures the above properties (Note: as far as we are aware, there has been no formal treatment in UC, or any other simulation-based framework, of IC signatures individually in prior works).

3.2 IC Signature Protocol

Now, we present our protocol $\varPi _{\mathsf {batch\text {-} IC}}$ which instantiates $\mathcal {F}_{\mathsf {batch\text {-} IC}}$. In the initialization phase, the dealer $D$ first sends to each party $P_i$, random $\alpha _i\leftarrow _{\$}\mathbb {F}$, for $i\in [n]$.

Signing. When signing some $\boldsymbol{s}\in \mathbb {F}^\ell$, the dealer $D$ samples a random degree-$(t+\ell -1)$ polynomial f(x) such that $f(-j+1)=s^j$ for $j\in [\ell ]$ and a random degree-$(t+\ell -1)$ polynomial r(x). $D$ then sends f(x) and r(x) to $INT$, and to each other party $P_i$, $v_i\leftarrow f(\alpha _i)$ and $r_i\leftarrow r(\alpha _i)$. Notice that since f(x) is of degree-$(t+\ell -1)$, an adversary’s t points $\{v_j\}_{j\in \textsf{Corr}}$ reveal nothing about $\boldsymbol{s}$. Now, note that a corrupt $D$ could send $v_i\ne f(\alpha _i)$ to some $P_i$. In order to catch this bad behavior, $INT$ samples random $\beta \leftarrow _{\$}\mathbb {F}$ and broadcasts $(\beta ,b(x))$, where $b(x)\leftarrow \beta \cdot f(x)+r(x)$; since $\beta$ is uniformly random, with all-but-negligible probability, $P_i$ will see that $b(\alpha _i)\ne \beta \cdot v_i + r_i$, and thus $D$ is corrupted. Also, observe that r(x) masks f(x) and thus $\boldsymbol{s}$. However, it could also be the case that $D$ is honest and a corrupted $INT$ broadcasts $(\beta ,b(x))$ where $b(x)\ne \beta \cdot f(x)+r(x)$; in this case, the honest $D$ will know that $INT$ is corrupted, and thus the adversary knows $\boldsymbol{s}$, so it can simply broadcast $\boldsymbol{s}$. If $D$ (honest or corrupt) broadcasts $\boldsymbol{s}$, then $INT$ sets the signature $\sigma \leftarrow g(x)$, where g(x) is the degree-$\ell$ polynomial such that $g(-j+1)=s^j$ for $j\in [\ell ]$, and each $P_i$ resets $v_i\leftarrow g(\alpha _i)$. If $D$ does not broadcast $\boldsymbol{s}$, but $b(\alpha _i)\ne \beta \cdot v_i + r_i$ then $P_i$ knows that $D$ is corrupt, and so will accept any signature from $INT$ for this batch of secrets. Also (whether or not $D$ is honest or corrupt), if $D$ does not broadcast $\boldsymbol{s}$, $INT$ sets $\sigma \leftarrow f(x)$.

Adding and multiplication by Public Vectors. To add two signatures together, $INT$ simply sets $\sigma _3(x)\leftarrow \sigma _1(x)+\sigma _2(x)$, and each $P_i$ sets $v_{3,i}\leftarrow v_{1,i}+v_{2,i}$, where it stored $v_{1,i}$ and $v_{2,i}$ for $\sigma _1$ and $\sigma _2$, respectively. To multiply $\sigma$ by some public vector $\boldsymbol{u}\in \mathbb {F}^\ell$, let u(x) be the degree-$(\ell -1)$ polynomial such that $u(-j+1)=u^j$ for $j\in [\ell ]$. $INT$ simply sets $\sigma '(x)\leftarrow \sigma (x) \cdot u(x)$ (so that it is of degree $t+2\ell -2$) and each $P_i$ sets $v'_i\leftarrow v_i\cdot u(\alpha _i)$.

Revealing. Finally, to reveal a signature, $INT$ simply broadcasts $\sigma (x)$. Then each $P_i$ broadcasts $\textsf{accept}$ if $\sigma$ is of degree at most $t+2\ell -2$ and $\sigma (\alpha _i)=v_i$ or they already marked $D$ as corrupt for this signature (or any of which this signature consists). If at least $t+1$ parties broadcast $\textsf{accept}$, then the honest parties set $s^j\leftarrow \sigma (=j+1)$ for $j\in [\ell ]$ and output $(s^1,\dots ,s^\ell )$; otherwise they output $\textsf{reject}$. Note that if $D$ is honest and $INT$ is corrupted, for any given honest $P_i$, if $\sigma$ is incorrect, then the probability that $\sigma (\alpha _i)=v_i$ is negligible, by the Schwartz-Zippel Lemma, since $\alpha _i$ is random and unknown to the adversary. Thus, with all-but-negligible probability, there will be no $P_i$ such that $\sigma (\alpha _i)=v_i$ for incorrect $\sigma$, and thus, the honest parties will only accept a correct $\sigma$ (since there are at most $t<t+1$ corrupted parties). Observe also that in the case of an honest $INT$ and corrupted $D$, from above, we will already have that $\sigma (\alpha _i)=v_i$, or $P_i$ marked $D$ as corrupt for this signature, for all $\ge t+1$ honest $P_i$, and thus all honest $P_i$ will accept.

Rerandomizaing Signatures of Degree-$(2t+2\ell -2)$ Before Revealing. One subtlety in the security proof occurs if both $D$ and $INT$ are honest, and a multiplication with some $\boldsymbol{u}$ occurs, boosting the degree of $\sigma$ to $2t+2\ell -2$. In this case, when $\sigma$ is revealed in the ideal world, the simulator $\mathcal {S}$ only has at most t corrupted parties’ shares and the $\ell$ points corresponding to the underlying signed $\boldsymbol{s}$, and thus cannot correctly simulate the polynomial $\sigma (x)$. For this reason, before broadcasting $\sigma$, $INT$ re-randomizes it with a degree-$(2t+2\ell -2)$ polynomial o(x) given to $INT$ by $D$ in the initialization phase, such that $o(-j+1)=0$ for $j\in [\ell ]$. Each party $P_i$ also adds to $v_i$, $o_i\leftarrow o(\alpha _i)$, given to them by $D$ in the initialization phase. Similarly to before, for honest $INT$ to ensure that corrupted $D$ gave it o(x) corresponding to the honest parties’ $o_i$ values, in the initialization phase it actually receives another such polynomial $o'(x)$ from $D$, and broadcasts $(\beta , \beta \cdot o(x)-o'(x))$, which the honest parties verifies is consistent with their $o_i,o'_i$. If an honest $INT$ or $D$ catches a corrupted $D$ or $INT$, respectively, misbehaving during the initialization phase, then it broadcasts $\textsf{Corr}\leftarrow 1$. If so, then for all future signatures, $D$ simply broadcasts the secret batch $\boldsymbol{s}$ (since the adversary would learn it anyway).

Now we present the formal protocol $\varPi _{\mathsf {batch\text {-} IC}}$, below.

Efficiency of $\varPi _{\mathsf {batch\text {-} IC}}$. First, it is clear the initialization phase takes O(1) rounds and costs $\textsf{P2P}(O(n))$ for sending the $\alpha _i$. We will count the cost of generating the $o_\tau (x)$ in the corresponding reveal phase below.

In the signing phase, $D$ first sends f(x), r(x) to $INT$, which costs $\textsf{P2P}(2(t+\ell ))$. $D$ then sends the $v_i,r_i$ to the parties $P_i$, which costs $\textsf{P2P}(2n)$ values. $INT$ then broadcasts $(\beta ,b(x))$ which costs $1\times \textsf{BC}(1+t+\ell )$. Then, in the worst case, $D$ broadcasts $\boldsymbol{s}$, which costs another $1\times \textsf{BC}(\ell )$. Thus, the signing phase costs $\textsf{P2P}(O(n+\ell ))$ and $1\times \textsf{BC}(O(n+\ell ))$. If $\ell =\varTheta (n)$, then this is $\textsf{P2P}(O(n))$ and $1\times \textsf{BC}(O(n))$. It is clear that the signing phase takes O(1) rounds. Note that both adding and multiplication are local operations.

In the reveal phase, $INT$ broadcasts h(x) which costs at most $1\times \textsf{BC}(t+2\ell -2)$. Then, each $P_i$ broadcasts $\textsf{accept}$ or $\textsf{reject}$ which costs $n\times \textsf{BC}(1)$. Additionally, in the initialization phase, $D$ sends $o_1(x),o_2(x)$ to $INT$, the former of which $INT$ adds to $\sigma (x)$ to get h(x), which costs $\textsf{P2P}(2(t+2\ell -2))$, and $o_{1,i},o_{2,i}$ to each $P_i$, which costs $\textsf{P2P}(2n)$. Then $INT$ broadcasts $(\beta ,o(x))$, which costs $1\times \textsf{BC}(t+2\ell -1)$. Counting the cost to generate $o_1(x)$ as part of the reveal phase cost, we get the reveal phase costs $\textsf{P2P}(O(n+\ell ))$, $O(n)\times \textsf{BC}(O(1))$, and $O(1)\times \textsf{BC}(O(n+\ell ))$. If $\ell =\varTheta (n)$, then this is $\textsf{P2P}(O(n))$, $O(n)\times \textsf{BC}(O(1))$, and $O(1)\times \textsf{BC}(O(n))$. It is clear that the reveal phase takes O(1) rounds.

Theorem 1

$\varPi _{\mathsf {batch\text {-} IC}}$ UC-realizes $\mathcal {F}_{\mathsf {batch\text {-} IC}}$ for any $\ell =\texttt{poly}(\kappa )$ with probability $1-\texttt{negl}(\kappa )$.

The proof is in the full version.

4 Packed, Batched, (Mass) Detectable Secret Sharing

In this section, we introduce our packed, batched, (mass) detectable secret sharing (DSS) ideal functionality and protocol. We base the protocol off of that of [11] and take from [1] the idea of “packing” many secrets into a single bivariate polynomial, as well as batching many bivariate polynomials to amortize costs. A DSS protocol is executed amongst n parties and allows any given $P_i$ to act as a dealer and secret share a batch of secret vectors $\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m\in \mathbb {F}^\ell$. As usual, we want the corrupted parties’ shares to reveal nothing about $\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m\in \mathbb {F}^\ell$. Later, the parties can choose to publicly reconstruct $\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m$; the reconstruction must either succeed, or $\varOmega (n)$ corrupted parties are publicly identified (the exact number depends on $\ell$). In fact, we allow the parties to add their shares of many such sharings together, which results in a sharing of the vector-wise sum of the underlying batches of secret vectors. We also allow the parties to compute a sharing of a shared batch of secrets, element-wise and component-wise multiplied by some public vectors $\boldsymbol{u}_1,\dots ,\boldsymbol{u}_m\in \mathbb {F}^\ell$, using the original sharing.

4.1 Detectable Secret Sharing Ideal Functionality

We now present our packed, batched, DSS ideal functionality. The properties that we want from a DSS are as follows: (i) If the given dealer $P_i$ is honest, then all honest parties will complete the sharing phase; (ii) If the given dealer $P_i$ is honest, then nothing about $\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m$ are revealed before the reconstruction phase; and (iii) If all honest parties finish a sharing phase, then there exists fixed $\boldsymbol{x}_1,\dots ,\boldsymbol{x}_m$ such that (a) if the given dealer $P_i$ is honest, then each $\boldsymbol{x}_i=\boldsymbol{s}_i$, and (b) if all honest parties start the reconstruction phase, either it succeeds with them outputting $\boldsymbol{x}_1,\dots ,\boldsymbol{x}_m$, or it fails, but $\varOmega (n)$ corrupted parties are identified.

Furthermore, we require the following linearity properties from our DSS: (i) Given a sharing of $\boldsymbol{s}_{1,1},\dots ,\boldsymbol{s}_{1,m}$ and a sharing of $\boldsymbol{s}_{2,1},\dots ,\boldsymbol{s}_{2,m}$, the parties can compute a sharing of $\boldsymbol{s}_{1,1}+\boldsymbol{s}_{2,1},\dots ,\boldsymbol{s}_{1,m}+\boldsymbol{s}_{2,m}$ with the above properties; and (ii) Given a sharing of $\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m$ and public vectors $\boldsymbol{u}_1,\dots ,\boldsymbol{u}_m\in \mathbb {F}^\ell$, the parties can compute a sharing of $\boldsymbol{s}_1*\boldsymbol{u}_1,\dots ,\boldsymbol{s}_m*\boldsymbol{u}_m$ with the above properties, only if $\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m$ is a linear combination of other sharings that were not themselves multiplied by a batch of public vectors.

Our main contributions to DSS are using packing and batching in the statistical setting, $t<n/2$ setting to amortize costs, as well as the mass detectability property in case of failure of reconstruction. Now we present the ideal functionality $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}$, which captures the above properties.

4.2 Detectable Secret Sharing Subroutines

Before presenting our DSS protocol $\varPi _{\mathsf {Packed\text {-} DSS}}$, we will first present various procedures which $\varPi _{\mathsf {Packed\text {-} DSS}}$ uses. Note, however, that $\varPi _{\mathsf {Packed\text {-} DSS}}$ starts with each party initializing separate instances of $\mathcal {F}_{\mathsf {batch\text {-} IC}}$ as a dealer with each other party acting as intermediary. The procedures will use these instances of $\mathcal {F}_{\mathsf {batch\text {-} IC}}$.

Sharing Procedure We begin by presenting the sharing procedure, $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}(d_x,\textsf{sid},(\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m))$, below. When a party $P_i$ wants to secret share a batch of vectors $\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m\in F^\ell$,⁴ with degree $n-1\ge d_x\ge t+\ell -1$, it begins by sampling m random degree-$(d_x,t)$ bivariate polynomials such that $F_\eta (-l+1,0)=s_\eta ^l$ for $l\in [\ell ],\eta \in [m]$. Then, letting $z_\eta ^{jk}\leftarrow F_{\eta }(j,k)$ and $\boldsymbol{z}_\eta ^{jk} \leftarrow (z_{1}^{jk},\dots ,z_{m}^{jk})$, $P_i$ invokes the $\mathcal {F}_{\mathsf {batch\text {-} IC}}$ instance with $P_j$ as intermediary on input $\boldsymbol{z}_\eta ^{jk}$ and $\boldsymbol{z}_\eta ^{kj}$ (thus implicitly sending to $P_j$ these vectors), for $j,k\in [n]$. Each $P_j$ then ensures that the points it receives define valid degree-$d_x$ and degree-$(t+\ell -1)$ polynomials, respectively. If not, it reveals their points to all of the parties, using $\mathcal {F}_{\mathsf {batch\text {-} IC}}$. Then, if a party sees such a set of bad points from some other party $P_k$ (checking that indeed, the points are bad), it aborts. Then, $P_j$ invokes the $\mathcal {F}_{\mathsf {batch\text {-} IC}}$ instance with $P_k$ as intermediary on input $\boldsymbol{z}_\eta ^{kj}$ (thus implicitly sending to $P_k$ this vector), for $k\in [n]$. Next, $P_j$ compares those points it received from $P_k$ to those received from the dealer $P_i$, and if there is any inconsistency, reveals those points that $P_i$ gave it to all of the parties, using $\mathcal {F}_{\mathsf {batch\text {-} IC}}$. Then, $P_j$ checks if some $P_k$ revealed points that are not consistent with those it received from $P_i$, and if so, reveals those points that $P_i$ gave it to all of the parties, using $\mathcal {F}_{\mathsf {batch\text {-} IC}}$. If any pair of parties $P_j\ne P_k$ revealed two different vectors of points from the dealer $P_i$, then all parties abort. Otherwise, each party $P_j$ outputs its share, $(\boldsymbol{z}_\textsf{sid}^{j1},\dots ,\boldsymbol{z}_\textsf{sid}^{jn})$.

We will only ever explicitly use $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$ in the following to generate sharings with degree $d_x=t+\ell -1$ or degree $d_x=t+(2\ell -1)$. If the parties do not abort in $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$, we denote a sharing of $\boldsymbol{s} = (\boldsymbol{s_1}, \ldots , \boldsymbol{s_m})$ with degree $d_x=t+\ell -1$ as $[\![ \boldsymbol{s} ]\!]$ and a sharing with degree $d_x=t+\ell -1$ as $[\![ \boldsymbol{s} ]\!]_*$.

Now, we prove the following simple lemma about $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$:

Lemma 1

If the dealer $P_i$ is honest in $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$, then all honest parties finish $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$ without aborting.

The proof is in the full version.

Next, we prove the following lemma, which shows that if the values $\boldsymbol{z}_\textsf{sid}^{kj}$ which the honest parties $P_j$ input to $\mathcal {F}_{\mathsf {batch\text {-} IC}}$ in step 5 of $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$, and which thus become part of $P_k$’s share, define degree-t polynomials $g_k(y)$, then they uniquely define the underlying degree-$(d_x,t)$ bivariate polynomials $F_\eta (x,y)$ and thus the shared secrets $\boldsymbol{s}_\eta$.

Lemma 2

For any $K\subseteq [n]$ such that $|K|\ge d_x+1$, let $\boldsymbol{z}_\textsf{sid}^{kj}$, for $k\in K$, be the vectors that the honest parties $P_j$ input to $\mathcal {F}_{\mathsf {batch\text {-} IC}}$ in step 5 of $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$. Assume that $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$ does not abort and that for each $\eta \in [m],k\in K$, $\{z_\eta ^{kj}\}_{j\in [\textsf{Hon}]}$ define degree-t polynomials. Then for all $\eta \in [m]$, the $\{z_\eta ^{kj}\}_{j\in \textsf{Hon}}$ for $k\in K$ together define unique degree-$(d_x,t)$ bivariate polynomials $F_\eta (x,y)$.

The proof is in the full version.

Efficiency of $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$. For analyzing the communication complexity of $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$, we will utilize the efficiency of our $\varPi _{\mathsf {batch\text {-} IC}}$ protocol for $\mathcal {F}_{\mathsf {batch\text {-} IC}}$. $P_i$, for each $P_j$, signs length-m vectors $\boldsymbol{z}_\textsf{sid}^{jk},\boldsymbol{z}_\textsf{sid}^{kj}$ for $k\in [n]$, with $\mathcal {F}_{\mathsf {batch\text {-} IC}}$ which costs $\textsf{P2P}(O(n^2\cdot (n+m)))$ and $n^2\times \textsf{BC}(O(n+m))$, using $\varPi _{\mathsf {batch\text {-} IC}}$. Then, in the worst case, each $P_j$ could reveal those signatures, which costs $\textsf{P2P}(O(n^2\cdot (n+m)))$, $n^3\times \textsf{BC}(O(1))$, and $n^2\times \textsf{BC}(O(n+m))$, using $\varPi _{\mathsf {batch\text {-} IC}}$. Next, each $P_i$ sends signs for each $P_k$ length-m vectors $\boldsymbol{z}_\textsf{sid}^{kj}$ with $\mathcal {F}_{\mathsf {batch\text {-} IC}}$, which costs $\textsf{P2P}(n^2\cdot (n+m))$ and $O(n^2)\times \textsf{BC}(O(n+m))$, using $\varPi _{\mathsf {batch\text {-} IC}}$. Next, in the worst case, each $P_j$ could reveal the signatures from $P_i$ for all $k\in [n]$, which costs $\textsf{P2P}(O(n^2\cdot (n+m)))$, $n^3\times \textsf{BC}(1)$, and $n^2\times \textsf{BC}(O(n+m))$, using $\varPi _{\mathsf {batch\text {-} IC}}$. Altogether, this is $\textsf{P2P}(O(n^3+n^2m))$, $O(n^3)\times \textsf{BC}(O(1))$, and $O(n^2)\times \textsf{BC}(O(n+m))$. If $m=\varTheta (n)$, this is $\textsf{P2P}(O(n^3))$, $O(n^3)\times \textsf{BC}(O(1))$, and $O(n^2)\times \textsf{BC}(O(n))$. It is clear that $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$ takes O(1) rounds.

Adding Packed, Batched DSS’s and Multiplying Them by Public Vectors. Let us assume that the parties have a packed, batched DSS $[\![ \boldsymbol{s}_{1} ]\!]$ and a packed, batched DSS $[\![ \boldsymbol{s}_{2} ]\!]$. Adding two such sharings together is a simple, local procedure, $\pi _{\mathsf {Packed\text {-} DSS \text {-} Add}}$, which consists of parties simply adding (the signatures on) their shares together:

We denote this as $[\![ \boldsymbol{s}_{3} ]\!]\leftarrow [\![ \boldsymbol{s}_{1} ]\!]+[\![ \boldsymbol{s}_{2} ]\!]$. Note that this also works for sharings $[\![ \boldsymbol{s}_{1} ]\!]_*$ and/or $[\![ \boldsymbol{s}_{2} ]\!]_*$ of higher degree ($d_x=t+2(\ell -1)$), in which case we denote $[\![ \boldsymbol{s}_{3} ]\!]_*$ as the resulting sharing.

Now, let us assume that the parties have a single packed, batched DSS of secrets $[\![ \boldsymbol{s} ]\!]$ (note that for such a sharing, $d_x=t+\ell -1\le n-\ell$), and some public vectors $\boldsymbol{u}_1,\dots ,\boldsymbol{u}_m\in \mathbb {F}^\ell$. Multiplying the sharing by this batch of public vectors is a simple, local procedure, $\pi _{\mathsf {Packed\text {-} DSS \text {-} Mult}}$, which consists of parties simply multiplying their shares (and the signatures on those shares) by the degree-$(\ell -1)$ polynomials $u_\eta (x)$ such that $u_\eta (-l+1)=u_\eta ^l$ for $\eta \in [n],l\in [\ell ]$:

We denote this as $[\![ \boldsymbol{s} ]\!]_*\leftarrow [\![ \boldsymbol{s} ]\!]*\boldsymbol{u}$, since the new sharing has degree $d_x=t+2(\ell -1)$.

Let $F_{\textsf{sid}',\eta }(x,y)$ be the unique polynomials defined by the $\{z_{\textsf{sid}',\eta }^{kj}\}_{j\in \textsf{Hon}}$ for $k\in K$, of some sharings $[\![ \boldsymbol{s}' ]\!]$ output by $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$, according to Lemma 2. We can again prove the following lemma similar to Lemma 2, which essentially says that for any sharing $[\![ \boldsymbol{s} ]\!]$ (or $[\![ \boldsymbol{s} ]\!]_*$) formed by running the addition and multiplication procedures above on sharings $[\![ \boldsymbol{s}' ]\!]$ originally output by $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$, the $\{\boldsymbol{z}_\textsf{sid}^{jk}\}_{j\in \textsf{Hon}}$ part of each $P_k$’s share (defined by the corresponding signatures), together uniquely define the underlying degree-$(d_x,t)$ bivariate polynomials $F_\eta (x,y)$, which are equal to the polynomials that result from applying the same addition and multiplication procedures on the $F_{\textsf{sid}',\eta }(x,y)$ above from the original sharings $[\![ \boldsymbol{s}' ]\!]$.⁵ The proof is in the full version.

Lemma 3

Let the sharing $[\![ \boldsymbol{s} ]\!]$ (resp. $[\![ \boldsymbol{s} ]\!]_*$), be the result of addition and multiplication procedures on sharings $[\![ \boldsymbol{s}' ]\!]$ originally output by $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$. For any $K\subseteq [n]$ such that $|K|\ge d_x+1$, let $\{\boldsymbol{z}_\textsf{sid}^{kj}\}_{j\in \textsf{Hon}}$ be the part of each $P_k$’s shares of $[\![ \boldsymbol{s} ]\!]$ (resp. $[\![ \boldsymbol{s} ]\!]_*$) defined by the $\mathcal {F}_{\mathsf {batch\text {-} IC}}$ instance with $P_j$ as dealer and $P_k$ as intermediary. Assume that for each $\eta \in [m],k\in K$, $\{z_{\textsf{sid},\eta }^{kj}\}_{j\in [\textsf{Hon}]}$ define degree-t polynomials. Then for all $\eta \in [m]$, the $\{z_{\textsf{sid},\eta }^{kj}\}_{j\in \textsf{Hon}}$ for $k\in K$ together define unique degree-$(d_x,t)$ bivariate polynomials $F_{\textsf{sid},\eta }(x,y)$ which are equal to the polynomials which result from applying the same addition and multiplication procedures on the unique polynomials $F_{\textsf{sid}',\eta }(x,y)$ defined by the $\{z_{\textsf{sid}',\eta }^{kj}\}_{j\in \textsf{Hon}}$ for $k\in K$, by Lemma 2.

Essentially, the above lemma shows that our add and multiplication procedures have the desired outcome of performing the corresponding operations. The following corollary will help us show that the correct secrets can then be reconstructed from such sharings. The proof is in the full version.

Corollary 1

If for each $\eta \in [n],k\in K$, $\{z_{\textsf{sid},\eta }^{ki}\}_{i\in [n]}$ in $P_k$’s share of $[\![ \boldsymbol{s} ]\!]$ (resp. $[\![ \boldsymbol{s} ]\!]_*$) define a degree-t polynomial, then given any $I\subseteq [n]$ such that $|I|=t+1$ (such as $[t+1]$) $\{z_{\textsf{sid},\eta }^{ki}\}_{i\in I}$ can be used to interpolate the same unique degree-$(d_x,t)$ bivariate polynomials $F_{\textsf{sid},\eta }(x,y)$ as in Lemma 3.

Reconstruction Procedure Next, we present the reconstruction procedure, $\pi _{\mathsf {Packed\text {-} DSS \text {-} Rec}}([\![ \boldsymbol{s} ]\!])$, which the honest parties use to reconstruct the batch of secret vectors defined by their shares of the sharing $[\![ \boldsymbol{s} ]\!]$. All parties $P_k$ first reveal their share $\boldsymbol{z}_\textsf{sid}^{k1},\dots ,\boldsymbol{z}_\textsf{sid}^{kn}$ to all parties using $\mathcal {F}_{\mathsf {batch\text {-} IC}}$. Then, each $P_k$ checks if the points that each $P_j$ revealed define degree-t polynomials in y, and if not, marks them as corrupt. Then, if the number of parties marked corrupt is greater than $2t-d_x$, the honest parties output those parties’ identities that are marked corrupt (note that sharings must satisfy $d_x\le n-1$, so $2t-d_x>0$). Otherwise, the parties use the shares of those parties that are not marked corrupt to interpolate the unique, correct $F_\eta (x,y)$ (that exist by Corollary 1) and output the corresponding secrets $\boldsymbol{s}_\eta$. Note that this procedure works in exactly the same way for sharings $[\![ \boldsymbol{s} ]\!]_*$ of higher degree $d_x=t+2(\ell -1)$.

We now have the following lemma, which shows that if $\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m$ are output by the honest parties, then they are the correct secrets corresponding to $[\![ \boldsymbol{s} ]\!]$; otherwise, each party $P_k\in T$ is actually corrupt. The latter is because for sharings output by $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$, honest parties’ shares are always consistent with degree-t polynomials, for otherwise they would have aborted. Furthermore, addition and multiplication operations do not affect the degree in the y variable, so the shares always stay consistent with degree-t polynomials. The proof appears in the full version.

Lemma 4

Let $\{\boldsymbol{z}_\textsf{sid}^{kj}\}_{k\in K,j\in [n]}$ be the points that are revealed via $\mathcal {F}_{\mathsf {batch\text {-} IC}}$ in $\pi _{\mathsf {Packed\text {-} DSS \text {-} Rec}}$. If $|T|\le 2t-d_x$, then the honest parties output the correct secrets $\boldsymbol{s}_1,\dots ,\boldsymbol{s}_m$ defined by the unique degree-$(t+\ell -1,t)$ bivariate polynomials $(F_1(x,y),\dots ,F_m(x,y))$ from Lemma 3. If $|T| >2t-d_x$, then the honest parties output $(\textsf{abort}, T)$ such that for each $P_j\in T$, $P_j\in \textsf{Corr}$.

Efficiency of $\pi _{\mathsf {Packed\text {-} DSS \text {-} Rec}}$. For analyzing the communication complexity of $\pi _{\mathsf {Packed\text {-} DSS \text {-} Rec}}$, we will utilize the efficiency of our $\varPi _{\mathsf {batch\text {-} IC}}$ protocol for $\mathcal {F}_{\mathsf {batch\text {-} IC}}$. Each $P_k$ simply reveals $\boldsymbol{z}_\textsf{sid}^{kj}$, for $j\in [n]$ with $\mathcal {F}_{\mathsf {batch\text {-} IC}}$, which costs $\textsf{P2P}(O(n^2\cdot (n+m)))$, $n^3\times \textsf{BC}(1)$, and $n^2\times \textsf{BC}(O(n+m))$, using $\varPi _{\mathsf {batch\text {-} IC}}$. If $m=\varTheta (n)$, this is $\textsf{P2P}(O(n^3))$, $O(n^3)\times \textsf{BC}(O(1))$, and $O(n^2)\times \textsf{BC}(O(n))$. It is clear that $\pi _{\mathsf {Packed\text {-} DSS \text {-} Rec}}$ takes O(1) rounds.

Creating Random Sharings $[\![ \boldsymbol{0} ]\!]_*$. After multiplying sharings by batches of public vectors, the degree of the sharing increases by $\ell -1$ in x. Thus, in order to securely open such sharings, we need to mask them by random sharings $[\![ \boldsymbol{0} ]\!]_{*}$, of degree $x_x=t+2(\ell -1)$, since all sharings created as part of the $\varPi _{\mathsf {Packed\text {-} DSS}}$ protocol will start as degree $d_x=t+\ell -1$. We use the typical random extraction technique from [13] to do this efficiently, which consists of each party creating their own such random sharings, and then using some super-invertible $(n-t)\times n$ matrix $\boldsymbol{M}$ to take linear combinations of these sharings and then output the resulting sharings that are random to the adversary.

However, it may be that the underlying secrets that corrupted parties share are not equal to $\boldsymbol{0},\dots ,\boldsymbol{0}$. For this, we adapt a standard technique, which takes as input two sharings from the same party which supposedly share $\boldsymbol{0},\dots ,\boldsymbol{0}$, take a random linear combination of the two, then open them to check if they are indeed sharings of $\boldsymbol{0},\dots ,\boldsymbol{0}$. We will adapt standard techniques to sample the random coefficients of the linear combination.

The procedures corresponding to the above, $\pi _{\mathsf {Packed\text {-} Zero\text {-} DSS}}$, $\pi _{\mathsf {Check\text {-} Zero\text {-} DSS}}$, and $\pi _{\mathsf {Packed\text {-} DSS\text {-} Coins}}$ are presented in the full version.

4.3 Detectable Secret Sharing Protocol

Now, we are finally ready to present our $\varPi _{\mathsf {Packed\text {-} DSS}}$ protocol. For generating a sharing, a given dealer simply uses $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$ with degree $d_x\leftarrow t+\ell -1$. For adding sharings and multiplying them by public vectors, the parties use $\pi _{\mathsf {Packed\text {-} DSS \text {-} Add}}$ and $\pi _{\mathsf {Packed\text {-} DSS \text {-} Mult}}$, respectively. The parties also keep track of when a given sharing is multiplied by a public vector. Then, for reconstruction, if the sharing is a linear combination of sharings that have not been multiplied by a public vector, the parties simply us $\pi _{\mathsf {Packed\text {-} DSS \text {-} Rec}}$ to reconstruct it. Otherwise, the parties first re-randomize it by adding a random sharing $[\![ \boldsymbol{0} ]\!]_{*}$ to it, and then use $\pi _{\mathsf {Packed\text {-} DSS \text {-} Rec}}$ to reconstruct it.

Efficiency of $\varPi _{\mathsf {Packed\text {-} DSS}}$. Initialization uses $\pi _{\mathsf {Packed\text {-} Zero\text {-} DSS}}$ in parallel, which takes O(1) rounds. We will count the communication cost of generating each such zero sharing towards each such sharing that is reconstructed using it below.

Sharing uses $\pi _{\mathsf {Packed\text {-} DSS \text {-} Share}}$, which costs $\textsf{P2P}(O(n^3+n^2m))$, $O(n^3)\times \textsf{BC}(O(1))$, and $O(n^2)\times \textsf{BC}(O(n+m))$. If $m,\ell =\varTheta (n)$, then this is $\textsf{P2P}(O(n))$, $O(n)\times \textsf{BC}(O(1))$, and $O(1)\times \textsf{BC}(O(n))$ per underlying secret. It also takes O(1) rounds.

Reconstruction possibly uses a zero sharing, generated from $\pi _{\mathsf {Packed\text {-} Zero\text {-} DSS}}$, which costs $\textsf{P2P}(O(n^3+n^2m))$, $O(n^3)\times \textsf{BC}(O(1))$, and $O(n^2)\times \textsf{BC}(O(n+m))$ for this sharing. It then uses $\pi _{\mathsf {Packed\text {-} DSS \text {-} Rec}}$, which costs $\textsf{P2P}(O(n^3+n^2m))$, $O(n^3)\times \textsf{BC}(O(1))$, and $O(n^2)\times \textsf{BC}(O(n+m))$. Altogether, this is $\textsf{P2P}(O(n^3+n^2m))$, $O(n^3)\times \textsf{BC}(O(1))$, and $O(n^2)\times \textsf{BC}(O(n+m))$. If $m,\ell =\varTheta (n)$, then this is $\textsf{P2P}(O(n))$, $O(n)\times \textsf{BC}(O(1))$, and $O(1)\times \textsf{BC}(O(n))$ per underlying secret. It also takes O(1) rounds.

Theorem 2

$\varPi _{\mathsf {Packed\text {-} DSS}}$ UC-realizes $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}$ in the $\mathcal {F}_{\mathsf {batch\text {-} IC}}$-hybrid model for any $\ell \le t/2$ and any $m=\texttt{poly}(\kappa )$, with probability $1-\texttt{negl}(\kappa )$.

The proof appears in the full version.

4.4 Extensions and Notation

The rest of the paper is devoted to using $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}$, Functionality 4.1, to obtain honest majority MPC with G.O.D., with our claimed communication and round complexities. In the real world, this functionality corresponds to our packed DSS, but from now on we will work with the $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}$ abstraction, which allows us to ignoring details regarding shares, degrees, and other aspects only needed to instantiate this functionality. $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}$ is implicitly parameterized by $\ell$ and m, and it models a simple but quite powerful arithmetic black box: parties can store vectors of dimension $m\ell$, and these vectors can be computed on by adding them together, as well as multiplying them element-wise by public constant vectors. Furthermore, any stored vector can be reconstructed, and the only way for the adversary to stop it is to reveal the identities of at least $t-2(\ell -1)$ corrupt parties. Recall that, for $\boldsymbol{s}\in \mathbb {F}^{m\ell }$, we denote $[\![ \boldsymbol{s} ]\!]$ a value stored in $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}$ with $\textsf{isMult}= 0$, and $[\![ \boldsymbol{s} ]\!]_*$ if $\textsf{isMult}=1$. Recall that given a public value $\boldsymbol{u}\in \mathbb {F}^{m\ell }$, it is possible to compute $[\![ \boldsymbol{s} ]\!]_*\leftarrow [\![ \boldsymbol{s} ]\!]*\boldsymbol{u}$. Addition of stored values and addition by public values is also possible. We use $[\![ \boldsymbol{a} ]\!] \leftarrow \textsf{share}(\boldsymbol{a})$ to denote sharing, and $\boldsymbol{a} \leftarrow \textsf{reconstruct}([\![ \boldsymbol{a} ]\!])$ to denote reconstruction (this also applies to $[\![ \cdot ]\!]_*$).

To be able to work with this functionality effectively, we will add to it a few helpful instructions that can be easily instantiated based on what we have seen so far. These include multiplication by scalars and addition by constants, which are particularly useful in the MPC context. The $[\![ \cdot ]\!]$ notation suggestively represents these operations. Finally, we add an instruction, whose call we abbreviate by $r\leftarrow \textsf{rand}()$, which allows the honest parties to obtain a fresh random value. This can be instantiated with a communication of $O(n^4)$, cf. Sectionthe full version

5 Our MPC Protocol

We are now ready to put together the building blocks developed in previous sections to construct our final MPC protocol for honest majority with G.O.D.. As mentioned in technical overview (Sect. 1.3), the overall structure of our protocol is inspired on that of Turbopack [15], which is particularly suitable for the use of packed secret-sharing, a crucial tool we make use of in our work. While Turbopack uses plain packed secret-sharing, we make use of our optimized detectable secret-sharing, together with its reconstruction properties.

First, we define the MPC functionality with G.O.D. we aim at instantiating in this work. Let C be an arithmetic circuit over a finite field $\mathbb {F}$ comprised of inputs, addition and multiplication gates, and outputs. Each party $P_i$ is responsible of providing a subset of the inputs. All parties are intended to receive the outputs. We use Greek letters $\alpha$, $\beta$, $\gamma$, etc. to label wires in the circuit. We aim at instantiating $\mathcal {F}_{\textsf{MPC}}$, Functionality 3, described below.

MPC for ${\boldsymbol{t<n/3}}$. As part of our protocol, we will need an MPC protocol with G.O.D. for $t<n/3$. We model this with a functionality that behaves almost exactly the same as $\mathcal {F}_{\textsf{MPC}}$, with the only difference being that (1) it interacts only with a subset of the parties, aborting if the subset has at least a 1/3 fraction of corruptions, and (2) it allows for reactive computation, meaning that different functions can be computed on the fly.⁶ We denote this functionality by $\mathcal {F}_{\mathsf {MPC\text {-} t<n/3}}$ The recent work of [1] instantiates $\mathcal {F}_{\mathsf {MPC\text {-} t<n/3}}$ with linear communication $O(n|C'|)$ while maintaining the number of rounds $O(\textsf{depth}(C'))$, where $C'$ is the function being computed (we will use $\mathcal {F}_{\mathsf {MPC\text {-} t<n/3}}$ with a function $C'$ that is slightly different to C, but has roughly the same size and depth). For the purpose of this section we use [x] when a value $x\in \mathbb {F}$ has been provided as input to $\mathcal {F}_{\mathsf {MPC\text {-} t<n/3}}$, and we say “$P_i$ inputs x, obtaining [x]”.

5.1 Offline Phase

We make use of two instances of $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}$. To clearly differentiate between the two, we make the dependency of $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}$ with $\ell$ and m explicit by writing $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}(\ell ,m)$. The first instance $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}(\ell ,m)$ allows parties to “share” or store vectors $\boldsymbol{s}\in \mathbb {F}^{m\cdot \ell }$, with $\ell = \lfloor \frac{n+6}{8}\rfloor$ and $m=n$. In what follows we use indistinctly “shared” and “stored” values/vectors, since even though we will be working in the $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}$-hybrid model, in the real world these corresponds to sharings. Recall from Sect. 4.4 that we use $[\![ \boldsymbol{s} ]\!]$ and $[\![ \boldsymbol{s} ]\!]_*$ to denote secret-shared vectors with $\textsf{isMult}=0$ and $\textsf{isMult}=1$. This, in the real world, corresponds to sharings of degree $t+(\ell -1)$ and $t+2(\ell -1)$ respectively, and the crucial difference is that first type of sharings allows for multiplications by public values whereas the latter does not. Reconstructions of $[\![ \boldsymbol{s} ]\!]$ and $[\![ \boldsymbol{s} ]\!]_*$ shared values may abort, at the expense of identifying more than $t-(\ell -1)$ or $t-2(\ell -1)$ corrupt parties respectively. The second instance $\mathcal {F}_{\mathsf {Packed\text {-} DSS}}(1,1)$ shares individual values $s\in \mathbb {F}$, and these stored values are denoted by $\langle s \rangle$. Here, the adversary cannot cause abort when reconstructing shared values. Throughout this section, we denote $\boldsymbol{1} = (1,\ldots , 1)\in \mathbb {F}^{m\ell }$, and for $i\in [m\ell ]$ we write $\boldsymbol{1}_i\in \mathbb {F}^{m\ell }$ for the vector of all zeros, except for the i-th entry, which equals 1.

Our preprocessing is as in Turbopack [15]. First, we group multiplication gates in each layer in groups of $m\cdot \ell$ gates each, and we do the same with the input wires associated to each party, as well as the output wires. Each circuit wire $\alpha$ that is not the output of an addition gate has associated to it a random mask $\lambda _\alpha \in \mathbb {F}$. If two wires $\alpha ,\beta$ are added to obtain wire $\gamma$, then $\lambda _\gamma := \lambda _\alpha + \lambda _\beta$. The preprocessing consists of sharings $[\![ \boldsymbol{\lambda _\alpha } ]\!]_*$ for every output group $\boldsymbol{\alpha }$, and sharings $([\![ \boldsymbol{\lambda _\alpha } ]\!], [\![ \boldsymbol{\lambda _\beta } ]\!],[\![ \boldsymbol{\lambda _\alpha }\star \boldsymbol{\lambda _\beta } - \boldsymbol{\lambda _\gamma } ]\!]_{*})$ for every group of multiplication gates with inputs $\boldsymbol{\alpha },\boldsymbol{\beta }$ and outputs $\boldsymbol{\gamma }$. In addition, every party $P_i$ having an input wire $\alpha$ must learn $\lambda _\alpha$. For the case of a restart, we also require every such $\lambda _\alpha$ for input wires to be VSS’ed as $\langle \lambda _\alpha \rangle$.⁷ This is captured by $\mathcal {F}_{\textsf{Prep}}$, Functionality 4.

Multiplication Triple Generation. For our preprocessing we will require uniformly random multiplication triples $([\![ \boldsymbol{a} ]\!],[\![ \boldsymbol{b} ]\!],[\![ \boldsymbol{c} ]\!]_*)$, with $\boldsymbol{c} = \boldsymbol{a}\star \boldsymbol{b}$. To this end, we show how to extend the techniques from [10], which are set in the standard (non-packed) secret-sharing setting, to the packed secret-sharing regime we use in our work. We choose the techniques from [10] since, in contrast to other approaches such as [13], no “degree-2t computations” are needed, and instead all shares are either degree $t+(\ell -1)$, or $t+2(\ell -1)$. This is crucial for us, where we require reconstruction to either succeed, or identify a large set of corrupt parties.

It is not difficult to adapt the techniques from [10] to our setting, and we discuss this in the full version. For the purpose of this section, we simply mention that there is a procedure $\pi _{\mathsf {triple \text {-} generation}}$ (Procedure ?? in the full version) that generates a single batched triple $([\![ \boldsymbol{a} ]\!], [\![ \boldsymbol{b} ]\!], [\![ \boldsymbol{c} ]\!]_*)$ which will be uniform and independent from the view of corrupt parties, as captured by the following Lemma (proven in the full version).

Lemma 5

$\pi _{\mathsf {triple \text {-} generation}}$ outputs a batched triple $([\![ \boldsymbol{a_\text {new}} ]\!], [\![ \boldsymbol{b_\text {new}} ]\!], [\![ \boldsymbol{c_\text {new}} ]\!]_*)$ which is uniform and independent from the view of an adversary corrupting at most t parties except with $\texttt{negl}(\kappa )$ failure probability.

The overall cost of $\pi _{\mathsf {triple \text {-} generation}}$ is $\textsf{P2P}(O(n^4))$, $O(n^4)\times \textsf{BC}(1)$. Since $\pi _{\mathsf {triple \text {-} generation}}$ outputs a single batched triple containing $O(m \ell ) = O(n^2)$ triples, the amortized communication cost per triple generation is $\textsf{P2P}(O(n^2))$, $O(n^2)\times \textsf{BC}(1)$.

Useful Procedures. Before we describe the protocol that instantiates $\mathcal {F}_{\textsf{Prep}}$, we describe a few useful procedures. The first, $\pi _{\mathsf {Input\text {-} Sharings}}(P_i)$ (Procedure ??), enables the parties to obtain random sharings of the form $([\![ r\cdot \boldsymbol{1} ]\!],\langle r \rangle )$, where $P_i$ knows r. This will be important for providing inputs, with the VSS part enabling restarting without input modification. The procedure follows along the same lines as $\pi _{\mathsf {Check\text {-} Zero\text {-} DSS}}$, Procedure ??, which lets $P_i$ distribute these sharings and the parties check them via random linear combinations. The second procedure, which we denote by $\pi _{\mathsf {Rand\text {-} Sharings}}$ (Procedure ??), allows the parties to obtain $[\![ r\cdot \boldsymbol{1} ]\!]$, where $r\in \mathbb {F}$ is uniformly random and unknown to any party. This first uses ideas as in the first procedure to let each party distribute one such sharing correctly, and then, similarly to $\pi _{\mathsf {Packed\text {-} Zero\text {-} DSS}}$ (Procedure ??), we can use standard techniques based on Vandermonde matrices to extract uniformly random sharings. The full descriptions of the procedures appear in the full version. The following two Lemmas are proven similarly to Lemma ?? in the full version, we omit their proof.

Lemma 6

Except with probability $\texttt{negl}(\kappa )$, the output $[\![ r\cdot \boldsymbol{1} ]\!],\langle r \rangle$ produced by $\pi _{\mathsf {Input\text {-} Sharings}}(P_i)$ is correct, and for an honest $P_i$, the secret r is distributed randomly given the corrupted parties’ shares.

Lemma 7

Except with probability $\texttt{negl}(\kappa )$, the outputs $([\![ s_1\cdot \boldsymbol{1} ]\!],\ldots ,[\![ s_{n-t}\cdot \boldsymbol{1} ]\!])$ produced by $\pi _{\mathsf {Rand\text {-} Sharings}}$ are correct, and are distributed randomly given the corrupted parties’ shares.

Preprocessing Protocol. We are finally ready to present our protocol for instantiating $\mathcal {F}_{\textsf{Prep}}$. This is given in $\varPi _{\textsf{Prep}}$, Protocol 7 below.

Theorem 3

$\varPi _{\textsf{Prep}}$ UC-realizes $\mathcal {F}_{\textsf{Prep}}$ in the $(\mathcal {F}_{\mathsf {Packed\text {-} DSS}}(\ell ,m),\mathcal {F}_{\mathsf {Packed\text {-} DSS}}(1,1))$-hybrid model, with probability $1-\texttt{negl}(\kappa )$.

The proof appears in the full version.

Communication Complexity. We now calculate the communication cost of $\varPi _{\textsf{Prep}}$ by calculating the cost of different parts:

• 1. Input groups: This step invokes $\pi _{\mathsf {Input\text {-} Sharings}}$ k times where k is the number of input wires. Each invocation of $\pi _{\mathsf {Input\text {-} Sharings}}$ costs $\textsf{P2P}(O(n^3))$, $O(n^3)\times \textsf{BC}(1)$ (assuming the cost of $\textsf{rand}()$ is amortized across n parties). Therefore, the total cost of this step is $\textsf{P2P}(O(|C| n^3))$, $O(|C| n^3)\times \textsf{BC}(1)$.

• 2. Sampling random masks: This step invokes $\pi _{\mathsf {Rand\text {-} Sharings}}$ O(|C|/n) times. Each invocation of $\pi _{\mathsf {Rand\text {-} Sharings}}$ costs $\textsf{P2P}(O(n^4))$, $O(n^4)\times \textsf{BC}(1)$. (assuming the cost of $\textsf{rand}()$ is amortized across n parties). Therefore, the total cost of this step is $\textsf{P2P}(O(|C| n^3))$, $O(|C| n^3)\times \textsf{BC}(1)$.

• 3. Multiplication groups: Let $k = |C|/n^2$ be the number of multiplication groups. This step invokes $\pi _{\mathsf {triple \text {-} generation}}$ k times where each invocation costs $\textsf{P2P}(O(n^4))$, $O(n^4)\times \textsf{BC}(1)$. Also, it performs a beaver multiplication (same as $\pi _{\textsf{Beaver}}$presented in the full version) k times where each multiplication costs $\textsf{P2P}(O(n^3))$, $O(n^3)\times \textsf{BC}(1)$. Therefore, the total cost of this step is $\textsf{P2P}(O(|C| n^2))$, $O(|C| n^2)\times \textsf{BC}(1)$.

Summing up all the above costs, the overall communication cost of $\varPi _{\textsf{Prep}}$ is $\textsf{P2P}(O(|C| n^3))$, $O(|C| n^3)\times \textsf{BC}(1)$.

Remark 2

(On function-dependent/independent preprocessing.). As in [15], we can easily make our offline phase function-independent without affecting our asymptotic communication in the online phase. For this, the offline phase consists only of generating sharings of the form $[\![ r\cdot \boldsymbol{1} ]\!]$ and $([\![ \boldsymbol{a} ]\!], [\![ \boldsymbol{b} ]\!], [\![ \boldsymbol{a}\star \boldsymbol{b} ]\!]_*)$ (which is function-independent), and the part of $\varPi _{\textsf{Prep}}$ that turns these into the function-dependent $([\![ \boldsymbol{\lambda _\alpha } ]\!], [\![ \boldsymbol{\lambda _\beta } ]\!],[\![ \boldsymbol{\lambda _\alpha }\star \boldsymbol{\lambda _\beta } - \boldsymbol{\lambda _\gamma } ]\!]_{*})$ is moved to the online phase $\varPi _{\textsf{MPC}}$. Crucially, the communication complexity of these steps is O(n|C|).

5.2 Online Phase

Finally, we present $\varPi _{\textsf{MPC}}$, Protocol 8, which instantiates $\mathcal {F}_{\textsf{MPC}}$ in the $\mathcal {F}_{\textsf{Prep}}$-hybrid model. This corresponds to the online phase, and at a high level it proceeds by maitaining the following invariant. For a wire $\alpha$ and a given assignment to the circuit inputs, let us denote by $v_\alpha$ the value held by wire $\alpha$. The protocol maintains that, for every wire $\alpha$, the parties have the values $\mu _\alpha := v_\alpha - \lambda _\alpha$ in the clear. This is ensured all the way up to the outputs, point in which the parties can reconstruct the associated masks and obtain the outputs. A major difference with respect to Turbopack [15] is that, in our case, we need to handle the case in which any of the steps that involve reconstructions—either in the offline or online phase—result in abort. For this, we let the parties restart the computation, kicking out the identified corrupt parties, which guarantees the new corruption threshold is 1/3. The parties make use of the $t<n/3$ MPC functionality for this $\mathcal {F}_{\mathsf {MPC\text {-} t<n/3}}$, but before doing that they use the initial VSS’ed masks $\langle \lambda _\alpha \rangle$ to ensure that the inputs provided to $\mathcal {F}_{\mathsf {MPC\text {-} t<n/3}}$ are consistent with these from the initial execution that resulted in abort.

We prove the following in the full version.

Theorem 4

$\varPi _{\textsf{MPC}}$ UC-realizes $\mathcal {F}_{\textsf{MPC}}$ in the $\mathcal {F}_{\textsf{Prep}}$-hybrid model, with probability $1-\texttt{negl}(\kappa )$.

Communication complexity. We now calculate the communication cost of $\varPi _{\textsf{MPC}}$ by calculating the cost of different parts:

• 1. Input gates: This involves each party broadcasting a batch of inputs per input group that it owns. Across all parties and all input groups possible, the cost of this step is bounded by $\textsf{P2P}(O(|C| n + n^4))$, $O(|C| n + n^4)\times \textsf{BC}(1)$.

• 2. Addition gates: This step is local so there is no communication cost.

• 3. Multiplication gates: Let $k = |C| / n^2$ be the total number of groups of multiplication gates in the circuit. For each group, we invoke a single $\textsf{reconstruct}$ which requires $\textsf{P2P}(O(n^3))$, $O(n^3)\times \textsf{BC}(1)$. Hence, the overall cost of this step is $\textsf{P2P}(O(|C| n))$, $O(|C| n)\times \textsf{BC}(1)$.

• 4. Output gates: Let $k = |C| / n$ be the total number of groups of output gates in the circuit. For each group, we invoke a single $\textsf{reconstruct}$ which requires $\textsf{P2P}(O(n^3))$, $O(n^3)\times \textsf{BC}(1)$. Hence, the overall cost of this step is $\textsf{P2P}(O(|C| n))$, $O(|C| n)\times \textsf{BC}(1)$.

• 5. Abort and restart: Let $c_I$ be the number of input wires. The cost of this step is $\textsf{P2P}(O(|C| n + c_I n^3))$, $O(c_I n^3)\times \textsf{BC}(1)$.

Combining all the costs, we get that the overall communication cost of $\varPi _{\textsf{MPC}}$ in the $\mathcal {F}_{\textsf{Prep}}$-hybrid model is $\textsf{P2P}(O(|C| n + c_I n^3 + n^4))$, $O(|C|n + c_I n^3 + n^4)\times \textsf{BC}(1)$. Assuming $C >> c_I \cdot n^2$, we get communication cost of $\textsf{P2P}(O(|C| n + n^4))$, $O(|C|n + n^4)\times \textsf{BC}(1)$.