key: cord-0061123-8h2gyudx
authors: Hazay, Carmit; Venkitasubramaniam, Muthuramakrishnan; Weiss, Mor
title: The Price of Active Security in Cryptographic Protocols
date: 2020-03-25
journal: Advances in Cryptology - EUROCRYPT 2020
DOI: 10.1007/978-3-030-45724-2_7
sha: 8a388d59bf21a78f18e3220aa5f2ec38530715d7
doc_id: 61123
cord_uid: 8h2gyudx

We construct the first actively-secure Multi-Party Computation (MPC) protocols with an arbitrary number of parties in the dishonest majority setting, for an arbitrary field [Formula: see text] with constant communication overhead over the “passive-GMW” protocol (Goldreich, Micali and Wigderson, STOC ‘87). Our protocols rely on passive implementations of Oblivious Transfer (OT) in the boolean setting and Oblivious Linear function Evaluation (OLE) in the arithmetic setting. Previously, such protocols were only known over sufficiently large fields (Genkin et al. STOC ‘14) or a constant number of parties (Ishai et al. CRYPTO ‘08). Conceptually, our protocols are obtained via a new compiler from a passively-secure protocol for a distributed multiplication functionality [Formula: see text] , to an actively-secure protocol for general functionalities. Roughly, [Formula: see text] is parameterized by a linear-secret sharing scheme [Formula: see text] , where it takes [Formula: see text] -shares of two secrets and returns [Formula: see text] -shares of their product. We show that our compilation is concretely efficient for sufficiently large fields, resulting in an overhead of 2 when securely computing natural circuits. Our compiler has two additional benefits: (1) it can rely on any passive implementation of [Formula: see text] , which, besides the standard implementation based on OT (for boolean) and OLE (for arithmetic) allows us to rely on implementations based on threshold cryptosystems (Cramer et al. Eurocrypt ‘01); and (2) it can rely on weaker-than-passive (i.e., imperfect/leaky) implementations, which in some parameter regimes yield actively-secure protocols with overhead less than 2. Instantiating this compiler with an “honest-majority” implementations of [Formula: see text] , we obtain the first honest-majority protocol with optimal corruption threshold for boolean circuits with constant communication overhead over the best passive protocol (Damgård and Nielsen, CRYPTO ‘07).

The problem of Secure Multi-party Computation (MPC) considers a set of parties with private inputs that wish to jointly compute a function of their inputs while simultaneously preserving correctness of the outputs, and guaranteeing overhead (even asymptotically) are known, both in the honest and the dishonest majority settings. For arithmetic computations with an arbitrary number of parties and over sufficiently large fields, the best concrete overhead (of 12x [17] ) still seems large. In the honest majority setting an overhead of 2 has been achieved only for large fields [9] .

Given this state of affairs, in this work we set out to answer the following fundamental open problem:

Can actively-secure protocols over an arbitrary field match the complexity of passively-secure protocols, in the dishonest and honest majority settings, with an arbitrary number of parties ? We resolve this open problem in terms of communication complexity in the affirmative, designing an asymptotically-efficient actively-secure protocol for boolean circuits (as well as arithmetic circuits over any field) in both the honest majority and dishonest majority settings, with constant communication overhead over the (best known) passively-secure counterparts.

We note that constant-overhead protocols are known based on general zeroknowledge proofs [19] , but these solutions rely on "heavy" tools and are practically inefficient. Instead, we focus on designing protocols that make black-box use of simpler (and lightweight) primitives such as One-Way Functions (OWFs), and parallel Oblivious-Transfer (OT) or parallel Oblivious Linear function Evaluation (OLE) in the boolean and arithmetic settings (resp.). Relying on OTs/OLEs is, in a sense, necessary since these are special cases of secure computation in their respective settings. Moreover, since our protocols make black-box use of these primitives, they will benefit from future improvements in the costs of OT/OLE implementations, which have been steadily decreasing.

Moreover, to frame a clean theoretical question, we focus on designing modular protocols in which the (relatively) computationally-expensive "cryptographic" component is separated from the rest of the protocol, and abstracted as an ideal functionality. Specifically, the "cryptographic" abstraction we consider in this work is a (constant-round) parallel protocol for computing distributed multiplication. Relying on a general multiplication functionality instead of OT/OLE allows us to simultaneously capture many settings of interest (boolean/arithmetic computations, two/multi-party, honest/dishonest majority) in a unified way. More specifically, we abstract distributed multiplication as an F MULT functionality that is parameterized by a secret sharing scheme S over some field F, takes S-shares of two secrets, and produces S-shares of their product. It is easy to see that one can use a general reduction from OT (resp. OLE) to a random instance F RMULT of F MULT (which generates additive shares of random multiplication triples in the sense of Beaver's triples [3] ) for boolean (resp. arithmetic) computations. In the multi-party setting, one can also realize F MULT using more general protocols based on threshold additively-homomorphic encryption schemes [10] . Table 1 . Asymptotic communication overheads of our results in both the dishonest and honest majority settings for boolean and arithmetic computations. The "best passive" column refers to the passively-secure protocol over which the overhead is computed. The "theorem number" column specifies the theorem which implies the corresponding result. t < n/2 * * Arbitrary Arbitrary -Constant [5] Theorem 6 * Concretely, this constant is 2 for moderately wide circuits. * * We note that though in the honest majority setting guaranteed output delivery is achievable, our protocol only guarantees security with abort.

New protocols in the dishonest majority setting. Our compiler exhibits the most substantial improvements in the dishonest majority setting, yielding the first constant-overhead actively-secure protocol with a dishonest majority over an arbitrary number of parties for boolean circuits. The concrete constants of our compiler are yet unknown since they depend on the concrete efficiency of Algebraic Geometric (AG) secret sharing schemes over constant-size fields [8] . The result is summarized in the following informal theorem; see Theorem 3 for the formal statement.

Any m-party function f over a constant-size field (resp., arbitrary size field) can be securely realized by an O(d)-round protocol in the OT-hybrid (resp., OLE-hybrid) model against an active adversary corrupting an arbitrary number of parties with total communication O(m 2 |C|) + poly(κ, d, m) field elements, where C is a depth-d circuit for f , and κ is a computational security parameter.

For arithmetic computations, we can concretely analyze the constants introduced by our compiler, and show that they can be as small as 2 for moderately wide circuits and sufficiently large fields. This improves over [17] in two aspects. First, their work requires at least 12 invocations of an active implementation of F MULT , while ours requires only two invocation of a passive implementation. This allows us to instantiate our compiler with passive implementations of F MULT based on threshold additively homomorphic encryption schemes [6, 10] . Second, their result is only useful for computations over sufficiently large fields (where the statistical error O (|C| / |F|) is small), whereas our result applies to fields of arbitrary size.

Building on the recent result of Hazay et al. [25] , we can extend our compiler to rely on a weaker-than-passive (e.g., imperfect or leaky) implementation of F MULT . Consequently F MULT can be instantiated with lattice-based protocols with "aggressive" (weaker) parameters, yielding actively-secure compiled protocols whose communication cost almost matches that of the best passive protocols, namely, essentially achieving active security at the cost of passive! Additionally, we achieve an interesting corollary in the constant-round regime for boolean computations. By viewing distributed garbling [4] as an arithmetic functionality over GF(2 κ ), we can instantiate our compiler for arithmetic circuits to achieve constant-overhead over that passive variant of [4] instantiated with F MULT over GF(2 κ ). See the full version [28] for details.

We believe our protocols can also be made to tolerate adaptive corruptions by instantiating the underlying cryptographic primitives (namely, F MULT and F COM ) with their adaptively-secure counterparts, and leave this to future work.

New protocols in the honest majority setting. In the honest majority regime for t < n/2, our compiler gives an actively-secure protocol for boolean circuits with constant overhead over a variant of passive-BGW [5] that is instantiated using AG secret sharing schemes. This result improves over the recent protocol by Chida et al. [9] , which only achieves constant overhead for large fields (introducing an extra statistical security parameter s for small fields with an overhead of s/ log 2 (|F|)), and over Ishai et al. [31] who achieve constant-overhead for arbitrary fields, but only for few parties. We note that [11] achieves constantrate secure protocols, but only for suboptimal corruption thresholds. For boolean computation with an arbitrary number of parties and optimal threshold, the best protocols are due to Genkin et al. [18] and achieve a poly log(|C| , s) overhead, where |C| is the circuit size.

We give a brief overview of recent efficient protocols, summarized in Table 2 .

The state-of-the-art: Boolean multi-party setting. For boolean circuits, secure protocol against a dishonest majority with an (asymptotic) constant overhead over passively-secure protocols, was achieved for constant number of parties by Ishai, Prabhakaran and Sahai [32] (referred to as the "IPS-compiler"). Their protocol operates in the OT-hybrid model, achieving constant overhead over passive-GMW. It also achieves constant rate, namely the communication complexity of evaluating a circuit C is O (|C|) + poly (log |C| , d, m, κ), where d, m, κ are the depth of C, the number of parties, and a security parameter, respectively. For an arbitrary number of parties, the protocol of Genkin et al. [18] obtains poly log (|C| , s) overhead over passive-GMW, where s is a statistical security parameter. This result is obtained by converting a boolean circuit C into a functionally-equivalent randomized circuit C that is immune against so called "additive attacks", and evaluating C using the semi-honest protocol of [19] . (This technique was originally introduced by [17] , but was essentially only useful over large fields, see discussion below.)

The state-of-the-art: arithmetic multi-party setting. In the arithmetic setting in which the computation is performed over an arbitrary field F, Genkin et al. [17] designed MPC protocols in the OLE-hybrid model, with a statistical error of O(|C|/F), and constant communication overhead compared to an algebraic variant of passive-GMW [19] , for sufficiently large fields F. As described above, their result is obtained by converting a circuit C over some field F into its additively-secure variant C , and evaluating C using passive-GMW and actively secure implementation of OLE. In practice, the constant in the communication overhead of their protocol is 12, and moreover their protocol is only useful for circuits over large fields (for which O(|C|/F) is sufficiently small). For arbitrary fields, the work of Döttling et al. [15] give an actively secure protocol where the overhead is 22 invocations of an actively secure implementation of F MULT per multiplication gate of the circuit. A practical implementation for arbitrary number of parties was given in [34] based on "tailor-made" zero-knowledge proofs to achieve active security.

We note that in the honest majority setting, the recent work by Chida et al. [9] presents a new actively-secure protocol for arithmetic circuits that obtains overhead 2 over passive protocols for sufficiently large fields. Similar to our protocol, their protocol is in the F MULT -hybrid model, where F MULT can be instantiated with any passively-secure protocol that further guarantees a notion of "security up to additive attacks" in the presence of active adversaries. It is unclear whether their paradigm extends to the dishonest majority setting, since their model of additive attacks is weaker than the standard one formulated in [17] , where in all natural candidates an active attack translates into an additive attack in the latter (stronger) attack model, and is therefore not protected against by the framework of [9] .

In an orthogonal vein, we note that Applebaum et al. [2] designed the first (variant of) passively-secure OLE based on LPN-style assumptions, implying secure arithmetic computation with asymptotic constant computational overhead over an insecure evaluation of the circuit.

The state-of-the-art: two-party setting. In the boolean setting, the protocols of [32] and [26] achieve (asymptotic) constant communication overhead over the passive protocols of [19] and [50] , respectively. The latter has the added benefit of matching the number of OT calls in [50] , which (unlike [19] ) is sublinear in the circuit size. Practical implementations of [32] have been studied in [36] , who identified bottlenecks in obtaining concretely-efficient protocols based on the IPS protocol due to the implementation of the so-called "watchlist channels". In the arithmetic setting, a recent work by Hazay et al. [25] instantiated the framework of [32] with a concretely-efficient honest majority protocol, obtaining small multiplicative overheads (between 2-8) compared to the passive protocol of [19] . Table 2 . Asymptotic and concrete communication overheads of state-of-the-art 2PC and MPC protocols in the dishonest majority setting. The overhead is measured as the number of calls to the underlying (passively or actively secure) OT or OLE functionality, compared to the number of calls made by the passive-GMW to the corresponding (passively secure) functionality (OT or OLE). The concrete overhead column is specified only when the overhead is constant, and holds over sufficiently large fields. s denotes a statistical security parameter, and C is the circuit being evaluated. 

We first recall the so-called "IPS framework" of Ishai, Prabhakaran and Sahai [32] , that constructs actively-secure m-party protocols for a function f using the following two weaker ingredients as a black-box: (1) an actively-secure honest-majority protocol (the "outer protocol") for f with m clients and n servers, tolerating active corruption of a minority t < n/2 of the servers and an arbitrary number of clients; and (2) a passively secure m-party protocol (the "inner protocol") for a "simpler" functionality, tolerating an arbitrary number of corruptions. Using appropriate instantiations of the outer and inner protocols, this framework yields a constant-overhead (in fact, constant-rate) actively-secure protocol for boolean functionalities in the dishonest majority setting with a constant number of parties m. However, it does not obtain constant overhead for a superconstant m, as we now explain.

To watch or not to watch? The high-level idea of the IPS compiler it to have the m parties "virtually" execute the outer protocol by emulating its n servers. Specifically, the parties first obtain (through some joint computation) secret shares of the initial server states, then use the inner protocol on the shared states to generate (secret shares) of the outputs of the "next message" functions of each server. Since the outer protocol is only secure when a majority of the servers are honest, the parties must insure that most servers were correctly emulated, for which it suffices to verify that the parties behave honestly in sufficiently many of the inner protocol executions. The IPS compiler introduces a novel "watchlist" mechanism in which parties "watch" each other to enforce such honest behaviour. More precisely, every party P i picks a random subset of t servers for which it learns the entire internal state throughout the computation. Consequently, P i can check that all parties honest emulated the t servers, and abort if some party misbehaves. The identity of servers watched by honest parties remains hidden from the adversary, thus even a single honest party forces the adversary to honestly emulate most (specifically, a majority) of the servers. In terms of parameters, obtaining a 2 −Ω(s) soundness error for a statistical security parameter s requires t, n = Ω(s). Since each corrupted party can choose an arbitrary subset of t watched servers, and there could be m − 1 corrupted parties, privacy is only preserved when (m−1)t < n/2. Since achieving constant-overhead requires n = O(s), this is only possible for m = O(1).

To solve this problem, our first idea is to have a single random subset of t servers which are simultaneously watched by all parties. Of course, now that the identity of the watched servers is known to all parties, it cannot be revealed before the computation has been completed. Instead, the subset is chosen using joint coin-tossing after the circuit has been evaluated, but before the output is reconstructed from the output shares. Correctness is preserved similarly to the original IPS compiler, but checking honest behavior after-the-fact might violate privacy. Indeed, unlike the IPS compiler we can no longer "catch" the adversary as soon as it deviates from the protocol, which raises two privacy concerns. First, by actively deviating from the protocol, the adversary can potentially violate the inner protocol privacy, and learn intermediate values during the circuit evaluation. Second, the adversary can potentially violate the privacy of the outer protocol, by "corrupting" a majority of the servers in the outer protocol (i.e., by not emulating them correctly). We note that even if the inner protocol has the stronger guarantee of remaining private even against active adversaries, this does not resolve the second issue because as long as the inner protocol is not actively-secure, active corruptions in it might violate correctness, which corresponds to corrupting servers in the outer protocol. Thus, an active adversary might still violate privacy in the outer protocol by violating correctness in the inner protocol (thus, in effect, corrupting possibly a majority of the servers).

Our approach. Due to these issues, we take a step back, and (instead of extending the IPS framework) focus on designing a new compiler that amplifies the security of a passively-secure inner protocol via a tailor-made outer protocol. Since we use different instantiates of the inner protocol, we model it more generally, assuming the parties have oracle access to an ideal multiplication functionality F MULT that works over some agreed-upon secret sharing scheme S. We note that in our compiler, we will not refer to "servers" (or an "outer" protocol), but rather think of these as "copies" of the circuit.

The combined protocol. To highlight the main components of our framework, we describe a basic MPC variant that will loosely rely on the passive BGW [5] protocol. Though this does not yield our asymptotic results, it will serve as a good starting point, which we build on to obtain our final framework (as described towards the end of the section).

At the onset of the computation each party P i secret shares its input x i using Shamir's secret sharing scheme with privacy parameter t, to obtain the shares X 1 , . . . , X n (as in the passive-BGW protocol). Then, P i generates additive shares x l j of each Shamir share X l , and sends x l j l∈ [n] to P j . The protocol will evaluates the circuit gate-by-gate as in passive-BGW, where addition gates are locally computed. We will preserve the invariant that when parties evaluate a gate G, they collectively hold additive shares of Shamir shares of the values of its input wires. That is, if G's inputs are values a, b which in the passive-BGW protocol have Shamir shares A 1 , . . . , A n , B 1 , . . . , B n (respectively), then for every l ∈ [n], party P i holds values a l i , b l i such that i a l i = A l and i b l i = B l . In passive-BGW, multiplications are performed by having each party locally multiply its Shamir shares A l , B l , followed by all parties jointly running a degreereduction sub-protocol on these products. However, in our modified protocol parties can no longer locally compute the products A l · B l , because no party knows A l , B l (parties only know additive shares of these values). To solve this issue, we use an ideal distributed-multiplication functionality F MULT which takes as input additive shares of two values x, y, and outputs a (fresh) additive sharing of their product x·y. (We discuss F MULT instantiations below.) This allows parties to learn additive shares of each product A l · B l .

Once (additive shares of) the products A l · B l have been computed, degree reduction should be performed. In the classical passive-BGW protocol, degree reduction requires expensive communication, which is improved by protocols such as [13] . We use a new approach that significantly reduces the communication complexity, leveraging the fact that degree-reduction is a linear operation over the Shamir shares.

Local degree-reduction. Each party locally performs degree reduction over its additive shares of the Shamir shares. Across all parties, the additive shares obtained as a result of this procedure constitute a valid Shamir sharing of the "right" value, due to the linearity properties of Shamir's secret sharing scheme. Intuitively, the second secret-sharing layer allows parties to locally perform degree reduction, because it gives each party a global "view" of the protocol execution, as an additive share of the global view of the protocol execution.

Once the computation is completed in all copies, we ensure it was performed correctly by incorporating a "correctness-enforcing" mechanism into the protocol. Specifically, before opening the output shares obtained at the outputs of all copies, we first run some correctness tests which will check that (with high probability) all parties honestly executed the computation. The output shares are revealed (and the output is reconstructed from these shares) only if all correctness tests pass.

To explain our correctness tests, we first analyze possible malicious strategies of corrupted parties. Roughly, a corrupted party can deviate from the protocol in one of four ways. First, it can incorrectly share its input (i.e., the "sharing" isn't of the right degree t). Second, it can incorrectly perform the degree-reduction procedure, by generating a fresh sharing that either isn't of the right degree (i.e., t), or doesn't share the right value (i.e., the value shared before degree reduction). Third, when evaluating a multiplication gate (i.e., computing the product of Shamir shares as described above), it can use different values than the ones provided by F MULT . Fourth, it can incorrectly perform the local linear computations.

To handle such deviations from the protocol, we introduce three tests. The first is a degree test, which checks that the secrets sharings used by all parties, either to share their inputs or as input to multiplication gates, have the right degree. The second is an equality test, which checks that the secret sharings before and after degree reduction share the same value. The degree and equality tests jointly guarantee that with overwhelming probability, the input sharings are valid, and the degree reduction procedure was executed correctly (in most copies). Similar degree and equality tests were used in [1, 25] to check similar conditions. The last test is a consistency test, which verifies that (with high probability) parties correctly performed the local computations in (most) copies of the circuit. This checks that the values used by the parties when evaluating a multiplication gate are consistent with the values they obtained from F MULT , that the local linear operations were performed correctly, and will also guarantee the soundness of the degree and equality tests. For this test, a random subset of copies is chosen, each party reveals its local view of the computation in those copies, and all parties check that the views are consistent with each other. Similar tests were used in the context of MPC-in-the-head [30, 32] .

We note that this high-level overview omits important details (see Sect. 4). For example, the order in which parties commit and reveal the correctness tests' values is crucial to preserving privacy even when the computations in most copies are incorrect. Using this combination of correctness tests, and proving the security of this approach is novel to our work, and requires subtle analysis.

Achieving constant communication overhead. Our basic MPC protocol does not achieve constant communication overhead since it increases the communication complexity of the underlying BGW protocol [5] by O(s), where s is a security parameter. We reduce this overhead to constant by replacing [5] with the protocol of Franklin and Yung [16] that uses packed secret sharing.

Loosely speaking, packed secret sharing extends Shamir's secret sharing, allowing a block of B secrets to be shared within a single set of shares. To exploit the advantages of packed secret sharing, we will assume the circuit is arranged in layers that contain only one type (addition/multiplication) of gates, where each phase of the protocol evaluates the gates in one layer.

Using packed secret sharing introduces two main differences from the basic protocol. First, before evaluating a specific layer the parties need to rearrange (repack) the shared secrets corresponding to the input wire values of that layer, to align the packing in blocks with the order of gates within the layer. Then, the layer can be evaluated similarly to the basic protocol (where additions are computed locally, and multiplications involve a call to F MULT , followed by a local degree-reduction step). The second difference from the basic protocol is that to insure correctness we must now check that the parties correctly rearranged the shared secrets between layers. This is checked through an additional "permutation test" [1, 11] . See Sect. 5 for further details.

This protocol reduces the amortized per-gate communication overhead to constant, because in effect the packed secret sharing allows us to evaluate many gates in one "shot". In particular, the wider the circuit to be evaluated, the larger the gains from employing packed secret sharing.

Instantiating the multiplication functionality F MULT . We instantiate F MULT through a reduction to a simpler functionality F RMULT which generates (unauthenticated) random triples. All prior protocols that relied on this abstraction (apart from [32] ), used actively-secure multiplication protocols to instantiate F MULT . Interestingly, we can greatly weaken the security of the multiplication protocol, requiring only a passively-secure instantiation, together with a coin tossing protocol to ensure correctly-sampled randomness. Moreover, our protocol can benefit from a preprocessing stage in an offline/online setting, where the triples are generated in the offline phase, and used in the online phase. The consistency test (described for our basic MPC protocol) will ensure, at the cost of a small overhead, that the triples were correctly generated with respect to the tossed coins. We note that unlike prior works, our security analysis can tolerate a small number of ill-formed triples without violating secrecy.

Conceptually, our consistency test can be viewed as a combination of the cut-and-choose approach [37] and the watchlist mechanism of [32] . Indeed, on the one hand we maintain multiple copies of the computed circuit, yet unlike the cut-and-choose technique the checked copies are not discarded, but rather used in the remainder of the computation to reconstruct the outputs. On the other hand, the purpose of our consistency test is similar to the watchlist channels, which add privacy and correctness to passively-secure protocols. The main difference between our tests and the watchlists of [32] is that in IPS these channels are used to constantly enforce correct behaviour throughout the protocol execution (and consequently also cause a high overhead), whereas we perform a single consistency test after the protocol execution has (essentially) ended, right before the output is reconstructed. These correctness enforcement mechanisms are known to have limitations to achieving scalable MPC. Specifically, the asymptotic limit of cut-and-choose is O(s/ log |C|) [49] , whereas the watchlists mechanism requires O(s · n) virtual servers for the outer protocol [36] . In both cases, the communication grows with some statistical parameter, and is hence neither constant-overhead nor scalable.

In this section we provide necessary preliminaries. Further preliminaries are deferred to the full version [28] .

Basic notations. We denote a security parameter by κ. We say that a function μ : N → N is negligible if for every positive polynomial p(·) and all sufficiently large κ's it holds that μ(κ) < 1 p(κ) . We use the abbreviation PPT to denote probabilistic polynomial-time and denote by [n] the set of elements {1, . . . , n} for some n ∈ N. We assume functions to be represented by an arithmetic circuit C (with addition and multiplication gates of fan-in 2), and denote the size of C by |C|. By default we define the size of the circuit to include the total number of gates including input gates. For a random variable X, we use Supp(X) to denote the set of values which X takes with positive probability.

An arithmetic circuit defined over a finite field F is a directed acyclic graph, where nodes (or gates) are labelled either as input gates, output gates or computation gates. Input gates have no incoming edges (or wires), while output gates have a single incoming wire and no outgoing wires. Computation gates are labelled with a field operations (either addition or multiplication), 1 and have exactly two incoming wires, which we denote as the left and right wire. A circuit with i input gates and o output gates over a field F represents a function f : F i → F o whose value on input x = (x 1 , . . . , x i ) can be computed by assigning a value to each wire of the circuit. Note that this abstraction captures boolean circuits as well, by setting F = GF (2) . In this work, we will exploit an additional structure of the circuit. Specifically, the gates of an arithmetic circuit can be partitioned into ordered layers L 1 , . . . , L d , such that i) a layer only consists of gates of the same type (i.e., addition, multiplication, input or output gates belonging to the same party), and ii) the incoming wires of all gates of layer i originate from gates in layers 0 to i − 1.

A core building block in our protocols is a multiplication functionality F MULT shown in Fig. 1 , that takes additive shares of two secrets over some field F and produces additive shares of their product. In fact, we will reduce F MULT to a random instance F RMULT , shown in Fig. 2 , where all shares are chosen uniformly at random from F. The reduction, due to Beaver [3] , is as follows. Denote by [a] the additive sharing of some value a ∈ F, namely, the tuple (a 1 , . . . , a m ). 

A secret-sharing scheme allows a dealer to distribute a secret among n parties, where each party receives a share (or piece) of the secret during a sharing phase. In its simplest form, the goal of (threshold) secret-sharing is to allow only subsets of players of size at least t + 1 to reconstruct the secret. More formally a t + 1out-of-n secret sharing scheme comes with a sharing algorithm that on input a secret s outputs n shares s 1 , . . . , s n and a reconstruction algorithm that takes as input ((s i ) i∈S , S) where |S| > t and outputs either a secret s or ⊥. In this work, we will use Shamir's secret sharing scheme [45] with secrets in F = GF(2 κ ). We present the sharing and reconstruction algorithms below:

Sharing algorithm: For any input s ∈ F, pick a random polynomial p(·) of degree t in the polynomial-field F[x] with the condition that p(0) = s and output p(1), . . . , p(n). Reconstruction algorithm: For any input (s i ) i∈S where none of the s i are ⊥ and |S| > t, compute a polynomial g(x) such that g(i) = s i for every i ∈ S. This is possible using Lagrange interpolation where g is given by

Finally the reconstruction algorithm outputs g(0).

Packed secret-sharing. The concept of packed secret-sharing was introduced by Franking and Yung in [16] in order to reduce the communication complexity of secure multi-party protocols, and is an extension of standard secret-sharing.

In particular, the authors considered Shamir's secret sharing with the difference that the number of secrets s 1 , . . . , s is now instead of a single secret, where the secrets are represented as the evaluations of a polynomial p(·) at distinct points. To ensure privacy in case of t colluding corrupted parties, p(·) must have degree at least t + . Packed secret sharing inherits the linearity property of Shamir's secret sharing, with the added benefit that it supports batch (blockwise) multiplications. This was used to design secure computation protocols with an honest majority and constant amortized overhead [11] . For this reason, we use this tool in our honest majority MPC protocol embedded within our dishonest majority protocol from Sect. 4, leveraging its advantages to improve the overhead of the former protocol.

A crucial ingredient in our construction is the use of Reed-Solomon codes as a packed secret sharing scheme [16] (as defined in Sect. 3.3) . In what follows, we provide our coding notations and related definitions.

Coding notation. For a code C ⊆ Σ n and vector v ∈ Σ n , we denote by d(v, C) the minimal distance of v from C, namely the number of positions in which v differs from the closest codeword in C, and by Δ(v, C) the set of positions in which v differs from such a closest codeword (in case of a tie, take the lexicographically first closest codeword). For any k ≤ d(v, C), we say that v is k-close to C, and for every k > d(v, C), we say that v is k-far from C. We further denote by d(V, C) the minimal distance between a vector set V and a code C, namely d(V, C) = min v∈V {d(v, C)}.

For positive integers n, k, finite field F, and a vector η = (η 1 , . . . , η n ) ∈ F n of distinct field elements, the code RS F,n,k,η is the [n, k, n − k + 1]-linear code 2 over F that consists of all n-tuples (p(η 1 ), . . . , p(η n )) where p is a polynomial of degree < k over F.

Let L = RS F,n,k,η be an RS code and ζ = (ζ 1 , . . . , ζ w ) be a sequence of distinct elements of F for w ≤ k. For u ∈ L we define the message Decode ζ (u) to be (p u (ζ 1 ), . . . , p u (ζ w )), where p u is the polynomial

Moreover, we recall that Decode ζ (·) is a linear operation, i.e. for any a, b ∈ F n (even if a, b are not in L), Decode ζ (a + b) = Decode ζ (a) + Decode ζ (b). It will be convenient to view m-tuples of codewords in L as codewords in an interleaved code L m . We formally define this notion below. 

In this section we describe a simple variant of our MPC protocol, which we build on in Sect. 5 to achieve constant overhead.

Our starting point is a passively-secure variant of the BGW protocol [5] , which we amplify to the actively-secure dishonest-majority setting. Amplifying the security of this protocol requires facing three challenges: (1) high overhead due to the degree-reduction sub-protocol; (2) security holds only with a dishonest minority; and (3) security holds only against passive corruptions.

Our strategy towards addressing the first issue is to have parties locally perform the degree-reduction procedure which the degree-reduction sub-protocol implements, thus (almost) eliminating the interaction it requires. This is achieved by using a second layer of secret-sharing.

Concretely, our MPC protocol with m parties relies on two layers of secret sharing schemes: (1) first layer sharing: Reed-Solomon codes (which can be thought of as Shamir's secret sharing), denoted by L-encoding, where L = RS F,n,k,η (cf. Sect. 3.4); and (2) second layer sharing: additive secret sharing. 3 Throughout the execution, the parties hold additive shares of the L-encodings of the wires of the evaluated circuit C. We note that using this two-layer secret sharing decouples the number of parties m from the length of the encoding n, since (unlike passive-BGW) parties no longer hold the symbols of the L-encodings. In fact, it will be useful to have m = n. Intuitively, this can be though of as having the parties emulate n copies of C, where the wires of the l'th copy carry the l'th symbol in the L-encodings of the wire values of C, and these symbols are additively shared among the parties. The execution maintains the invariant that when evaluating the gates in layer L, the parties hold for each copy l additive shares of the l'th symbols in the L-encodings of the outputs of previous layers.

Our protocol is described in the F RMULT -hybrid model (cf. Sect. 3.2) which generates m additive shares of random triples, and is used to execute multiplications. In more detail, the parties evaluate the n copies of C layer by layer, locally performing additions, substractions and multiplications by a constant (this is possible due to the linear nature of our secret sharing schemes), whereas multiplication gates require communication.

Roughly, a multiplication gate G in the l'th copy of C is evaluated as follows. The parties hold additive shares of the l'th symbols A l , B l at the inputs of G, and use F RMULT (and a reduction from F MULT to F RMULT , described in Sect. 3.2) to obtain additive shares of the product A l B l . Across all copies, these products form anL-encoding of the output wire of G, whereL = RS F,n,2k,η . To obtain a fresh L-encoding of the output wire, each party interprets its additive shares of theL-encoding (across all copies) as an encoding in RS F,n,n,η , decodes it, and then generates a fresh L-encoding of this decoded value. The additive shares obtained through this procedure reconstruct to the correct value because degree reduction is a linear operation.

Employing a second secret-sharing layer solves the second challenge (that passive-BGW is only private in the honest majority setting) since a subset of parties learn only a strict subset of additive shares. The third challenge (passive-BGW is only secure against passive corruptions) is handled by incorporating correctness-enforcing tests into the protocol, as described in Sect. 2.

Our detailed protocol is given in Figs. 3, 4 and 5. We next state the following theorem; its proof appears in the full version [28] . 

where k > δ + 4e,n > 2k + 4e and e ≤ (n − k + 1)/3.

The simulation follows by having the simulator Sim execute the protocol with the adversary, emulating the ideal functionalities for it, and emulating the honest parties on dummy 0-inputs. Before executing the output decommitment step, Sim performs several checks regarding the actions of the corrupted parties. Specifically, the simulator determines the set E of copies for which, if they were chosen during the consistency test, the test would fail. It also identifies the set E of copies in which the F RMULT values the corrupted parties committed to are inconsistent with the ones Sim provided to them. Then, it verifies that |E| ≤ e, |E| ≤ 3e, and that there existÛ,X i , i ∈ [m], andẑ which are valid encodings in the appropriate (interleaved) codes that agree with

, and i∈[m] z i (respectively) except for the copies in E. It also verifies that there exists aV in the interleaved code overL that agrees with i∈[m] V i except for the copies in E ∪ E . We note that Sim can perform these checks because it emulated the internal ideal functionalities for the adversary, whereas the honest parties in the protocol cannot perform these checks. If all checks pass then Sim can extract effective inputs for the corrupted parties, and use them to obtain the output from the trusted party. Finally, Sim "corrects" the output shares of the honest parties to share the correct outputs.

Next, we highlight some of the challenges we face when proving indistinguishability of the simulated and real views. Recall that unlike [32] we run a single consistency test, right before output reconstruction. Thus, we essentially Protocol Φ.

-Inputs. Pi's input is xi for all i ∈ [m]. The parties share a description of an arithmetic circuit C with fan-in 2 which contains h multiplication gates and implements functionality .

-Initialization.

The parties invoke the RMULT functionality hn times. Each invocation yields additive shares r 1 1 , . . . , r 1 m , r 2 1 , . . . , r 2 m and r 3 1 , . . . , r 3 m , with party Pi holding (r 1 i , r 2 i , r 3 i ), such that r j = m i=1 r j i for j ∈ {1, 2, 3}, and r 3 = r 1 · r 2 . Each party Pi generates a random L-encoding γi = (γ 1 i , . . . , γ n i ) of a random value, a random L encoding νi = (ν 1 i , . . . , ν n i ) of 0, and a randomL encoding γi = ( γ 1 i , . . . , γ n i ) of 0. Pi samples a tuple (ψ 1 i , . . . , ψ m i ) such that ψ j i ∈ F n and m j=1 ψ j i is the all-0 vector. Pi sends ψ j i to party Pj. These "blinding" encodings are used in the degree and equality tests of Figure 4 . Then, for every copy l ∈ [n], Pi commits using COM to:

• The triples obtained from the (l − 1) · h + 1, . . . , hl'th invocations of the RMULT oracle. Pi performs the gate operation by applying it locally on the additive shares maintained as the inputs of that gate in the l'th copy.

To compute a multiplication gate, the parties invoke the following multiplication protocol, where each party uses as inputs its l'th-copy shares of the inputs of G.

• For every i, let a l i , b l i denote the shares of the inputs of G which Pi holds in the l'th copy of C. Then the parties compute additive shares

where Pi receivesc l i , via the reduction from MULT to RMULT (described in Section 3.2), using the first unused triple obtained from RMULT in the (next unused portion of the) randomness generation phase above. Correctness tests. The following tests are performed to verify that the parties correctly evaluated the n copies of C (including the degree reduction step executed after each multiplication gate).

-Commit to degree test. This test checks that the input encodings and the shares produced by all parties at the end of every degree reduction step are valid L-encodings. This is done by checking that a random linear combination of the sum of all these shares is a valid encoding in L = RS F,n,k,η . More precisely, the parties first obtain from COIN random vectors r ∈ F h , r ∈ F m , and r ∈ F (recall that h is the number of multiplication gates in C, and m is the number of inputs -one from each party). Next, each party Pi constructs the matrix Ui ∈ F h×n that contains the L-encodings obtained after the degree reduction step of all multiplication gates (arranged in some arbitrary order, agreed upon by all parties). Then, Pi locally computes

where X i is the L-encoding of Pi's input xi committed at the input sharing step, νi is the L-encoding of 0 committed to by Pi at the initialization step and γi is the blinding L-encoding committed to at the initialization step. Pi then commits to each element of qi, and each column of Ui, using COM .

-Commit to equality test. This test checks that the degree reduction step was performed correctly. This is done by checking that a random linear combination of the sum of differences of shares before and after the degree reduction step (performed as part of evaluating a multiplication gate) is a valid encoding of 0 inL = RS F,n,2k,η . Specifically, the parties obtain from COIN a random vector α = (α1, . . . , α h ) ∈ F h and random element β ∈ F. Pi sets Vi to contain the additive shares which Pi obtains from the MULT to RMULT reduction computed during the evaluation of multiplication gates. Next, Pi locally computes:q

γi is theL-encoding of 0 from the initialization step. Finally, Pi commits to each element ofqi using COM . have one "shot" to catch the adversary, causing the test to be more involved. Another challenge is that parties are only committed to small portions of the execution, whereas in [32] parties commit to all their messages via the watchlists channels. Consequently, Sim cannot verify correct behavior directly by checking the messages, and instead we need to show that the messages can be extracted from the partial information which parties commit to. Fortunately, we show that correctness can be defined based on the F RMULT inputs, and the transcript of the reduction from F MULT to F RMULT . Finally, correctness is guaranteed by the combination of local and global checks in our protocol. Specifically, the consistency -Consistency test. This test checks that the parties correctly executed the local computations in each copy. P1, . . . , Pm obtain from COIN a random subset Γ ⊂ [n] of size δ. For every l ∈ Γ , each Pi opens its entire view of the execution of the l'th copy of C. Specifically, Pi decommits X l i , and the randomness (including all components of the commitments generated in the initialization step) it used in the execution of the l'th copy. It also opens the commitments to the degree and equality tests, and the additive shares of the final outputs of the l'th copy. Then, Pi checks (as described next) that all local computations in the copies in Γ were performed correctly, aborting if an inconsistency is detected. To check the l'th copy, Pi first checks that for every j ∈ [m], j ∈[m] ψ j ,l j = 0. Then, it obtains the l'th column of Uj and zj from the decommitments of Pj, and uses the decommitments to RMULT values to determine the multiplication triples used by all parties for the l'th copy. Using these triples, Pi determines the inputs and outputs each party used in each multiplication gate of the l'th copy. Having determined the outputs of multiplication gates, Pj can reconstruct the l'th column of Vj. Moreover, since the final output is a linear combination of outputs of multiplication gates and parties' inputs, j w l j can be obtained by computing this linear combination over the corresponding rows in j Uj's and the Xj's. Since addition gates are evaluated locally, correct execution of addition gates can be verified by checking that the inputs to all multiplication gates were computed correctly. Recall that an input to a multiplication gate is a linear combination of outputs of previous multiplication gates and parties' inputs. Thus, correctness can be checked by verifying that the sum of additive shares used as inputs to multiplication gates by all parties (as inferred from the RMULT triples, and the transcript), and the linear combination of the corresponding rows in j Uj and the Xj's, are equal. Parties also verify that the reduction from MULT to RMULT was computed correctly in the l'th copy, and that z l i = w l i + ν l i for every i. -Degree test check. The parties decommit the degree test commitments for all remaining copies l / ∈ Γ , namely each Pi opens the commitment to the value qi computed in Figure 4 . (Note that the parties do not decommit the remaining columns of Ui.) Each party computes the vector q = (q1 + . . . + qm) and aborts if q is not a valid L-encoding.

-Equality test check. The parties decommit their equality test commitments for all copies l / ∈ Γ , namely each Pi opens the commitment to the valueqi computed in Figure 4 . Each party computesq = (q1 + . . . +qm), and aborts if eitherq ∈L orq does not decode to the value 0. -Output decommitments. If the consistency, degree and equality tests pass correctly, then every party Pi decommits its output commitments for all copies l / ∈ Γ . The parties then locally reconstruct z = i zi, and if it is an L-encoding, decode the output of C from the encoding. test verifies local correctness of the computation within each copy, by inspecting a subset of copies; and the degree and equality tests verify that some global relation holds over all copies (i.e., all additive shares).

In the proof, we show that if all the protocol tests pass then except with negligible probability, all the conditions checked by the simulator before the output reconstruction phase hold, and moreover the output is consistent with the outputs of the honest parties, and the effective outputs that Sim extracts for the corrupted parties. Thus, it suffices to prove indistinguishability of the simulated distribution and a hybrid distribution which is obtained from the real execution by performing Sim's checks, and aborting if they are violated. The difference between the hybrid and simulated distributions is that the honest parties use their real inputs in the former, and 0-inputs in the latter. We prove indistinguishability by a case analysis based on which tests pass. Intuitively, the views revealed during the consistency tests are identically distributed due to the secrecy of Shamir's secret sharing scheme (alternatively, Reed-Solomon codes). The degree test values are indistinguishable because the honest parties' values are valid L-encodings, which are uniformly random due to the masking by the γ i 's. The equality test values are indistinguishable because the sum of honest parties' values are validL-encodings of 0, which are uniformly random subject to this constraint due to the masking by the γ i 's. Since the equality test values are masked by additive shares of 0, the values themselves are identically distributed. Finally, conditioned on all tests passing, the output shares are uniformly random L-encodings whose sum encodes the correct output, due to the masking by the ν i 's.

Assuming the existence of a PRG, parties can commit to their F RMULT triples by committing (during the initialization step) to a PRG seed for each copy (the other initialization-phase commitments are generated as in Fig. 3) . Consequently, the total communication, assuming rate-1 commitments, is: n · m · (κ + (3 + m) · log 2 |F|) rnd/blind com. + m · n · log 2 |F| input commitments + m 2 · n · log 2 |F| input sharing + n · h · CCMULT multiplication + |Γ | · m · (κ + (4 + m) · log 2 |F|) consistency test + 2· m · n · log 2 |F| degree test com. and dec. + 2· m · n · log 2 |F| equality test com. and dec. + 2· n · m · log 2 |F| output com. and dec.

where CC MULT is the communication complexity of the m-party multiplication protocol (implementing F RMULT and the F MULT to F RMULT reduction), and h is the number of multiplication gates in the circuit. (We note that the degree and equality test commitments revealed during the consistency test are counted as part of the degree and equality test terms, resp.) In order to get 2 −Ω(s) soundness, we need to set n = O(s). Assuming s ≤ κ, the overall communication complexity can be bounded by O(s · h · CC MULT ) + poly(m, κ, log 2 |F|). Since h represents the size of the circuit (i.e. number of multiplication gates), the best passive protocol in the F MULT -hybrid can be bounded by O(h) · CC MULT . Therefore, the communication overhead of our basic variant is O(s).

Recall from Sect. 4.1 that F RMULT is the multiplication functionality that outputs three tuples of additive shares a, b, c such that the "inputs" a, b share random values a, b, and the "output" c shares the product a · b. In this section we discuss how to realize this functionality, while identifying the minimal security properties required from it. Our first observation is that we do not need an actively-secure implementation of the F RMULT functionality. In fact, it suffices to consider a protocol that is only "private" against active adversaries, in the sense that throughout the protocol execution, an actively corrupted party cannot violate the privacy of the honest parties' inputs. In particular, the underlying implementation does not have to retain correctness in this case, or provide a mechanism for extracting the adversary's inputs. Extraction in our protocol is achieved by requiring the adversary to commit to its input and randomness used for the F RMULT -functionality. Correctness, on the other hand, is enforced through our consistency test that ensures correctness of the computations in most of the copies, by checking a random subset of δ copies.

When computing a boolean circuit, the pairwise products of the shares can be computed using Oblivious Transfer (OT) [3, 41] . Based on the discussion above, it suffices to use a private OT protocol [24] . Indeed, consistency between the different OT executions will be verified during the consistency test of our protocol, as discussed above. 4 Intuitively, privacy is guaranteed because an OT sender has no output in the execution, and the security/privacy of OT ensures that even if the sender cheats it learns nothing about the receiver's input. Moreover, though an OT receiver can use inconsistent inputs in the OT executions with different honest parties, this can only violate correctness, and not privacy, since the output of each OT execution is an additive share of the cross product (e.g., a i · b j ), which reveals nothing about the other party's share. Similarly, when working over large fields, F RMULT can be realized using private OLE, where private OLE can be defined analogously to private OT, requiring that parties do not infer any additional information (except what can be inferred from their inputs and outputs).

Relaxing to passive implementation of the F RMULT -functionality. We can further weaken the security requirement on the F RMULT implementation, by incorporating the reduction from defensible privacy to passive security. We first informally review the notion of defensible privacy which was introduced by Haitner in [22, 23] ; see [23] for the formal definitions. Let π be a two-party protocol between P 1 and P 2 , and let trans = (q 1 , a 1 , . . . , q , a ) be a transcript of an execution of π when P 1 is controlled by an adversary A, where q i denotes the i'th message from P 1 , and a i denotes the i'th message from P 2 (that is, a i is the response to q i ). Informally, a defence of A relative to trans, which is provided after the protocol execution ends, is a pair (x, r) of input and random tape for P 1 . We say that a defence (x, r) of A relative to trans is good if the transcript generated by running the honest P 1 with input x and random tape r against P 2 's messages a 1 , . . . , a results exactly in trans. Intuitively, a defense (x, r) is good relative to trans if, whenever P i uses (x, r) in an honest execution of π, the messages sent by P i are identical to the messages sent by the adversary in trans. Thus, in essence, a defense serves as a "proof" of honest behavior. Defensible privacy guarantees that when the adversary provides a good defence, then it learns nothing beyond what can be inferred from its input and prescribed output. 5 The security of a passive protocol can be amplified to defensible privacy by adding a coin tossing phase (which, in our case, samples the inputs to F RMULT ), and ensuring that these coins were indeed used in the passive execution. The latter can be checked as part of our consistency test, however to guarantee privacy we cannot postpone this check until the consistency test is performed at the end of the circuit emulation, since by that time the adversary could have already violated privacy by using badly-sampled randomness. Thus, we include in our protocol two consistency tests: the first is the consistency test described in Fig. 4 , and the second checks consistency of F RMULT inputs and the tossed coins, and is executed during the initialization phase. This second consistency test ensures that with overwhelming probability, all but (possibly) a small subset of random triples are correct (namely, the aggregated parties' shares correspond to c = a · b), and consistent with the random coins. This will suffice for our security analysis, because the number of copies will be sufficiently large such that by cheating in a small number (< k) of copies, the adversary learns nothing.

Relaxing further to weaker than passive. Following ideas from [25] , our protocol can, in fact, tolerate an imperfect passive OLE, namely one that has a non-negligible statistical privacy or correctness error. This security feature can be turned into an efficiency advantage. For example, imperfect F RMULT can be implemented more efficiently by aggressively setting the parameters in existing LWE-based OLE constructions, see the full version [28] for details.

In this section we present our main result, namely, an MPC protocol for an arbitrary number of parties that achieves constant communication overhead over the passive GMW protocol.

On a high-level, we will incorporate a variant of the protocol of Frankling and Yung [16] instead of [5] in our basic MPC protocol. Recall that the main overhead in the basic MPC protocol is caused by the n = O(s) copies of the circuit used to perform the computation, where s is a statistical security parameter. Then, similar to [16] we improve the communication overhead, achieving constant overhead, by having all copies evaluate multiple gates in parallel using packed secret sharing. Our protocol will achieve constant-overhead for moderately wide circuits (See Sect. 6 for a more detailed discussion.)

In more detail, given a circuit C, and block-width parameter B, the parties agree on a divisions of the circuit evaluation into layers, where at most B multiplication gates are evaluated in parallel in each layer, and arbitrary linear operations are performed between layers. During the evaluation of the protocol on a specific input, we can associate with each layer of gates G a vector (block) B G O of B values whose i'th position contains the output value assigned to the i'th gate in the layer (or 0 if the block has less than B gates). For each layer (except blocks of input gates), we will associate two additional blocks: a "left" block B G L and "right" block B G R whose i'th position contains the value of the left input wire and right input wire of the i'th gate, respectively. In other words, the value of the i'th gate of a multiplication block can be expressed as

In the protocol, the parties will collectively operate on an efficient (constant-rate) Reed-Solomon encoding (equivalently, packed secret shares) of each block. The protocol parameters include a description of the Reed-Solomon code L = RS F,n,k,η , and a vector of elements ζ = (ζ 1 , . . . , ζ B ) ∈ F B which is used for decoding.

Next, we describe our protocol, simulation and proof by specifying the main differences from the description of the basic protocol from Sect. 4. 

where P i receivesc l i , just as in the basic MPC protocol. Then, each P i locally performs the degree reduction procedure as in the basic MPC protocol, with the difference that P i decodes (c 1 i , . . . ,c n i ) to obtain a block of values which it uses as the additive shares of the outputs of the multiplication gates in the layer. Why repacking is needed. To see why rearranging the values within and between blocks might be necessary, consider a circuit that has a wire connecting the 3'rd value in the 2'nd block in layer 1 with the 5'th value in the 3'rd block in layer 2; or a wire connecting the 4'th value in the 1'st block in layer 1 with the 2'nd value in the 1'st block in layer 2. 6 -Correctness tests. We will employ the equality test as before, modify the degree test to also check the repacked encodings, and add an additional permutation test, as described next. -The modified degree test. As in the basic protocol, the degree test will compute a random linear combination of the tested encodings. These encodings include the blocks X i encoding the parties' inputs (which were committed in the input sharing step), the block of 0s encoded in ν i (which was committed in the initialization step), and the matrix U i which contains Lencodings of the blocks of additive shares that were obtained from the degree reduction step following a multiplication step (U i was committed to during the commit to degree test step). The difference from the degree test of the basic MPC protocol is that the linear combination will now also include an additional matrix U i which contains the L-encodings of the repacked blocks of additive shares that were used as inputs to multiplication gates. (We note that these values are never committed to, but as explained in the proof of Corollary 2 below, can be extracted by the simulator from the transcript of the execution.) More formally, the parties will obtain from F COIN random vectors r, r , r , and a random value r , and party P i will compute A = (r 11 , . . . , r 1B , . . . , r m1 , . . . , r mB ) . Now, let r j (·) be the unique polynomial of degree < B such that r j (ζ Q ) = r jQ for every Q ∈ [B] and j ∈ [m]. Then party P i locally computes q i = (r 1 (ζ i ), . . . , r m (ζ i )) T U i + γ i , where γ i is the blinding encoding from the initialization step (that encode in RS F,n,k+B,η random blocks of values that sum to 0), and U i is the matrix obtained by concatenating the rows of U i and U i from the degree test. Notice that the rows of U i consist of the L-encodings which P i obtained at the output of multiplication layers (after degree reduction), and the L-encodings it used as inputs to multiplication layers (after repacking). Finally, P i commits to each element of q i using F COM . -Consistency test check. In the consistency test, we also check for all l ∈ Γ that the permutation test values of copy l were computed correctly. Specifically, each party checks that for every i ∈ [m], the l'th element of q i is consistent with the l'th element of γ i , the l'th column of U i , and r (the coins obtained from F COIN for the permutation test). -Permutation test check. The parties decommit their permutation test commitments for all copies l / ∈ Γ , namely each P i opens the commitment to the value q i computed above. Each party computes q i = (q 1 + . . . + q m ), and aborts if q = (q 1 , . . . , q n ) ∈ RS F,n,k+B,η or x 1 + · · · + x w = 0 where x = (x 1 , . . . , x w ) = Decode ζ (q ).

The following Theorem follows from Theorem 1 and the discussion above; its proof appears in the full version [28] . 

where k > δ + 4e + B, n > 2k + 4e, and e < (n − k + 1)/3.

Assuming that each layer of the circuit has at least B parallel multiplications, the communication complexity of this variant is given by O(n · h B · CC MULT ) + poly(m, κ, log 2 |F|) since we amortize over B multiplications. By setting n = O(s), the amortized communication overhead of this protocol becomes O(1) per copy. Circuits of an arbitrary structure can be easily handled at a worst-case additional cost of poly(s, d). The statistical error can be improved by repeating the tests. The analysis presented above works for fields of size larger than n, for smaller fields, we can rely on the analysis from [11] .

In this section we consider several different instantiations of the F RMULT functionality, thus obtaining our main results in the different settings as instances of the generic protocol of Sect. 5.

Dishonest majority. Our main result is obtained by replacing the Reed-Solomon codes in our protocol with Algebraic Geometric (AG) secret sharing over fields of constant size [8] , instantiating the F RMULT functionality with pairwise calls to a passively-secure implementation of the F OT functionality, and instantiating commitments using a pseudorandom generator. Formally: We note that the exact constants in the overhead of Theorem 3 depend on the concrete constants of the underlying AG code, which have not been studied before. The communication complexity of our protocol using a bit-OT protocol for the boolean setting asymptotically matches the communication complexity of the best known passively-secure protocol, namely [19] using a passively-secure OT protocol. The best known previous result for active security is due to Genkin et al. [18] who achieve O(m 2 |C| poly log(s)) communication complexity, i.e., a multiplicative factor of poly log(s) over GMW.

Honest majority. To obtain our main result for the honest majority setting, we need to slightly modify our protocol in two ways. First, we will rely on the passive variant of a protocol of Damgård and Nielsen [13] , instantiated with secret-sharing based on AG codes over constant-size finite fields, to instantiate the parallel F RMULT functionality (i.e., to generate the triples in the initialization phase). To achieve this, we replace the additive secret sharing used in our protocol with secret sharing based on AG codes for constant-size fields. We note that the passively-secure honest-majority m-party protocol of [13] can generate T = Ω(m) random triples with total communication complexity O(mT ). Second, we will consider F RMULT and F MULT whose underlying secret sharing scheme is based on the same AG secret sharing scheme. Specifically, parallel F RMULT distributes secret-shares of many triples a, b and c such that a · b = c. Then the F MULT to F RMULT reduction works essentially as in the basic protocol, where the only difference is that the values e, d are reconstructed using the reconstruction procedure of the AG secret sharing scheme. Consequently, we obtain the following theorem. Theorem 4. Let κ, s denote computational and statistical security parameters (resp.), m denote the number of parties, and F be a constant-size field. Then there exists a protocol compiler that, given a pseudorandom generator G with seed length κ, s, and a description of an m-party functionality expressed as a depth-d circuit C with constant fan-in, outputs a UC-secure O(d)-round m-party protocol realizing f with O(m|C|)+poly(m, κ, d) bits total communication complexity, and security against a static adversary corrupting a minority of parties.

We remark that this improves over the result of Chida et al. [9] that achieves O(s) overhead for binary fields, and generalizes the result of Ishai et al. [31] that achieves the same result, but only for a constant number of parties. We remark that the latter protocol additionally achieve constant-rate, while our protocol only achieves constant-overhead.

Dishonest majority. To obtain our result for fields of arbitrary size, we realize the F RMULT functionality using a passively-secure OLE protocol. For fields of size ≤ s we rely on AG sharing, whereas for fields of size Ω(s) we use Reed-Solomon codes. Thus, we can re-derive a result of Genkin et al. [17] (Theorem 5.7 in the full version), who construct an actively-secure m-party protocol for arbitrary functionalities (represented by an arithmetic circuit C), in the dishonest majority setting, using O(m 2 |C|) calls to an OLE oracle. More precisely, we have the following theorem: Theorem 5. Let κ, s denote computational and statistical security parameters (resp.), m denote the number of parties, and F be a field. Then there exists a protocol compiler that, given a pseudorandom generator G with seed length κ, s, a constant-round implementation of the F OLE functionality over F with total communication complexity CC OLE , and a description of an m-party functionality expressed as a depth-d arithmetic circuit C over F with constant fan-in, outputs a UC-secure O(d)-round m-party protocol realizing f with communication complexity O(m 2 |C| CC OLE ) + poly(m, κ, d) field elements, with security against an active adversary corrupting an arbitrary number of parties.

This result asymptotically matches the communication complexity of the best known passively-secure protocol [19] using a passively-secure OLE protocol. Furthermore, for sufficiently wide circuits, we can show that the overhead of our protocols is 2. We present the concrete parameters in the full version [28] .

Honest majority. Just as in Sect. 6.1, we can obtain constant overhead over the best passively-secure protocol in the honest majority setting: Theorem 6. Let κ, s denote computational and statistical security parameters (resp.), m denote the number of parties, and F be a field. Then there exists a protocol compiler that, given a pseudorandom generator G with seed length κ, s, and a description of an m-party functionality expressed as a depth-d arithmetic circuit C over F with constant fan-in, outputs a UC-secure O(d)-round m-party protocol realizing f with total communication complexity O(m|C|)+poly(m, κ, d) bits, where security holds against a static adversary corrupting a minority of parties.

Applying the analysis of concrete parameters (see above and the full version [28] ) we re-derive the result of Chida et al. [9] who show an overhead-2 actively-secure honest-majority protocol. Their result applies to arbitrary circuits over sufficiently large fields, whereas ours achieves overhead of 2 for sufficiently wide circuits.

Ligero: lightweight sublinear arguments without a trusted setup

Secure arithmetic computation with constant computational overhead

Efficient multiparty protocols using circuit randomization

The round complexity of secure protocols (extended abstract)

Completeness theorems for noncryptographic fault-tolerant distributed computation (extended abstract)

Semi-homomorphic encryption and multiparty computation

Multiparty unconditionally secure protocols (abstract)

Algebraic geometric secret sharing schemes and secure multi-party computations over small fields

Fast large-scale honest-majority MPC for malicious adversaries

Multiparty computation from threshold homomorphic encryption

Scalable secure multiparty computation

Practical covertly secure MPC for dishonest majority -or: breaking the SPDZ limits

Scalable and unconditionally secure multiparty computation

Multiparty computation from somewhat homomorphic encryption

TinyOLE: efficient actively secure two-party computation from oblivious linear function evaluation

Communication complexity of secure computation (extended abstract)

Circuits resilient to additive attacks with applications to secure computation

Binary AMD circuits from secure multiparty computation

How to play any mental game acompleteness theorem for protocols with honest majority

Communication-efficient unconditional MPC with guaranteed output delivery

Fast garbling of circuits under standard assumptions

Semi-honest to malicious oblivious transfer-the black-box way

Black-box constructions of protocols for secure computation

Smooth projective hashing and two-message oblivious transfer

Leviosa: Lightweight secure arithmetic computation

Actively secure garbled circuits with constant communication overhead in the plain model

Low cost constant round MPC combining BMR and oblivious transfer

The price of active security in cryptographic protocols. IACR Cryptology ePrint Archive

Amortizing garbled circuits

Zero-knowledge from secure multiparty computation

Secure protocol transformations

Founding cryptography on oblivious transfer -efficiently

Secure arithmetic computation with no honest majority

Overdrive: making SPDZ great again

Improved garbled circuit: free XOR gates and applications

The IPS compiler: optimizations, variants and concrete efficiency

An efficient protocol for secure two-party computation in the presence of malicious adversaries

Secure two-party computation via cut-and-choose oblivious transfer

Efficient constant round multiparty computation combining BMR and SPDZ

Blazing fast 2PC in the offline/online setting with security for malicious adversaries

A new approach to practical active-secure two-party computation

LEGO for two-party secure computation

Faster malicious 2-party secure computation with online/offline dual execution

Practical two-party computation based on the conditional gate

How to share a secret

Fast two-party secure computation with minimal assumptions

Faster secure two-party computation in the single-execution setting

Authenticated garbling and efficient maliciously secure two-party computation

Global-scale secure multiparty computation

How to generate and exchange secrets (extended abstract)

Two halves make a whole -reducing data transfer in garbled circuits using half gates