On Fully-Secure Honest Majority MPC Without $n^2$ Round Overhead

Abstract

Fully secure multiparty computation (or guaranteed output delivery) among n parties can be achieved with perfect security if the number of corruptions t is less than n/3, or with statistical security with the help of a broadcast channel if $t<n/2$. In the case of $t<n/3$, it is known that it is possible to achieve linear communication complexity, but at a cost of having a round count of $\varOmega (\textsf{depth}(C) + n)$ in the worst case. The number of rounds can be reduced to $O(\textsf{depth}(C))$ by either increasing communication, or assuming some correlated randomness (a setting also known as the preprocesing model). For $t<n/2$ it is also known that linear communication complexity is achievable, but at the cost of $\varOmega (\textsf{depth}(C) + n^2)$ rounds, due to the use of a technique called dispute control. However, in contrast to the $t<n/3$ setting, it is not known how to reduce this round count for $t<n/2$ to $O(\textsf{depth}(C))$, neither allowing for larger communication, or by using correlated randomness.

In this work we make progress in this direction by taking the second route above: we present a fully secure protocol for $t<n/2$ in the preprocessing model, that achieves linear communication complexity, and whose round complexity is only $O(\textsf{depth}(C))$, without the additive $n^2$ term that appears from the use of dispute control. While on the $t<n/3$ such result requires circuits of width $\varOmega (n)$, in our case circuits must be of width $\varOmega (n^2)$, leaving it as an interesting future problem to reduce this gap. Our $O(\textsf{depth}(C))$ round count is achieved by avoiding the use of dispute control entirely, relying on a different tool for guaranteeing output. In the $t<n/3$ setting when correlated randomness is available, this is done by using error correction to reconstruct secret-shared values, but in the $t<n/2$ case the equivalent is robust secret-sharing, which guarantees the reconstruction of a secret in spite of errors. However, we note that a direct use of such tool would lead to quadratic communication, stemming from the fact that each party needs to authenticate their share towards each other party. At the crux of our techniques lies a novel method for reconstructing a batch of robustly secret-shared values while involving only a linear amount of communication per secret, which may also be of independent interest.

1 Introduction

Secure multiparty computation (MPC) is a set of techniques that enable a set of parties $P_1,\ldots ,P_n$, each $P_i$ having a private input $x_i$, to securely compute a function $z = f(x_1,\ldots ,x_n)$ while only involving communication among each other, in such a way that they learn the output z, and not even an adversary corrupting a subset of t parties can learn any information about the inputs $x_i$ from non-corrupted/honest parties, besides from what is inherently leaked by the result z.

Multiple MPC protocols exist depending on different factors like the power of the adversary, or the level of security required. A first important distinction is whether the adversary is passive, meaning that the behavior of corrupt parties is not affected (i.e. they follow the protocol specification), or whether he is active, meaning that the corrupt parties can deviate arbitrarily from the protocol execution. In this work we only consider active security, so from now on we assume the adversary under consideration is malicious, or active. Also, security can be computational, meaning that it is based on the hardness of some computational problem, or it can be information-theoretic, which means that security holds even against computationally unbounded adversaries. In the information-theoretic case there is a further distinction between perfect and statistical security, where the latter allows for a negligible error probability while the former achieves zero error probability.

Different techniques are used—and different results can be obtained—conditioning on the amount of parties t that the adversary is assumed to corrupt. If $t<n/3$ then we can achieve very efficient MPC with perfect security and with guaranteed output delivery (also abbreviated G.O.D., which means that the honest parties are guaranteed to receive the correct output z in spite of arbitrary adversarial behavior) [BTH08], and if $t<n/2$ then we can achieve the same but with statistical security, assuming a broadcast channel, which can be shown to be necessary [GSZ20]. Finally, if we do not assume any bound on t, then we must rely on computational assumptions, and the G.O.D. property (or even fairness, where the honest parties get the output if the adversary gets it) cannot be obtained in general. The focus of this work is the setting $t<n/2$, also known as honest majority. Furthermore, we assume the maximal case $n=2t+1$. From now on, whenever we refer to the setting $t<n/2$, we mean statistical security with an assumed broadcast channel, while for $t<n/3$ we mean perfect security without broadcast. In both cases we require full security, or G.O.D.

Several works have studied MPC in the honest majority setting. As we have mentioned, it is known that in this case G.O.D. with statistical security is attainable, with the help of a broadcast channel. Furthermore, this can be done while maintaining a total communication complexity of O(n|C|), where |C| is the size of the circuit to be computed (measured in the number of multiplication gates) [GSZ20]. This means that the total communication scales linearly with the number of parties, or put differently, the communication per party (i.e. after dividing by n) is constant in n. This is crucial for scalability, since this ensures each party does not communicate more as more parties join. Unfortunately, there is a major drawback of these works: the round complexity is given by $\varOmega (\textsf{depth}(C) + n^2)$. In contrast, weaker notions such as security with abort in the honest majority setting allow for a round complexity of $O(\textsf{depth}(C))$, without any dependency in n. This is good for cases where the underlying communication has high latency, and the number of parties is large enough so that $n^2$ extra rounds become too much of an overhead.

Dispute Control. To understand where this additive term of $n^2$ originates from, it is worth discussing at a high level the core ideas involved in existing G.O.D. constructions like [GSZ20, BSFO12, BTH06]. In short, these works operate by letting the parties compute the circuit in a gate-by-gate fashion, where the parties maintain the invariant that for each wire they hold secret-shares of the underlying value. Multiplication gates require interaction, and a malicious party may cause an error by misbehaving. To ensure that the computation can recover from this failure, a technique called dispute control, introduced in [BTH06], is used. With this method, upon detecting a failure, the parties execute a “localization” protocol whose purpose is to identify a pair of parties $\{P_i,P_j\}$ where at least one is guaranteed to be corrupt (we say that $P_i$ and $P_j$ are dispute with each other). At this point, the computation is attempted once again, but this time some machinery is put on top so that it is ensured that either (1) the computation succeeds, or (2) a new dispute is identified, that is, the same pair $\{P_i,P_j\}$ will not fall in a dispute again.

The techniques used for securely computing multiplication gates require linear communication complexity O(n) per gate, with interaction at each layer of the circuit, so in particular if there are no failures, the total communication is O(n|C|) distributed across $O(\textsf{depth}(C))$ rounds. Unfortunately, an active adversary can cause all new attempts to fail, generating the maximal number of disputes, which is $\varOmega (n^2)$. This would lead to a communication of $n^2\cdot \varOmega (n|C|) = \varOmega (n^3|C|)$ and $n^2\cdot \varOmega (\textsf{depth}(C))$ rounds, but fortunately this can be addressed by partitioning the circuit into segments and verifying the correctness of each of them, instead of checking the whole circuit. This way, at most $n^2$ segments are repeated, and by choosing segments of size $|C|/n^2$ we see that the overall communication remains O(n|C|). In terms of round count, letting d be the depth of each segment, the number of rounds is $O(\textsf{depth}(C))$ from the optimistic case, plus $\varOmega (n^2d)$ from the possible $n^2$ segments that are repeated in the worse case. Hence, the round complexity in the worst case becomes $\varOmega (\textsf{depth}(C) + n^2)$. We note that this is particularly prohibitive when n is moderately large, with the overhead being more and more noticeable for not so large values of $\textsf{depth}(C)$ (in particular when $\textsf{depth}(C) = o(n^2)$).

On the $<n/3$ Setting. We recall that honest majority protocols that achieve weaker notions such as security with abort achieve a round complexity of $O(\textsf{depth}(C))$. Currently, it is not known whether G.O.D. protocols with $O(\textsf{depth}(C)) + o(n^2)$ rounds exist, which shows that, in the honest majority case, there is an efficiency gap between security with abort and guaranteed output delivery. In contrast, the landscape turns out to be different for the $t<n/3$ case. There it is also possible to achieve linear communication complexity by making use of a tool called player elimination. This is similar to dispute control (and in fact, player elimination predates dispute control), with the difference that when a pair $\{P_i,P_j\}$ with at least one corrupt party is identified, both of these parties can be removed from the computation, before a reattempt.¹ This way, a segment is repeated at most O(n) times (since for every iteration there is one less corrupt party), so by taking segments of size |C|/n, linear communication is achieved with a round count of $\varOmega (\textsf{depth}(C) + n)$ in the worst case.

In stark contrast with the honest majority case, for $t<n/3$ it is actually possible to remove the overhead in n in the round complexity to obtain a protocol with $O(\textsf{depth}(C))$ rounds, and this can be done in two different ways:

• 1. Pay more in terms of communication, leading to works such as [AAPP22, AAY21] that have superlinear communication.²

• 2. Maintain linear communication, but assume correlated randomness, or in other words, consider a protocol in the preprocessing model.

The second approach above is based on the observation that, in player-elimination-based protocols such as [BTH08], the adversary can only cause the repetition of a segment in a preprocessing phase in which some correlated randomness is established. Once this is completed, the online phase is guaranteed to provide output “in one go”, without the need of repeating any segment (or splitting the remaining of the computation into segments, for that matter). We emphasize again that it is not known how to achieve $O(\textsf{depth}(C))$ round count for the honest majority case, not even giving up on linear communication complexity, or even assuming correlated randomness. Hence, this motivates the following question:

Can we design fully secure honest majority MPC protocols with statistical security that require $O(\textsf{depth}(C))$ rounds to securely compute a circuit C, either by having superlinear communication or assuming correlated randomness?

1.1 Our Contribution

As previously mentioned, for the $t<n/3$ setting with perfect security, such result is only known to be achievable by either allowing for superlinear communication complexity, or having linear communication but assuming correlated randomness. In this work we take the second route in the question above, and we present a statistically and fully secure MPC protocol for honest majority, that has a round complexity $O(\textsf{depth}(C))$ that is independent of n, and has linear communication complexity. One drawback of our protocol is that the claimed linear communication holds for circuits of width $\varOmega (n^2)$, while in the $t<n/3$ case this width requirement is a factor of n smaller. We leave it as interesting future work to further extend our techniques to tolerate circuits of width $\varOmega (n)$, hence narrowing down the gap between results for $t<n/2$ and $t<n/3$.

In more detail, we present an MPC protocol to securely compute a circuit |C| over a finite field $\mathbb {F}$, that has the following features:

• The protocol is set in the preprocessing model where the parties have access to some correlated randomness;

• The communication complexity is $O(n|C| + n^3\textsf{depth}(C))$, which is linear if $\textsf{depth}(C) = O(|C|/n^2)$, that is, each layer should contain $\varOmega (n^2)$ multiplication gates.

• The round complexity is $O(\textsf{depth}(C))$.

Our result is achieved by introducing novel ideas that remove the need of using dispute control techniques, in the preprocessing model. Qualitatively speaking, our approach offers several advantages with respect to protocols based on dispute control: the protocol proceeds in a gate-by-gate fashion (batching multiplication gates in the same layer), and handling each gate is guaranteed to be completed “in one go”, without the need of checking its correctness or repeating its computation. Furthermore, our protocol is also arguably simpler than dispute-control-based protocols, as it does not need to localize and handle disputes, repeat segments, or incur in any of the related complexities of using dispute control. In fact, one important advantage of our protocol we only require a broadcast channel for the input phase, while the rest of the computation can happen over point to point channels; in contrast, dispute-control-based protocols like [BTH06] require a broadcast channel throughout the whole computation.

At the heart of our techniques lies a new and non-trivial technique for reconstructing a batch of $n^2$ values that are secret-shared in a robust manner, while involving a communication complexity of $O(n^3)$, which ultimately leads to a communication of O(n) per reconstructed value. This may find several other applications in contexts where robust secret-sharing is used, like secure distributed storage.

1.2 Related Work

We already discussed some related work above, but here we present a more thorough discussion on relevant literature. In [HMP00], which is set in the $t<n/3$ setting, the idea of splitting the circuit into segments, together with the tool of player elimination, were introduced. This work makes use of verifiable secret-sharing and re-sharing á la [BOGW88, GRR98] in order to securely compute a given arithmetic circuit. This was later improved in [BTH08] by making use of multiplication triples, which, on top of achieving linear communication complexity, pushes the use of player elimination to the offline phase thanks to the use of error-correction techniques for the online phase. Any work that uses player elimination introduces an additive overhead of $\varOmega (n)$ in terms of the number of rounds, stemming from the need of re-running each segment every time a new semi-corrupt pair (a pair of parties where at least one of them is guaranteed to be corrupt) is identified. If one wishes to avoid this overhead, works such as [AAPP22, AAY21] achieve a round count of $O(\textsf{depth}(C))$, albeit with superlinear communication complexity. Substantial progress towards improving this trade-off was made in [AAPP23], where a perfectly secure protocol for $t<n/3$ with linear communication complexity (for certain class of circuits) and expected $O(\textsf{depth}(C))$ rounds was given.

In [BTH06] the dispute control framework, which is inspired by the player elimination framework, is introduced for the setting of $t<n/2$. This time, instead of removing an identified semi-corrupt pair, a mechanism is set in place so that these parties can keep participating in the protocol, and subsequent cheating leads to a new semi-corrupt pair being identified. To enable the identification of semi-corrupt pairs whenever cheating takes place, the secret-sharing structure must be enhanced by letting the parties hold shares of their shares, along with extra additional information in the form of tags under a message authentication code (MAC). Similarly to the player elimination technique, the use of dispute control introduces an additive overhead in terms of the number of rounds, this time of $n^2$, which corresponds to the maximum number of disputes that can occur.

The protocol in [BTH06] achieves a communication complexity of $O(|C|n^2\kappa )$ (ignoring non-dominant terms and broadcast calls), where $\kappa$ is the statistical security parameter. This was later improved in [BSFO12] to $O(|C|(n+\kappa ))$.³ Concrete constants (plus certain quadratic term that is affected by the depth of the circuit) are further improved in [GSZ20]. We remark, however, that these two works still make use of the core ideas introduced in [BTH06] regarding dispute control, splitting the circuit into segments and repeating each of these in case of cheating. As a result, they suffer from a $n^2$ overhead in terms of the number of rounds. This also holds for the work of [BGIN20], which is based on replicated secret-sharing.

Another important work is [IKP+16], where a transformation that takes a semi-honest honest majority protocol together with a fully-secure protocol with a potentially smaller threshold, and produces a fully-secure honest majority protocol, is presented. This achieved by adapting the IPS compiler [IKP+16] from the computational to the information-theoretic setting. However, their approach once again makes use of similar ideas as player elimination and dispute control, and hence they incur in an additive overhead of $\textsf{poly}(n)$ in terms of the number of rounds.⁴

1.3 Overview of Our Techniques

For aiding in terms of readability, we provide a high level overview of our techniques.

A Protocol for $t<n/3$ in the Preprocessing Model. In order to motivate our protocol, we begin by presenting a G.O.D. protocol (with perfect security) in the $t<n/3$ setting, that achieves linear communication complexity and only requires $O(\textsf{depth}(C))$ number of rounds. This is a simplified version of the protocol from [BTH08]. First, we introduce some notation: we consider a finite field $\mathbb {F}$, and use $\llbracket x \rrbracket _d$ to denote Shamir secret-sharing with degree d. At a high level, the protocol proceeds as the majority of secret-sharing-based protocols: the parties start with degree-t sharings of the inputs of the computation, and then they proceed in a gate-by-gate fashion by computing shares of the result of each gate, until shares of the output are obtained, which can then be reconstructed. Addition gates are processed locally with the help of the linearity properties of Shamir secret-sharing. For multiplication gates, the parties make use of the preprocessing model in the following way: given $\llbracket x \rrbracket _t$ and $\llbracket y \rrbracket _t$ to be multiplied, and given correlated randomness of the form $(\llbracket a \rrbracket _t,\llbracket b \rrbracket _t,\llbracket a\cdot b \rrbracket _t)$, where $a,b\in \mathbb {F}$ are uniformly random, (1) the parties compute locally $\llbracket d \rrbracket _t = \llbracket x \rrbracket _t - \llbracket a \rrbracket _t$ and $\llbracket e \rrbracket _t = \llbracket y \rrbracket _t - \llbracket b \rrbracket _t$, (2) they reconstruct these values to obtain d and e, and (3) the parties compute locally $\llbracket xy \rrbracket _t = e\llbracket a \rrbracket _t + d\llbracket b \rrbracket _t + \llbracket ab \rrbracket _t + de$.

The protocol is private given that a (and b) entirely hides x (and y) when reconstructing d (and e). Communication-wise, the complexity depends on how d and e are reconstructed. One way of doing this is letting each party announce their share of $\llbracket d \rrbracket _t$ (and $\llbracket e \rrbracket _t$) to each other party, who then reconstruct d (and e) from the received shares. A crucial property of Shamir secret-sharing with degree t is that, if $t<n/3$, then the t potentially incorrect shares provided by the corrupt parties can be error-corrected, and the receiving parties are guaranteed to be able to reconstruct the right underlying secret. In particular, every gate is guaranteed to succeed, so no repetitions are required and hence the number of rounds is $O(\textsf{depth}(C))$.

Getting Linear Communication Complexity. The approach sketched above, however, suffers from one major issue: since each party sends a share to every other party, communication is $\varOmega (n^2)$. We are interested in linear communication, so a different approach is required. A common idea to achieve linearity when reconstructing secret-shared values is to use a “relay”: all parties send their shares to a chosen party, say $P_1$, who reconstructs and forwards the result to the other parties. Unfortunately nothing prevents a corrupt $P_1$ from forwarding an incorrect value of their choice to the other parties. To handle this, a clever solution is given in [DN07], which consists of using multiple relays in such a way that, intuitively, there is always at least one honest relay who is guaranteed to reconstruct the right secret. However, special care is needed to really reduce communication to linear.

To do this reconstruction efficiently—while also guaranteeing successful reconstruction—the trick is to batch a collection of $t+1$ values to be reconstructed $\llbracket s_0 \rrbracket _t,\ldots ,\llbracket s_t \rrbracket _t$, define the polynomial $f(\texttt{Z}) = \sum _{\ell =0}^ts_\ell \cdot \texttt{Z}^\ell$, compute (locally) $\llbracket f(j) \rrbracket _t$ for $j\in [n]$, and reconstruct each f(j) towards each party $P_j$, who then relays this reconstructed value to the other parties. The main observation is that the parties can again apply error correction to $(f(1),\ldots ,f(n))$ in order to recover the polynomial $f(\texttt{Z}) = \sum _{\ell =0}^ts_\ell \cdot \texttt{Z}^\ell$, from which they can recover the secrets $s_0,s_1,\ldots ,s_t$. Notice that communication is still quadratic in n, but crucially, $t+1$ values have been reconstructed. Hence, if $t+1 = \varTheta (n)$ (e.g. if $n=3t+1$), then this is $O(n^2/(t+1)) = O(n)$ communication per secret, as desired. One can interpret $(f(1),\ldots ,f(n))$ as “Shamir sharings”, except that we are not interested in the zero point f(0), but rather in the polynomial $f(\texttt{Z})$ itself.

A First $\varOmega (n^2|C|)$ Protocol for Honest Majority. With the ideas for G.O.D. with $t<n/3$ in the preprocessing model, we are ready to tackle the $t<n/2$ case. We begin by presenting a construction that achieves quadratic communication, and then discuss how we improve this initial protocol to achieve linear communication complexity. First, we follow a similar template as the protocol above: the parties start with Shamir sharings $\llbracket \cdot \rrbracket _t$ of each input, proceed in a gate-by-gate manner, handling addition gates locally and multiplication gates using triples $(\llbracket a \rrbracket _t,\llbracket b \rrbracket _t,\llbracket ab \rrbracket _t)$, and finally reconstruct the output. Recall that, with this paradigm, a major bottleneck is the reconstruction of a secret-shared value $\llbracket s \rrbracket _t$, which in the $t<n/3$ setting is done while exploiting the error-correcting properties of Shamir secret-sharing. Unfortunately, for $t<n/2$, degree-t Shamir sharings do not satisfy error correction, and instead they only satisfy error detection, which ensures that either the correct secret is reconstructed by the receiver, or possibly no secret is reconstructed at all. At this point, one can obtain a protocol with abort, but it is not clear how to leverage this for G.O.D., besides making use of dispute control techniques to identify disputes and re-run some computation, which we want to avoid in order to only use $O(\textsf{depth}(C))$ rounds.

Our first observation towards solving this issue is that, even though in the honest majority setting it is not possible to perform error correction, there is a related notion that provides a similar functionality, and this is robust secret-sharing. In a robust secret-sharing scheme there is a share algorithm that enables the distribution of a secret into multiple shares, and there is a rec(onstruction) algorithm that, on input n shares among which t of them are potentially maliciously modified, outputs the correct underlying secret, with overwhelming probability. There are multiple robust secret-sharing constructions in the literature (cf. [BPRW16, FY19]). Normally, these schemes operate by letting each party obtain Shamir shares of the secret s, together with some authentication tags that enable each share owner to prove to the intended receiver that the share they send is correct. To check correctness of the received shares and tags, each party also receives some keys. Let us abstract this notion and denote by $\langle x \rangle$ when a value x is robustly secret-shared. It is common that these constructions satisfy some notion of linearity, meaning that the parties can locally compute $\langle x + y \rangle$ from $\langle x \rangle$ and $\langle y \rangle$. We will make use of this in what follows.

We can use $\langle \cdot \rangle$ as a building block instead of plain Shamir $\llbracket \cdot \rrbracket _t$ in the template above to obtain an honest majority G.O.D. protocol, where the preprocessing produces correlations of the form $(\langle a \rangle ,\langle b \rangle ,\langle ab \rangle )$. In its basic form, reconstruction would be done by letting the parties use the rec procedure towards every other party, which enables each party to successfully reconstruct each value needed for handling multiplication gates.⁵ However, this basic protocol is insufficient for our goals here, simply due to the reason that the resulting communication complexity is $\varOmega (n^2|C|)$. This stems from the fact that, whenever a shared value must be learned by all parties (which again, happens for every single multiplication gate), each single party must send their share and tags to each other single party.

Reducing to ${\boldsymbol{O(n|C|)}}$ for ${\boldsymbol{t<n/2}}$. Our core contribution consists of improving the approach from above, that achieves G.O.D. in the preprocessing model using quadratic communication via robust secret-sharing, to linear communication. $\varOmega (n^2)$ communication stems from the need of reconstructing a robustly-shared value towards all parties. Recall that a similar issue was faced when we sketched the protocol for $t<n/3$, and in page xx we discussed a solution to this problem originating in the ideas from [DN07]. Hence, our first approach is to try and adapt this idea from the secret-sharing scheme used there, namely plain Shamir secret-sharing $\llbracket \cdot \rrbracket$, to the robust scheme $\langle \cdot \rangle$ used here. Such adaptation would look like this: to reconstruct $t+1$ robustly-shared values $\langle s_0 \rangle ,\ldots ,\langle s_t \rangle$, (1) the parties define the polynomial $f(\texttt{Z}) = \sum _{\ell =0}^ts_\ell \cdot \texttt{Z}^\ell$, (2) they compute $\langle f(j) \rangle$ for $j\in [n]$ (which can be done using the homomorphic properties of $\langle \cdot \rangle$), (3) they reconstruct each f(j) towards each party $P_j$, who successfully reconstructs this f(j) using the robustness properties of $\langle \cdot \rangle$. At this point, $P_j$ is supposed to send f(j) to the other parties, who then recover $f(\texttt{Z})$ from these received values. However, here we face a fundamental issue: while this works in the $t<n/3$ case due to error correction, in our $t<n/2$ case the polynomial $f(\texttt{Z})$ cannot necessarily be recovered from the values $(f(1),\ldots ,f(n))$! This is precisely why robust secret-sharing was introduced: in order to guarantee reconstruction.

Our idea is to ensure that the parties are able to get not only “Shamir shares of $f(\texttt{X})$”, as above, but actual “robust shares of $f(\texttt{X})$”. In a bit more detail, our approach is to ensure the parties can obtain authentication information on the “Shamir shares” $(f(1),\ldots ,f(n))$, which guarantees that each receiver can successfully filter out incorrect f(i)’s, and hence reconstruct the polynomial $f(\texttt{Z})$, and with it the secrets $s_0,\ldots ,s_t$. An important problem here, however, is that we would need to devise a way to enable each $P_j$ to obtain tags on f(j), one for each receiver $P_k$. We now discuss at an intuitive level how this is addressed in our work.

Providing ${\boldsymbol{P_j}}$ with Authentication Information. Recall that $P_j$ holds f(j), which is a “Shamir share” of the polynomial $f(\texttt{Z})$, and $P_j$ sends f(j) to every other recipient $P_k$. We are missing a method by which $P_k$ can check the correctness of this f(j). To this end, imagine that $(f(1),\ldots ,f(n))$ were robust sharings of $f(\texttt{Z})$, that is, in addition to the share f(j), each party $P_j$ also holds a set of authentication tags $(\tau _{1j},\ldots ,\tau _{nj})$ on f(j). To reconstruct, $P_j$ provides $P_k$ with f(j) and $\tau _{kj}$, and $P_k$ uses $\tau _k$ to verify the correctness of f(j). Now, in our setting f(j) is not a “sharing” per se, as it is not the result of a dealer distributing robust shares, or linear combinations of these. Instead, $P_j$ obtained f(j) via a robust reconstruction of $\langle f(j) \rangle$.

Our idea is to enhance the robust secret-sharing scheme to allow for “nested” reconstruction: we let the parties also hold shares of $(\langle \tau _{1j} \rangle ,\ldots ,\langle \tau _{nj} \rangle )$, which can be reconstructed towards $P_j$ so that this party can obtain the tags $(\tau _{1j},\ldots ,\tau _{nj})$ on f(j), and hence prove correctness of f(j) to each other party $P_k$. The problem with this approach is that communication grows to $n^3$, given that each party must reconstruct n values towards each other party.

To alleviate this issue, consider a larger number of shares to be reconstructed, say n groups of $t+1$ sharings each (hence, there are $O(n^2)$ total shared values). If we first apply the idea above to each of the n groups, we obtain a communication of $n^4$, or $n^4/n^2 = n^2$ per reconstruction. However, here we make the crucial observation that, among these $n^4$ messages, the amount related to transmitting shares not related to authentication is $n^3$. Indeed, if authentication was not an issue, for each group, each $P_j$ would receive one share from each other party $P_i$, and each $P_j$ would send one share to each $P_k$, leading to $n^2$ elements, which is $n^3$ when the number of groups is factored in. As a result, the $n^4$ overhead is only coming from the transmission of authentication-related information. In the notation of the sketch above, this is originating from the reconstruction of the authentication tags $(\langle \tau _{1j} \rangle ,\ldots ,\langle \tau _{nj} \rangle )$ towards $P_j$ (one for each group), whose sole purpose is to enable $P_j$ to prove the correctness of f(j) towards $P_k$.

To achieve linear communication complexity, we note that all authentication information can be compressed across the n groups using random linear combinations, or in other words, the parties can distribute the authentication data of the n groups at the same cost of one single group. This results in $n^3$ communication in total for the $n^2$ reconstructions, or $n^3/n^2 =n$ per reconstruction, as desired. One must be careful when developing this idea in detail. First, a corrupt party can easily overcome a check that uses random linear combinations if he/she knows the random coefficients before adding the errors. To address this, in contrast to vanilla robust secret-sharing where each party can send their Shamir share at the same time as the authentication information, we require each party to “commit” to their errors by first sending their Shamir shares before sampling the random coefficients, and only then they distribute the associated authentication data. However, this new approach introduces another complication, which is that the random linear combination used to convince each $P_j$ of the reconstruction of f(j) cannot be the same as the one $P_j$ will use to convince each $P_k$ of the correctness of f(j). To this end, after $P_j$ has sent f(j) to each $P_k$, new random coefficients are sampled, and the parties robustly reconstruct towards $P_j$ the necessary authentication data (using these coefficients) to convince $P_k$ of the correctness of f(j).

This high level idea is materialized in detail in Sect. 3, where we show how to efficiently and robustly reconstruct secret-shared values. The robust secret-sharing scheme we use is introduced in Sect. 2.

1.4 Notation

We let $\mathbb {F}$ be a finite field with $|\mathbb {F}|> \textsf{poly}(n)\cdot 2^{\kappa }$, where $\kappa$ is the statistical security parameter. We use [k] to denote the set $\{1,\ldots ,k\}$. $\mathbb {F}_{\le d}[\texttt{X}]$ denotes the vector space of polynomials over $\mathbb {F}$ of degree at most d, on the variable $\texttt{X}$. For security definitions in MPC we refer the reader to standard references such as [CDN15].

2 Robust Secret-Sharing

The main tool we make use of in our work is that of robust secret-sharing, which enables the properties of error correction, a secret to be distributed into multiple shares. Concretely, we introduce the following construction.

Definition 1

We define the sharing $\langle x \rangle$ for a secret $x \in \mathbb {F}$ to consist of

• a random sharing polynomial $F_0(\texttt{X})\in \mathbb {F}_{\le t}[\texttt{X}]$ subject $F_0(0) = x$,

• random randomizer polynomials $F_1(\texttt{X}),\ldots ,F_t(\texttt{X})\in \mathbb {F}_{\le t}[\texttt{X}]$

• random key polynomials $A_0(\texttt{Y}),\ldots ,A_t(\texttt{Y}) \in \mathbb {F}_{\le t}[\texttt{Y}]$, and

• the checking polynomial $C(\texttt{X},\texttt{Y})\in \mathbb {F}_{\le t,\le t}[\texttt{X},\texttt{Y}]$ given by

  $$\begin{aligned} C(\texttt{X},\texttt{Y}) = F_0(\texttt{X}) \cdot A_0(\texttt{Y}) + F_1(\texttt{X}) \cdot A_1(\texttt{Y}) + \cdots + F_t(\texttt{X}) \cdot A_t(\texttt{Y}) \, . \end{aligned}$$

  (1)

Every party $P_i$ is given $F_0(i), F_1(i),\ldots , F_t(i)$ and $A_0(i), A_1(i),\ldots , A_t(i)$ as well as the (coefficients of the) polynomial $C(\texttt{X},i)$.

With the definition above, we note that the view of party $P_i$ is given by

$$ \textsf{view}_i(\langle x \rangle ) = \big (A_0(i), A_1(i),\ldots , A_t(i),F_0(i), F_1(i),\ldots , F_t(i),C(\texttt{X},i) \big ); $$

similarly, $\textsf{view}_\mathcal{A}(\langle x \rangle )$ denotes the joint view of a set $\mathcal A$ of parties. For multiple secrets, their sharings are defined as above, but with the same key polynomials $A_0(\texttt{Y}),\ldots ,A_t(\texttt{Y})$ yet random and independent sharing and randomizer polynomials. In other words, the key polynomials $A_0(\texttt{Y}),\ldots ,A_t(\texttt{Y})$ are sampled uniformly at random once and for all, and the sharing and randomizer polynomials are sampled freshly for each x uniformly at random subject to the given constraint, i.e., $F_0(0) = x$.

To have simpler notation and more concise expressions, we introduce the polynomial vectors ${\boldsymbol{F}}(\texttt{X}) = \big (F_0(\texttt{X}), \ldots , F_t(\texttt{X})\big ) \in \mathbb {F}_{\le t}[\texttt{X}]^{t+1}$ and ${\boldsymbol{A}}(\texttt{X}) = \big (A_0(\texttt{Y}),\ldots , A_t(\texttt{Y})\big )\in \mathbb {F}_{\le t}[\texttt{Y}]^{t+1}$, which allows us to re-write (1) very compactly as

$$\begin{aligned} C(\texttt{X},\texttt{Y}) = {\boldsymbol{F}}(\texttt{X}) \cdot {\boldsymbol{A}}(\texttt{Y}) \, . \end{aligned}$$

(2)

A sharing $\langle x \rangle$ is then a random triple $\big ({\boldsymbol{A}}(\texttt{Y}),{\boldsymbol{F}}(\texttt{X}),C(\texttt{X},\texttt{Y})\big )$ subject to $F_0(0) = x$ and (2), and the view of $P_i$ (and similar for a set of parties) becomes $\textsf{view}_i(\langle x \rangle ) = \big ({\boldsymbol{A}}(i),{\boldsymbol{F}}(i),C(\texttt{X},i)\big )$.

It follows immediately from (2) and the fact that ${\boldsymbol{A}}(\texttt{Y})$ is reused for different sharings, that linear functions can be computed on shared values by obvious local computations. We will use the notation $\langle x+y \rangle \leftarrow \langle x \rangle + \langle y \rangle$ for local additions, and similarly for more general affine combinations.

Lemma 1 below ensures that a sharing $\langle x \rangle$ of a secret x leaks no information on x to any t parties, except with negligible probability.

Lemma 1

For any set $\mathcal A$ of t (or fewer) parties, and for a random key polynomial vector ${\boldsymbol{A}}(\texttt{Y})$, the following holds except with probability $1/|\mathbb {F}|$ over the choice of ${\boldsymbol{A}}(\texttt{Y})$: The distribution of $\textsf{view}_\mathcal{A}(\langle x \rangle )$ conditioned on ${\boldsymbol{A}}(\texttt{Y})$ does not depend on the value of x.

Proof

Without loss of generality, we may assume $\mathcal{A} = \{P_1,\ldots ,P_t\}$. We consider an arbitrary but fixed choice of ${\boldsymbol{A}}(\texttt{Y})$, and we show the claimed independence to hold unless the $(t \times t)$-matrix with entries $A_i(j)$ for $i,j \in [t]$ is singular, which happens with probability $1/|\mathbb {F}|$ for a random ${\boldsymbol{A}}(\texttt{Y})$.

Let $K_0(\texttt{X})\in \mathbb {F}_{\le t}[\texttt{X}]$ be the (unique) polynomial with $K_0(0) = 1$ yet $K_0(1) = \cdots = K_0(t) = 0$. Also, let $K_1(\texttt{X}),\ldots ,K_t(\texttt{X})$ be such that also here $K_\ell (1) = \cdots = K_\ell (t) = 0$ for $\ell \in [t]$, but now $K_1(0) \cdot A_1(j) + \cdots + K_t(0) \cdot A_t(j) = - A_0(j)$ for $j \in [t]$. This exists due to the assumption on ${\boldsymbol{A}}(\texttt{Y})$. The above conditions ensure that $K_1(\texttt{X}) \cdot A_1(j) + \cdots + K_t(\texttt{X}) \cdot A_t(j) = - K_0(\texttt{X}) \cdot A_0(j) \, ,$ and thus ${\boldsymbol{K}}(\texttt{X}) \cdot {\boldsymbol{A}}(j) = 0$, for $j \in [t]$. Then, for any $\delta \in \mathbb {F}$, the pair consisting of ${\boldsymbol{F}}'(\texttt{X}) := {\boldsymbol{F}}(\texttt{X}) + \delta \cdot {\boldsymbol{K}}(\texttt{X})$ and $C'(\texttt{X},\texttt{Y}) := {\boldsymbol{F}}'(\texttt{X}) \cdot {\boldsymbol{A}}(\texttt{Y})$, together with ${\boldsymbol{A}}(\texttt{Y})$, forms a sharing $\langle x' \rangle$ for the secret $x' = x+\delta$, for which the parties $P_1,\ldots ,P_t$ have the same view; namely ${\boldsymbol{F}}'(i) := {\boldsymbol{F}}(i)$ and $C'(\texttt{X},i) = \big ({\boldsymbol{F}}(\texttt{X}) + \delta \cdot {\boldsymbol{K}}(\texttt{X})\big ) \cdot {\boldsymbol{A}}(i) = {\boldsymbol{F}}(\texttt{X}) \cdot {\boldsymbol{A}}(i) = C(\texttt{X},i)$ for all $i \in [t]$. Furthermore, the above mapping from $\big ({\boldsymbol{F}}(\texttt{X}),C(\texttt{X},\texttt{Y})\big )$ to $\big ({\boldsymbol{F}}'(\texttt{X}),C'(\texttt{X},\texttt{Y})\big )$ is bijective, which proves the claim of the statement.    $\square$

Recall that $P_i$’s share vector ${\boldsymbol{s}}_i = {\boldsymbol{F}}(i)$ satisfies ${\boldsymbol{s}}_i \cdot {\boldsymbol{A}}(j) = C(i,j)$, and so any incorrect share vector ${\boldsymbol{s}}'_i \ne {\boldsymbol{s}}_i$ satisfies ${\boldsymbol{s}}'_i \cdot {\boldsymbol{A}}(j) = C(i,j)$ if and only if $({\boldsymbol{s}}_i - {\boldsymbol{s}}'_i) \cdot {\boldsymbol{A}}(j) = 0 \, ,$ which happens with probability $1/|\mathbb {F}|$ only when ${\boldsymbol{A}}(j)$ is random. Thus, Lemma 2 below implies that the set $\mathcal A$ of corrupt parties will find an incorrect share vector that will be accepted by honest $P_j$ with probability $1/|\mathbb {F}|$ only, even if they get to see the entire sharing polynomial vector ${\boldsymbol{F}}(\texttt{X})$. Hence, any honest $P_j$ can filter out all incorrect share vectors ${\boldsymbol{s}}'_i \ne {\boldsymbol{s}}_i$, allowing him to reconstruct the polynomial vector ${\boldsymbol{F}}(\texttt{X})$, and thus ${\boldsymbol{F}}(0)$ and the actual secret $x = F_0(0)$.

Lemma 2

For any set $\mathcal A$ of t (or fewer) parties, for any $j \not \in \mathcal A$, and for any $x \in \mathbb {F}$, the key vector ${\boldsymbol{A}}(j)$ is uniformly random and independent of the pair $\big (\textsf{view}_\mathcal{A}(\langle x \rangle ),{\boldsymbol{F}}(\texttt{X})\big )$.

Proof

Again, we may assume $\mathcal{A} = \{P_1,\ldots ,P_t\}$. Let $K(\texttt{Y}) \in \mathbb {F}_{\le t}[\texttt{Y}]$ be such that $K(1) = \cdots = K(t) = 0$ and $K(j) = 1$. Then, for any vector ${\boldsymbol{\delta }}\in \mathbb {F}^{t+1}$ the triple consisting of ${\boldsymbol{A}}'(\texttt{Y}) = {\boldsymbol{A}}(\texttt{Y}) + K(\texttt{Y}) \cdot {\boldsymbol{\delta }}$, ${\boldsymbol{F}}(\texttt{X})$ and $C'(\texttt{X},\texttt{Y}) = {\boldsymbol{F}}(\texttt{X}) \cdot {\boldsymbol{A}}'(\texttt{Y})$ forms a sharing $\langle x \rangle$ of x for which the parties $P_1,\ldots ,P_t$ have the same view, but now with $P_j$ having key vector ${\boldsymbol{A}}'(j) = {\boldsymbol{A}}(j) + {\boldsymbol{\delta }}$. Furthermore, the above mapping from $\big ({\boldsymbol{A}}(\texttt{Y}),{\boldsymbol{F}}(\texttt{X}),C(\texttt{X},\texttt{Y})\big )$ to $\big ({\boldsymbol{A}}'(\texttt{Y}),{\boldsymbol{F}}(\texttt{X}),C'(\texttt{X},\texttt{Y})\big )$ is bijective, which proves the claim of the statement.    $\square$

From the above, we see that a secret-shared value $\langle x \rangle$ can be reconstructed towards a given receiver $P_j$, in such a way that $P_j$ is guaranteed to obtain the correct secret. More precisely, each party $P_i$ sends their share vector $\boldsymbol{s}_i = \boldsymbol{F}(i)$ to the receiver $P_j$, who checks that $\boldsymbol{s}_i\cdot \boldsymbol{A}(j) = C(i,j)$ for every $i\in [n]$. There are at least $t+1$ honest shares $\boldsymbol{s}_i$ that will pass the check, and due to Lemma 2 above, any incorrect share will fail the check with overwhelming probability. Hence, $P_j$ will have sufficient correct shares to reconstruct the right secret: from the $\ge t+1$ shares $\boldsymbol{s}_i = (F_0(i),\ldots ,F_t(i))$ that pass the check, $P_j$ uses the corresponding $F_0(i)$’s to reconstruct the secret $x = F_0(0)$. We call this procedure $\pi _{\textsf{QuadRec}}(\langle x \rangle )$.

3 Efficient Reconstruction

It is possible to securely evaluate any arithmetic circuit over $\mathbb {F}$ with using our robust secret-sharing solution and multiplication triples $(\langle a \rangle ,\langle b \rangle ,\langle ab \rangle )$ from the preprocessing model: to add two robustly shared values the parties use the linearity properties of $\langle \cdot \rangle$, and to multiply they make use of the multiplication triples by first opening $d\leftarrow \langle x \rangle -\langle a \rangle$ and $e\leftarrow \langle y \rangle -\langle b \rangle$, and then computing locally $\langle xy \rangle \leftarrow e\langle a \rangle + d\langle b \rangle + \langle ab \rangle + de$. Reconstruction is guaranteed to result in the correct d and e, which ensures correctness, which is also the same property that guarantees the final output can be reconstructed correctly.

Since our goal is to achieve linear communication, we must design a way of reconstructing a series of shared values robustly and with linear communication per secret, which is precisely what we discuss in this section. Jumping ahead, our protocol will reconstruct $n^2$ secrets with $O(n^3)$ communication per secret, which means O(n) per secret amortized. In the MPC protocol sketched above⁶ each multiplication gate requires two reconstructions, and all reconstructions corresponding to multiplication gates in a single layer can be batched together. This means we need $n^2/2 = O(n^2)$ multiplication gates per layer (in average) to get the linear communication benefits from our reconstruction procedure, which is where the circuit width requirements of our results come from.

3.1 Towards Efficient Reconstruction

The naive approach of reconstructing a shared value by every party sending their share to every other party has quadratic complexity even when ignoring additional information, like tags etc., that are needed to filter out incorrect shares. In other words, just communicating the actual Shamir shares produces a too large overhead. For passive security, one can reconstruct a Shamir-shared value by sending the shares to a single party, who reconstructs and acts as a relay by sending the result to the other parties. In the actively secure setting, the work of [DN07] introduces a technique to achieve linear communication when reconstructing a batch of Shamir-shared values, essentially by using a different honest party to reconstruct each different value. However, for guaranteed output delivery this trick requires error correction, which is possible when $t<n/3$, but does not work in the $t<n/2$ regime, where only error detection is possible.

Here, we show how to reconcile the trick from [DN07] with the sharing $\langle x \rangle$ introduced above so that the (amortized) communication of the actual Shamir shares $s_i = F_0(i)$ becomes linear. However, the resulting reconstruction approach will still involve quadratic communication, but crucially, the super-linear overhead will be “only” due to the tags, i.e., the remaining coordinates of ${\boldsymbol{F}}(i)$. We address this in Sect. 3.2, where we show how this quadratic communication can be taken care of. This is done, in essence, by batching together sufficiently many openings and using a single set of tags to verify a random linear combination.

Consider $t+1$ sharings $\langle x^{(0)} \rangle ,\ldots ,\langle x^{(t)} \rangle$ that need to be reconstructed. They are given by $t+1$ triples $\bigl ({\boldsymbol{A}}(\texttt{Y}),{\boldsymbol{F}}^{(\ell )}(\texttt{X}),C^{(\ell )}(\texttt{X},\texttt{Y})\bigr )$ with the same ${\boldsymbol{A}}(\texttt{Y})$ and with $C^{(\ell )}(\texttt{X},\texttt{Y}) = {\boldsymbol{F}}^{(\ell )}(\texttt{X}) \cdot {\boldsymbol{A}}(\texttt{Y})$. Inspired by the basic idea from [DN07], we consider ${\boldsymbol{F}}(\texttt{X},\texttt{Z}) = \sum _{\ell =0}^t \texttt{Z}^\ell \cdot {\boldsymbol{F}}^{(\ell )}(\texttt{X})$ and $C(\texttt{X},\texttt{Y},\texttt{Z}) = \sum _{\ell =0}^t \texttt{Z}^\ell \cdot C^{(\ell )}(\texttt{X},\texttt{Y})$ which satisfy $C(\texttt{X},\texttt{Y},\texttt{Z}) = {\boldsymbol{F}}(\texttt{X},\texttt{Z}) \cdot {\boldsymbol{A}}(\texttt{Y})$. The reconstruction then proceeds as follows:

• 1. Each $P_i$ sends ${\boldsymbol{F}}(i,j) = \sum _\ell j^\ell {\boldsymbol{F}}^{(\ell )}(i)$ to $P_j$.

• 2. Each $P_j$ checks that $C(i,j,j) = {\boldsymbol{F}}(i,j) \cdot {\boldsymbol{A}}(j)$ for $i\in [n]$, and $P_j$ reconstructs ${\boldsymbol{F}}(0,j)$ from the values that pass the check.

• 3. Each $P_j$ sends to each $P_k$ the vector ${\boldsymbol{F}}(0,j)$.

• 4. Each $P_k$ checks that $C(0,k,j) = {\boldsymbol{F}}(0,j) \cdot {\boldsymbol{A}}(k)$ for each $j\in [n]$, and then $P_k$ reconstructs ${\boldsymbol{F}}(0,\texttt{Z})$ from the values ${\boldsymbol{F}}(0,j)$ that pass the check. From ${\boldsymbol{F}}(0,\texttt{Z})$ one can then read out ${\boldsymbol{F}}^{(0)}(0),\ldots ,{\boldsymbol{F}}^{(t)}(0)$ and thus $x^{(0)},\ldots ,x^{(t)}$.

The key idea in our protocol above is the following. When $P_j$ receives the vectors ${\boldsymbol{F}}(1,j),\ldots ,{\boldsymbol{F}}(n,j)$ in step 1, $P_j$ can filter out incorrect shares and hence reconstruct ${\boldsymbol{F}}(0,j)$, so in particular $P_j$ obtains the “secret” $F_0(0,j)$, which is relayed to each other party $P_k$. However, the main observation is that $P_j$ also obtained as a “byproduct” the other points $(F_1(0,j),\ldots ,F_t(0,j))$, and it turns out these can be used for $P_j$ to convince each receiver $P_k$ of the correctness of $F_0(0,j)$. In a bit more detail, we make the crucial observation that ${\boldsymbol{F}}(\texttt{X},j)$ are the share vectors corresponding to the sharing $\big ({\boldsymbol{A}}(\texttt{Y}),{\boldsymbol{F}}(\texttt{X},j),C(\texttt{X},\texttt{Y},j)\big )$. So, from the discussion before Lemma 2, an honest $P_j$ will indeed be able to recover ${\boldsymbol{F}}(0,j)$. Similarly the ${\boldsymbol{F}}(0,j)$’s sent to $P_k$ in step 3. are the share vectors corresponding to the sharing $\big ({\boldsymbol{A}}(\texttt{Y}),{\boldsymbol{F}}(0,\texttt{Z}),C(0,\texttt{Y},\texttt{Z})\big )$, allowing each $P_k$ to recover ${\boldsymbol{F}}(0,\texttt{Z})$.

3.2 Batched Verification

Unfortunately, the above reconstruction still has quadratic amortized complexity. This originates in the fact that, in the first (and third) step, each party sends a length-$(t+1)$ vector to each other party. However, the crucial observation is that if we do not count the information that is “only” sent for checking purposes, e.g., if in step 1. we only count the first coordinate $F_0(i,j)$ of ${\boldsymbol{F}}(i,j)$, then we actually have linear amortized complexity.

Due to this observation, we can get the aspired amortized linear complexity by doing the verification in batches, that is, compressing the checking information of a number of reconstructions without increasing the associated communication costs. Concretely, we consider the reconstruction of n groups of $t+1$ secrets each: $\langle x^{(m,0)} \rangle ,\ldots ,\langle x^{(m,t)} \rangle$ for $m\in \{0,\ldots ,n-1\}$. Intuitively, our protocol with linear communication complexity is obtained by running, for each $m\in \{0,\ldots ,n-1\}$, the solution from the previous section, but ignoring the checking information. That is, step 1. from the previous section is modified by letting each $P_i$ compute $\boldsymbol{F}^{(m)}(i,\texttt{Z}) = \sum _{\ell =0}^t\texttt{Z}^\ell \boldsymbol{F}^{(m,\ell )}(i)$, but $P_i$ only sends the first coordinate $F_{0}^{(m)}(i,j)$ to $P_j$. For each other coordinate $h\in [t]$, $P_i$ sends a compressed version $F_h(i,j) = \sum _{m=0}^{n-1}\xi ^mF_h^{(m)}(i,j)$, where $\xi \in \mathbb {F}$ is a fresh uniformly random value known by all parties.⁷This can still be used by $P_j$ to filter out incorrect shares and hence reconstruct $F_0^{(m)}(0,j)$ for $m\in \{0,\ldots ,n-1\}$. Then, $P_j$ relays these values to each other party $P_k$.

The challenge now is that, to interpolate $F_0^{(m)}(0,\texttt{Z})$ and hence learn the reconstructed secrets, $P_k$ requires certain checking information to verify the validity of the values $F_0^{(m)}(0,j)$ sent by $P_j$. In step 3. from Sect. 3.1, such information corresponds to $(F_1^{(m)}(0,j),\ldots ,F_t^{(m)}(0,j))$, but $P_j$ does not have the means to send this to $P_k$ as $P_j$ only received $(F_1(0,j),\ldots ,F_t(0,j))$, which is a compressed version of these values (and moreover, even if $P_j$ had this data, sending it to each $P_k$ would be too costly). The solution once again is to apply compression. A first thought would be to let $P_j$ send $(F_1(0,j),\ldots ,F_t(0,j))$ to $P_k$, who can use these values to check the correctness of $F_0^{(0)}(0,j),\ldots ,F_0^{(n-1)}(0,j)$ by verifying the correctness $F_0(0,j) = \sum _{m=0}^{n-1}\xi ^mF_0^{(m)}(0,j)$ instead. However, this does not work since $P_j$ already knows $\xi$ before sending each $F_0^{(m)}$, so $P_j$ can correct any error present in these terms.

The solution here is to sample a new fresh random challenge $\omega$, after $P_j$ has “committed” to the values $F_0^{(m)}$ by sending them to each $P_k$, and use the compressed check as above but with this new term for the linear combination. The problem now is that, for $h\in [t]$, $P_j$ holds $F_h(0,j) = \sum _{m=0}^{n-1}\xi ^mF_h^{(m)}(0,j)$, but not the necessary $F_h'(0,j) = \sum _{m=0}^{n-1}\omega ^mF_h^{(m)}(0,j)$ to convince each receiver $P_k$. To address this we simply let the parties run the “checking part” of the first part of the protocol above but using the challenge $\omega$ instead of $\xi$. More precisely, each $P_i$ sends $F_h'(i,j)= \sum _{m=0}^{n-1}\omega ^mF_h^{(m)}(0,j)$ to $P_j$, who uses this values to interpolate $F_h'(0,j)$, which $P_j$ sends to $P_k$. The details of this protocol are provided below.

Theorem 1

After executing procedure $\pi _{\textsf{LinRec}}$ on input $(\langle x^{(m,\ell )} \rangle )_{\ell \in \{0,\ldots ,t\},m\in \{0,\ldots ,n-1\}}$, each party $P_k$ outputs the correct secrets $x^{(m,\ell )}$, except with probability $3t(n+1)/|\mathbb {F}|$. Moreover, the protocol requires linear communication complexity and makes use of a constant number of rounds.

Proof

The claim on the number of rounds is verified by inspection. It is also easy to check that the total communication is $\varTheta (n^3)$, and when we divide by the $(t+1)n = \varTheta (n^2)$ elements being reconstructed, we obtain an amortized communication of $\varTheta (n)$ per secret, as required.

Now, we prove the correctness and security of the protocol. To this end, we begin with the following claim.

Claim

In step 5, each $P_j$ interpolates the correct $\boldsymbol{F}(\texttt{X},j)$, except with probability $t(n+1)/|\mathbb {F}|$.

Proof (of claim)

Let us consider a malicious party $P_i$ who sends incorrect $\{F_0^{(m)}(i,j)+\epsilon ^{(m)}_0\}_{m=0}^{n-1}$, and $(F_1(i,j)+\epsilon _1,\ldots ,F_t(i,j)+\epsilon _t)$, to $P_j$. Assume that at least one $\epsilon _0^{(m)}$ is not zero. The check that $P_j$ performs is

$$\sum _{h=0}^t(F_h(i,j) + \epsilon _h)\cdot A_h(j) = \sum _{m=0}^{n-1}\sum _{\ell =0}^t\xi ^{m}j^\ell \cdot C^{(m,\ell )}(i,j),$$

where $\epsilon _0 = \sum _{m=0}^{n-1}\xi ^m\epsilon ^{(m)}_0$. Notice that the distribution of $\{\epsilon ^{(m)}_0\}_{m=0}^{n-1}$ is independent of $\xi$ since $P_i$ sent $\{F_0^{(m)}(i,j)+\epsilon ^{(m)}_0\}_{m=0}^{n-1}$ to $P_j$ before the value $\xi$ was opened. Hence, since at least one $\epsilon ^{(m)}_0$ is not zero, Schwartz-Zippel lemma implies that $\epsilon _0$ is also not zero except with probability at most $(n-1)/|\mathbb {F}|$.

It can be checked that the right hand side is equal to $\sum _{h=0}^tF_h(i,j)\cdot A_h(j)$, so in particular the check passes if and only if $\sum _{h=0}^t\epsilon _h\cdot A_h(j) = 0$. From the above, except with probability at most $|\mathbb {F}|^{-1}$, the vector $\boldsymbol{\epsilon }$ is not zero. Furthermore, from Lemma 2 we have that, except with probability $|\mathbb {F}|^{-1}$, the vector $\boldsymbol{A}(j)$ looks uniformly random to the adversary. Hence, we see that except with probability $(n-1)/|\mathbb {F}| + 1/|\mathbb {F}| = n/|\mathbb {F}|$, the adversary passes the check if and only if a dot product between a random vector and a non-zero vector results in zero. This can happen only with probability $1/|\mathbb {F}|$. Hence, except with probability $1-(n+1)/|\mathbb {F}|$, the shares received by $P_i$ are rejected.

From the above we see that the probability that $P_j$ accepts an incorrect share is at most $(n+1)/|\mathbb {F}|$. Since there are at most t malicious parties, we have that the probability that there is at least one incorrect share accepted by $P_j$ is at most $t(n+1)/|\mathbb {F}|$. Since the check for every honest party passes, and there are at least $t+1$ honest parties, $P_j$ successfully reconstructs the correct $\boldsymbol{F}(\texttt{X},j)$, except with the probability above. This completes the proof of the claim.

With the claim at hand, we see that with overwhelming probability, every honest party $P_j$ sends the correct $F_0^{(m)}(0,j)$ to each $P_k$ in step 6. In a completely similar way as the proof of the claim above, we can prove the following:

Claim

In step 10, each $P_j$ interpolates the correct $\boldsymbol{F}'(\texttt{X},j)$, except with probability $t(n+1)/|\mathbb {F}|$.

Proof (of claim)

We proceed in the same way as in the claim above, but replacing $\xi$ by $\omega$, and $(F_1(i,j)+\epsilon _1,\ldots ,F_t(i,j)+\epsilon _t)$ by $(F_1'(i,j)+\delta _1,\ldots ,F_t'(i,j)+\delta _t)$, where $\delta _h$ are the possible errors introduced by $P_i$ in step 8. The same proof works given that, as before, the error $\epsilon _0^{(m)}$ on $F_0^{(m)}$ is chosen by the adversary before sampling $\omega$. We do not write down the rest of the details.

This claim shows then that, with overwhelming probability, each honest $P_j$ will send to each $P_k$ the correct $(F_1'(0,j),\ldots ,F_t'(0,j))$ in Step 11, so in particular $P_k$ receives at least $t+1$ correct shares. This turns out to be enough for an honest $P_k$ to interpolate $F_0^{(m)}(0,\texttt{Z})$ correctly since, as the following claim illustrates, $P_k$ can filter out incorrect shares with overwhelming probability.

Claim

In step 13, $P_k$ interpolates the correct $F_0^{(m)}(0,\texttt{Z})$, except with probability at most $t(n+1)/|\mathbb {F}|$.

Proof (of claim)

The proof is similar to that of the previous two Lemmas 1 and 2. Consider a malicious $P_j$ who sends $\{F_0^{(m)}(0,j) + \delta _0^{(m)}\}_{m=0}^{n-1}$ to $P_k$ in step 6, and also $(F_1'(0,j)+\delta _1,\ldots ,F_t'(0,j)+\delta _t)$ in step 11. The check that $P_k$ carries out is then

$$\sum _{h=0}^t(F'_h(0,j) + \delta _h)\cdot A_h(j) = \sum _{m=0}^{n-1}\sum _{\ell =0}^t\omega ^{m}j^\ell \cdot C^{(m,\ell )}(0,j),$$

where $\delta _0 = \sum _{m=0}^{n-1}\omega ^{m}\delta _0^{(m)}$. The right-hand side equals $\sum _{h=0}^tF'_h(0,j)\cdot A_h(j)$, so the check passes if and only if $\sum _{h=0}^t\delta _h\cdot A_h(j) = 0$. Here, we proceed as with the proofs of the previous claims, noticing that $\{\delta _0^{(m)}\}_{m=0}^{n-1}$ is chosen by the adversary before seeing the challenge $\omega$, so $\delta _0\ne 0$ with probability at least $1-(n-1)/|\mathbb {F}|$. Following similar steps as the previous proofs, we obtain that $P_k$ accepts an incorrect share with probability at most $(n+1)/|\mathbb {F}|$. Hence, the probability that $P_k$ reconstructs an incorrect $F_0^{(m)}(0,\texttt{Z})$ is at most $t(n+1)/|\mathbb {F}|$, as stated in the claim.

Putting together what we have seen above, we obtain that, except with probability $3t(n+1)/|\mathbb {F}|$, each $P_k$ reconstructs the correct secrets. Thus, the theorem is proven.    $\square$