Issue 
Security and Safety
Volume 1, 2022



Article Number  2021001  
Number of page(s)  43  
Section  Information Network  
DOI  https://doi.org/10.1051/sands/2021001  
Published online  14 June 2022 
Review
Concretely efficient secure multiparty computation protocols: survey and more
^{1}
State Key Laboratory of Cryptology, Beijing, 100878, China
^{2}
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China
^{*} Corresponding author (email: yangk@sklc.org)
Received:
11
October
2021
Revised:
5
November
2021
Accepted:
6
December
2021
Secure multiparty computation (MPC) allows a set of parties to jointly compute a function on their private inputs, and reveals nothing but the output of the function. In the last decade, MPC has rapidly moved from a purely theoretical study to an object of practical interest, with a growing interest in practical applications such as privacypreserving machine learning (PPML). In this paper, we comprehensively survey existing work on concretely efficient MPC protocols with both semihonest and malicious security, in both dishonestmajority and honestmajority settings. We focus on considering the notion of security with abort, meaning that corrupted parties could prevent honest parties from receiving output after they receive output. We present highlevel ideas of the basic and key approaches for designing different styles of MPC protocols and the crucial building blocks of MPC. For MPC applications, we compare the known PPML protocols built on MPC, and describe the efficiency of private inference and training for the stateoftheart PPML protocols. Furthermore, we summarize several challenges and open problems to break though the efficiency of MPC protocols as well as some interesting future work that is worth being addressed. This survey aims to provide the recent development and key approaches of MPC to researchers, who are interested in knowing, improving, and applying concretely efficient MPC protocols.
Key words: Secure multiparty computation / Privacypreserving machine learning / Secret sharings / Garbled circuits / Oblivious transfer and its arithmetic generalization
Citation: Feng D and Yang K. Concretely efficient secure multiparty computation protocols: survey and more. Security and Safety 2022; 1: 2021001. https://doi.org/10.1051/sands/2021001
© The Author(s) 2022. Published by EDP Sciences and China Science Publishing & Media Ltd.
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1. Introduction
Secure multiparty computation (MPC) allows a set of parties to jointly compute a function on their private inputs without revealing anything but the output of the function. Specifically, MPC allows n parties to jointly compute the following function:
$$\begin{array}{c}\hfill ({y}_{1},\cdots ,{y}_{n})\leftarrow f({x}_{1},\cdots ,{x}_{n}),\end{array}$$
where every party P_{i} holds an input x_{i}, obtains an output y_{i}, and can learn nothing except for (x_{i}, y_{i}, f), and function f is often modeled as a Boolean or arithmetic circuit. MPC is a foundation of cryptography, and is also a core technology to protect privacy of data for cooperative computing in the big data era.
In the late 1980s, it was shown that MPC protocols for any function can be constructed [1–6], which demonstrates the feasibility of MPC. However, significant improvements are necessary to make MPC sufficiently efficient to be used in practice. In the last decade, MPC has been developed from a theoretical field to a practical one, and is starting to see reallife deployments. A series of opensourced libraries for MPC (e.g., ABY [7], EMPtoolkit [8], FRESCO [9], JIFF [10], MPSPDZ [11], MPyC [12], SCALEMAMBA [13], Bogdanov et al. [14], and TinyGable [15]) have been developed, and further promote the applications and deployment of MPC. We refer the reader to [16, 17] for more MPC libraries and the comparison of known libraries. Many applications can be built upon MPC to protect the privacy of data, including machine learning (see, e.g., [18–31] and references therein), federated learning (see, e.g., [32–36]), data mining [37–40], auction [41–43], genomic analysis [44–46], securing databases (see [47] and references therein), and blockchain [48–53]. In addition, some techniques underlying MPC protocols can also be used to construct noninteractive zeroknowledge (ZK) proofs [54–61] based on the MPCinthehead paradigm, scalable ZK proofs [62–71], threshold cryptography (see [72–79] and references therein), and private set intersection (PSI) (see, e.g., [80–85]).
Secure multiparty computation guarantees privacy (meaning that the protocol reveals nothing but the output) and correctness (meaning that the correct function is computed), among others (e.g., independence of inputs, meaning that a party cannot choose its input as a function of the other parties’ inputs). The security properties must be guaranteed in the presence of adversarial behaviors. We mainly consider two classic adversaries:

Semihonest: Semihonest adversaries (a.k.a., passive adversaries) follow the protocol specification but may try to learn more than allowed from the protocol transcript;

Malicious: Malicious adversaries (a.k.a., active adversaries) can run an arbitrary attack strategy in its attempt to break the protocol.
According to the maximum number t of corrupted parties, there are typically two settings considered in the literature: dishonest majority (n/2 ≤ t < n, particularly we often adopt t = n − 1) and honest majority (t < n/2), where n is the total number of parties. In addition to the basic properties (privacy and correctness), some applications might further require fairness meaning that if one party obtains output then so do all, or guaranteed output delivery (GOD) meaning that all parties always receive output. To obtain better efficiency, we often consider a relaxed security notion, called security with abort, which allows corrupted parties to prevent honest parties from receiving output after the corrupted parties received their output. This security notion is standard in the dishonestmajority setting, as not all functions can be computed fairly without an honest majority [86]. We focus on considering the notion of security with abort and the static adversary that determines the set of corrupted parties at the onset of protocol, which allows to achieve the best efficiency. In this paper, we mainly consider concretely efficient MPC protocols, and ignore the MPC protocols that have a good asymptotic complexity or optimal round complexity, but their concrete efficiency is very low.
There are two main approaches for designing MPC protocols [87]: (1) the secretsharing approach (followed by [2–4]) that makes the parties interact for every nonlinear gate of the circuit, and has a low communication bandwidth but a number of rounds linear to the circuit depth; (2) the garbledcircuit approach (followed by [1, 6]) that lets the parties construct an encrypted version of the circuit allowing to be computed only once, and has a constant number of rounds but a large communication bandwidth. In general, the secretsharing approach is more suitable for lowlatency networks such as local area network (LAN), while the garbledcircuit approach will perform better in highlatency networks such as wide area network (WAN).
There are a lot of concretely efficient MPC protocols that have been proposed, and these MPC protocols give a different tradeoff in terms of security and efficiency. Thus, it is not easy to make the best choice of MPC protocols in concrete applications for nonexperts. In addition, many techniques have been developed for MPC, which makes it difficult for new researchers to understand the techniques in a short period. Through this survey, we aim to help the researchers, who are interested in MPC, rapidly understand the recent development and some basic/key ideas of concretely efficient MPC protocols, and be able to make a better choice in terms of applying MPC protocols.
1.1. Our contribution
In this paper, we comprehensively survey the known work on concretely efficient MPC protocols with both semihonest and malicious security. This survey not only covers the work in the dishonestmajority setting, but also concerns on the recent development in the honestmajority setting. Our survey involves not only secretsharing based MPC but also garbledcircuit based MPC. We present the basic approaches for designing concretely efficient MPC protocols, and give the highlevel ideas for the key techniques underlying these MPC protocols. In particular, we give a uniform framework and view of MPC protocols based on additive, Shamir, and replicated secret sharings. We also provide a highlevel view of the recent approach with sublinear communication to design correlated oblivious transfer (COT) that is a crucial building block for dishonestmajority MPC. In addition, we describe one important application of MPC (i.e., privacypreserving machine learning, or PPML in short), and summarize the known PPML protocols in terms of functionality, security, techniques and neuralnetwork architectures as well as discussing several key techniques for designing concretely efficient PPML protocols. Furthermore, we propose several challenges and interesting open problems to break through the efficiency of differently flavored MPC protocols, and also present some future work that need to be addressed for developing or deploying MPC.
Comparison with other MPC surveys. Recently, Lindell [88] presented a short MPC survey, which gives an overview of the security of MPC, a summarization of MPC feasible results, an honestmajority MPC framework based on Shamir secret sharing, two specific MPC protocols (i.e., PSI and threshold RSA), a very short overview of dishonestmajority MPC, and several application examples of MPC. This survey focuses on the notion and security of MPC and how MPC is being currently used, and does not involve the recent development of MPC protocols which is addressed by our survey. Besides, Orsini [89] gave a survey for only SPDZstyle MPC protocols in the dishonestmajority malicious setting. Compared to the two surveys [88, 89], our survey is more comprehensive, presents an important MPC application (i.e., PPML) and also gives interesting future work for MPC.
1.2. Organization
In Section 2, we define the necessary notation to be used in the subsequent main body, and then describe the security and communication models for MPC and give a sketch of several basic building blocks of MPC. We describe the development and the key techniques for MPC based on secret sharings (resp., garbled circuits) in Section 3 (resp., Section 4). We present the crucial building blocks for dishonestmajority MPC in Section 5. In Section 6, we summarize the protocols that apply MPC to realize private inference and training of machine learning, as well as several key techniques for PPML applications. Finally, we conclude this survey, and propose open problems and future work for MPC.
2. Preliminaries
2.1. Notation
We use κ and ρ to denote the computational and statistical security parameters, respectively. In the known MPC implementations, we often adopt κ = 128 and ρ = 40, where sometimes we also consider ρ = 64 or ρ = 80. For two integers a, b with a < b, we denote by [a, b] the set {a, …, b} and by [a, b) the set {a, …, b − 1}. We use x ← S to denote sampling x uniformly at random from set S and x ← 𝒟 to denote sampling x according to distribution 𝒟. For bitstring x, we use lsb(x) to denote the least significant bit of x. For row vector x, we use x_{i} to denote the ith component of x with x_{1} the first entry, and denote by HW(x) the Hamming weight of x (i.e., the number of nonzero entries in vector x). For two families of distributions X = {X_{κ}}_{κ ∈ ℕ} and Y = {Y_{κ}}_{κ ∈ ℕ}, we write $X\stackrel{c}{\approx}Y$ if X and Y are computationally indistinguishable.
We use 𝔽 to denote a finite field defined by a prime or a power of prime, and denote by 𝔽 the size of field 𝔽. In particular, we often consider a binary field 𝔽 = 𝔽_{2} and an arithmetic field 𝔽 = 𝔽_{p} for a large prime p. Let 𝕂 be a field extension of 𝔽 of degree k. We fix some monic, irreducible polynomial f(X) of degree k and write 𝕂 ≃ 𝔽[X]/f(X). Then, we can denote every element y ∈ 𝕂 by a polynomial y_{0} + y_{1} ⋅ X + … + y_{k − 1} ⋅ X^{k − 1} over 𝔽, and view y as a vector (y_{0}, y_{1}, …, y_{k − 1})∈𝔽^{k}. When we write arithmetic expressions involving both elements of 𝔽 and elements of 𝕂, it means that values in 𝔽 are viewed as polynomials lying in 𝕂 with only constant terms. Specifically, we use 𝔽_{2κ} to denote the degreeκ extension field of 𝔽_{2}. In the context of MPC for Boolean circuits, we often use {0, 1}^{κ}, 𝔽_{2}^{κ} and 𝔽_{2κ} interchangeably, and thus addition in 𝔽_{2}^{κ} or 𝔽_{2κ} corresponds to XOR in {0, 1}^{κ}.
Most of the known MPC protocols model a function as a circuit. Specifically, circuit 𝒞 over an arbitrary field 𝔽 is defined by a set of input wires and output wires along with a list of gates of the form (α, β, γ, T), where α, β are the indices of the input wires of the gate, γ is the index of the output wire of the gate, and T ∈ {ADD, MULT} is the type of the gate. If 𝔽 = 𝔽_{2}, then 𝒞 is a Boolean circuit with ADD = ⊕ and MULT = ∧. Otherwise, 𝒞 is an arithmetic circuit where ADD/MULT corresponds to addition/multiplication in field 𝔽. We let 𝒞 denote the number of MULT gates in the circuit.
We will use n and t to denote the number of total parties and the number of corrupted parties respectively, unless otherwise specified. Sometimes, we call t as the corruption threshold.
2.2. Security and communication models
Security model. All security properties for MPC can be formalized in an Ideal/Real paradigm [90, 91], which provides a modular way to prove security. The realworld execution where the parties interact with semihonest/malicious adversary 𝒜 and execute a protocol Π is compared to the idealworld execution where the parties interact with a simulator ${\mathcal{S}}_{}$ and an ideal functionality ℱ. In the ideal word, ℱ plays the role of an incorruptible trusted party, and captures the security of MPC protocols. We use P_{1}, …, P_{n} to denote n parties running a protocol. In the multiparty setting (i.e., n > 2), we often consider a rushing adversary 𝒜, meaning that 𝒜 is allowed to receive its incoming messages in a round before it sends its outgoing message. If the adversary is allowed to be computationally unbounded, the protocol is said to be informationtheoretically secure. If the adversary is bounded to (nonuniform) probabilistic polynomial time (PPT), the protocol satisfies the computational security.
The known MPC protocols mainly use two types of simulation models: standalone setting [91, 92] and universal composability (UC) [90]. Compared to standalone model, UC model additionally involves an environment Ƶ which can determine the inputs of honest parties and receive the outputs from the honest parties. This may make security proofs of MPC protocols somewhat more complex. While standalone model only guarantees the security under the sequential composition, UC model has the property that the protocols maintain their security, even though running concurrently with other (in)secure protocols. According to the result from [93], we obtain that any MPC protocol in the standalone model, which is proven secure with a blackbox straightline simulator and has the property the inputs of all parties are fixed before the protocol execution begins (referred as to start synchronization or input availability), is also secure under concurrent composition.
Communication model. The default method of communication for MPC is authenticated channel, which can be implemented in practice using the known standard techniques. In the multiparty setting, all parties are also connected via pointtopoint channels, and sometimes need also a broadcast channel. A broadcast channel can be efficiently implemented using a standard 2round echobroadcast protocol [94], as we only consider security with abort. The communication overhead of this broadcast protocol can be significantly improved by letting all parties send the hash outputs of received messages and aborting if an inconsistent hash value is detected. Sometimes, the parties need to communicate over a private channel, meaning that the messages sent over such channel are kept confidential and authenticated. As such, private channel can be established using the standard techniques.
2.3. Oblivious transfer and oblivious linearfunction evaluation
Informally, oblivious transfer (OT) [95, 96] involves two parties where a sender inputs two messages (m_{0}, m_{1}) and a receiver inputs a choice bit b, and allows the receiver to obtain m_{b} while keeping b secret against the sender and m_{1 − b} confidential against the receiver. We use an OT extension protocol to generate a large number of OT correlations (see Section 5). Oblivious linearfunction evaluation (OLE) is an arithmetic generalization of OT to a large field 𝔽, and is a special case of oblivious polynomial evaluation introduced in [97]. Specifically, OLE is a twoparty protocol between a sender and a receiver, where the sender inputs u, v ∈ 𝔽, and the receiver inputs x ∈ 𝔽 and obtains an output y = u ⋅ x + v ∈ 𝔽. We discuss the development of OT/OLE and their variants in Section 5.
2.4. Commitment and cointossing
Commitment. In the dishonestmajority setting, MPC protocols often need a commitment scheme to commit a value while keeping it secret (the hiding property), and then to open the value while keeping it consistent with the one that has been committed (the binding property). To achieve high efficiency, the commitment scheme is often constructed in the randomoracle model by defining Commit(x)=H(x, r), where x is a message, r is a randomness, and H : {0, 1}^{*} → {0, 1}^{2κ} is a cryptographic hash function modeled as a random oracle.
Cointossing. A lot of MPC protocols with malicious security require the parties to generate multiple public randomness by executing a cointossing protocol, while guaranteeing that no malicious parties can control the randomness or make them deviate from uniform distribution. In the dishonestmajority setting, the cointossing protocol is constructed by that (1) every party P_{i} commits a random seed s_{i} and then opens the seed; (2) every party computes s := ⨁_{i ∈ [n]}s_{i} and then generates the public randomness with s and a pseudorandom generator (PRG) modeled as a random oracle. In the honestmajority setting, the cointossing protocol is constructed in a totally different way. Specifically, all parties generate multiple random shares, and then open these shares as the public randomness, where random shares can be generated very efficiently when a majority of parties are honest.
3. MPC protocols based on secret sharings
Based on the secretsharing approach, the concretely efficient MPC protocols enable the parties to send small messages per nonlinear gate, but has a number of rounds linear to the depth of the circuit being computed. For now, concretely efficient MPC protocols mainly adopt three kinds of linear secretsharing schemes (LSSSs): additive secret sharing, Shamir secret sharing [98], and replicated secret sharing (a.k.a., CNF secret sharing) [99, 100], where additive secret sharing is mainly used for MPC protocols in the dishonestmajority setting, while Shamir and replicated secret sharings are adopted for honestmajority MPC protocols. We first recall the constructions of these LSSSs in a uniform view. To achieve malicious security, additive secret sharing needs to be equipped with informationtheoretic message authentication codes (ITMACs), and thus we define two types of ITMACs used in MPC with dishonest majority. Note that ITMACs are unnecessary for Shamir/replicated secret sharing in the honestmajority setting. Then, based on LSSSs, we describe how to construct semihonest MPC protocols with a uniform structure. Finally, we present how to transform semihonest MPC protocols to maliciously secure MPC protocols using the stateoftheart checking techniques.
3.1. Linear secretsharing schemes
All the three kinds of LSSSs used in MPC are (n, t)threshold secret sharing schemes, which enable n parties to share secret x among the parties, such that no subset of t parties can obtain any information on secret x, while any subset of t + 1 parties can reconstruct secret x. Additive secret sharing can only be made for t = n − 1, while Shamir/replicated secret sharing allows any t < n (we often adopt t < n/2 for honestmajority MPC). The three kinds of LSSSs are defined over a field 𝔽. While additive/replicated secret sharing allows an anysized field (including 𝔽_{2}), Shamir secret sharing requires 𝔽> n. Below, we describe the constructions of these LSSSs and the useful procedures for designing MPC protocols.

Share(x): For x ∈ 𝔽, a dealer generates n shares x^{1}, …, x^{n}. By [x], we denote the sharing of x.

(a)
Additive secret sharing: This is the simplest LSSS as far as we know. To share a value x ∈ 𝔽, the dealer samples x^{i} ← 𝔽 for i ∈ [1, n] such that ∑_{i ∈ [1, n]}x^{i} = x, and sends x^{i} to P_{i}.

(b)
Shamir secret sharing: Let α_{1}, …, α_{n} ∈ 𝔽 be n distinct nonzero elements (e.g., α_{i} = i for i ∈ [1, n]). The dealer samples a random polynomial f(X) of degree t over 𝔽 such that f(0)=x, and then sends x^{i} = f(α_{i}) to P_{i}. Shamir secret sharing is mainly used for a large n in the honestmajority MPC protocols.

(c)
Replicated secret sharing: The dealer samples x^{T} ← 𝔽 for T ∈ 𝒯 such that ∑_{T ∈ 𝒯}x^{T} = x, where 𝒯 consists of all sets of t parties. Every party P_{i} obtains shares x^{T} for all T ∈ 𝒯 subject to i ∉ T. In general, the total number of shares is $\left(\genfrac{}{}{0pt}{}{n}{t}\right)$ and every party stores $\left(\genfrac{}{}{0pt}{}{n1}{t}\right)$ shares, which can become very large as n and t grow. Therefore, we mainly use replicated secret sharing when n is small. For example, if n = 3 and t = 1, then the dealer samples x^{1}, x^{2}, x^{3} ← 𝔽 such that x^{1} + x^{2} + x^{3} = x, and then sends (x^{2}, x^{3}) to P_{1}, (x^{1}, x^{3}) to P_{2} and (x^{1}, x^{2}) to P_{3}.
Note that the shares for replicated/Shamir secret sharing need to be sent over a private channel, but this may be not necessary for additive secret sharing in most cases. In MPC protocols, either a party P_{i} acts as a dealer if it knows secret x, or the computation of a dealer is performed distributedly by a protocol if no one knows x. In the computational setting, we can use the pseudorandom secret sharing (PRSS) approach [99] to reduce the communication cost that distributes the shares of Shamir and replicated sharings. For example, to generate a degreet Shamir sharing [x]_{t}, the dealer can send a random seed s_{i} to P_{i} who computes x^{i} with s_{i} and a pseudorandom generator PRG for each i ∈ [1, t]. Then, the dealer sends x^{t + 1}, …, x^{n} to P_{t + 1}, …, P_{n}, respectively, such that (x^{1}, …, x^{t + 1}) defines a degreet polynomial f with f(0)=x and x^{i} = f(α_{i}) for i ∈ [t + 2, n]. Since the seeds s_{1}, …, s_{t} can be reused for multiple Shamir sharings, the communication to send the seeds could be ignored. Besides, based on the PRSS technique [99], we can convert a random replicated sharing into a random Shamir sharing with a small communication to distribute the seeds. This technique is only suitable for a small number of parties, as the number of random seeds is $\left(\genfrac{}{}{0pt}{}{n}{t}\right)$ and grows exponentially with the number of parties.

(a)

Reconstruct([x]; i): This procedure enables only P_{i} to obtain secret x. When any t + 1 shares of [x] are sent to P_{i} over a private channel, secret x can be reconstructed by P_{i} as follows:

(a)
Additive secret sharing: Given {x^{j}}_{j ≠ i} from all other parties, P_{i} computes x := ∑_{i ∈ [1, n]}x^{i}.

(b)
Shamir secret sharing: Secret x can be reconstructed using Lagrange interpolation. Without loss of generality, we assume that P_{i} gets shares x^{1}, …, x^{t + 1}. Then P_{i} can compute x := ∑_{i ∈ [1, t + 1]}δ_{i}(0)⋅x^{i}, where δ_{i}(X)=∏_{j ∈ [1, t + 1],j ≠ i}(X − α_{j})/(α_{i} − α_{j}) is a degreet polynomial.

(c)
Replicated secret sharing: Given x^{T} for all T ∈ 𝒯 with i ∈ T, P_{i} computes x := ∑_{T ∈ 𝒯}x^{T}. Specifically, for (n, t)=(3, 1), after receiving x^{i} from one party, P_{i} computes x := x^{1} + x^{2} + x^{3}.

(a)

Open([x]): This procedure allows all parties to know x. This is easy to be realized by executing Reconstruct([x],i) for i ∈ [1, n], where a private channel is unnecessary.

Linear combination: Given public coefficients c_{1}, …, c_{ℓ}, c ∈ 𝔽, all parties can compute locally [y]:=∑_{h ∈ [1, ℓ]}c_{h} ⋅ [x_{h}]+c such that y = ∑_{h ∈ [1, ℓ]}c_{h} ⋅ x_{h} + c as follows:

(a)
Additive secret sharing: For i ≠ 1, P_{i} computes y^{i} := ∑_{h ∈ [1, ℓ]}c_{h} ⋅ x_{h}^{i} where x_{h}^{i} is P_{i}’s share of x_{h}. Party P_{1} computes y^{1} := ∑_{h ∈ [1, ℓ]}c_{h} ⋅ x_{h}^{1} + c.

(b)
Shamir secret sharing: For i ∈ [1, n], P_{i} computes y^{i} := ∑_{h ∈ [1, ℓ]}c_{h} ⋅ x_{h}^{i} + c.

(c)
Replicated secret sharing: Fix a set T_{1} ∈ 𝒯. For i ∈ T_{1}, P_{i} computes y^{T} := ∑_{h ∈ [1, ℓ]}c_{h} ⋅ x_{h}^{T} + c for all T ∈ 𝒯 subject to i ∉ T where x_{h}^{T} is the P_{i}’s share of x_{h}. For i ∈ [1, n],i ∉ T_{1}, P_{i} computes y^{T} := ∑_{h ∈ [1, ℓ]}c_{h} ⋅ x_{h}^{T} for all T ∈ 𝒯 with i ∉ T. In particular, when n = 3 and t = 1, y^{i} = ∑_{h ∈ [1, ℓ]}c_{h} ⋅ x_{h}^{i} if i ≠ 1 and y^{i} = ∑_{h ∈ [1, ℓ]}c_{h} ⋅ x_{h}^{i} + c otherwise, where P_{i} gets {y^{j}}_{j ≠ i}.

(a)
The LSSSs defined as above guarantee perfect privacy in the presence of malicious adversaries, but only provide correctness against semihonest adversaries. To achieve malicious security for the case of t < n/2, we need to modify the Reconstruct procedure as follows:

Reconstruct([x]; i): When all shares of [x] are sent to P_{i} over a private channel, P_{i} can reconstruct secret x as follows:

(a)
Shamir secret sharing: After receiving all shares x^{1}, …, x^{n} of [x], P_{i} can compute a polynomial f(X):=∑_{j ∈ [1, t + 1]}δ_{j}(X)⋅x^{j}, where ${\delta}_{j}(X)=\prod _{k\in [1,t+1],k\ne j}\frac{X{\alpha}_{k}}{{\alpha}_{j}{\alpha}_{k}}$ is a degreet polynomial. Then, for j ∈ [1, n]∖[1, t + 1], P_{i} computes f(α_{j}) and checks that x^{j} = f(α_{j}). If the check fails, P_{i} aborts; otherwise, it computes x := f(0). If the check passes, then all shares are computed from a unique polynomial f(X). We know that t + 1 shares of n shares are correct from honest parties, and uniquely determine the polynomial f(X). Therefore, x reconstructed by P_{i} is correct, if P_{i} does not abort. If multiple secret values need to be reconstructed, then we can optimize the communication similarly using a cryptographic hash function. In particular, P_{j} for all j ∈ [1, n]∖[1, t + 1] send the hash values of their shares to P_{i}, and then P_{i} computes their shares using polynomial interpolation and checks whether these hash values are correct.

(b)
Replicated secret sharing: For the sake of simplicity, we focus on the case that only one party of three parties allows to be corrupted (i.e., n = 3 and t = 1). For other honestmajority cases, this procedure can be done similarly.
Concretely, P_{i − 1} sends x_{(i − 1)}^{i} to P_{i} and P_{i + 1} sends x_{(i + 1)}^{i} to P_{i}, where the subscript indexes are computed module 3. Then P_{i} checks that x_{(i − 1)}^{i} = x_{(i + 1)}^{i}. If the check fails, P_{i} aborts; otherwise, it defines x^{i} := x_{(i − 1)}^{i} and computes x := x^{1} + x^{2} + x^{3}. Since either P_{i − 1} or P_{i + 1} is honest, the equality check can guarantee that share x^{i} is correct, and thus the secret x reconstructed by P_{i} is correct.
If [x_{1}],…,[x_{ℓ}] need to be reconstructed, then we can further reduce the communication of this procedure using a cryptographic hash function H : {0, 1}^{*} → {0, 1}^{κ} [101]. In particular, P_{i − 1} sends x_{1}^{i}, …, x_{ℓ}^{i} to P_{i}, while P_{i + 1} sends $\tau :=\mathsf{H}({\stackrel{~}{x}}_{1}^{i},\cdots ,{\stackrel{~}{x}}_{\ell}^{i})$ to P_{i}. Then, P_{i} checks τ = H(x_{1}^{i}, …, x_{ℓ}^{i}). If the check fails, P_{i} aborts; otherwise, it computes x_{h} := x_{h}^{1} + x_{h}^{2} + x_{h}^{3} for h ∈ [1, ℓ]. If P_{i − 1} is honest, then it is clear that P_{i} will obtain the correct secrets. Otherwise (i.e., P_{i + 1} is honest), if there exists some h ∈ [1, ℓ] such that ${x}_{h}^{i}\ne {\stackrel{~}{x}}_{h}^{i}$, then P_{i} will abort except with probability negl(κ), based on the second preimage resistance of H.

(a)
For additive secret sharing, we need to equip it with ITMACs to guarantee the security of procedures Reconstruct and Open in the presence of malicious adversaries, which is shown in the next subsection.
3.2. Informationtheoretic message authentication codes
In the dishonestmajority setting, MPC protocols can use additive secret sharing to execute the circuit evaluation privately [4, 102]. This is sufficient for semihonest security. Nevertheless, in the malicious setting, ITMACs need to be introduced to guarantee the correctness of secret values [103, 104]. Currently, there are twostyle ITMACs that are used in MPC protocols: BDOZstyle [105] and SPDZstyle [103]. While the original ITMACs are defined over a single large field, it is easy to extend them so that values are defined over an anysized field 𝔽 and authentication is done over a large extension field 𝕂, which is described as follows:

BDOZstyle ITMACs [105]: Sample a global key (a.k.a. MAC key) Δ ← 𝕂. For a message x ∈ 𝔽, sample a local key K ← 𝕂, and define an MAC on x as M = K + x ⋅ Δ, where (x, M) is held by a party ${\mathsf{P}}_{A}$ and (K, Δ) is produced by the other party ${\mathsf{P}}_{B}$. If a malicious ${\mathsf{P}}_{A}$ forges an MAC M′ on x′≠x such that M′=K + x′⋅Δ, then ${\mathsf{P}}_{A}$ learns Δ = (M − M′)/(x − x′), which occurs with probability 1/𝕂 as Δ is perfectly hidden.

SPDZstyle ITMACs [103]: Sample a global key Δ ← 𝕂. For a message x ∈ 𝔽, the MAC on x is defined as M = x ⋅ Δ. Note that every party holds the additive shares of Δ and M, and no party knows the key Δ and the MAC M (see below for details). The security analysis is similar to that of BDOZstyle ITMACs.
It is easy to see that SPDZstyle ITMACs are more compact than BDOZstyle ITMACs. Nevertheless, when applying to MPC, it is incomparable for the ITMACs of two styles. While BDOZstyle ITMACs are more suitable to be used in constantround MPC protocols based on distributed garbling [106–111], SPDZstyle ITMACs are mainly adopted to transform the semihonest GMW protocol [4] into efficient MPC protocols with malicious security.
Given the above ITMACs, we can define authenticated secret sharing (i.e., additive secret sharing with ITMACs authentication) as follows:

Initialize: For each i ∈ [1, n], a dealer samples Δ_{i} ← 𝕂, and sends Δ_{i} to P_{i}. For SPDZstyle ITMACs, the dealer also computes Δ := ∑_{i ∈ [1, n]}Δ_{i}, where Δ_{i} is the P_{i}’s share of Δ and can be also written as Δ^{i} in this case.

Share(x): For x ∈ 𝔽, the dealer generates n random additive shares x^{1}, …, x^{n} ∈ 𝔽 such that ∑_{i ∈ [1, n]}x^{i} = x, where x^{i} is the P_{i}’s share. Then, the dealer computes their MAC tags as follows:

(a)
BDOZstyle: Each share x^{i} is authenticated independently by n − 1 different parties. In particular, for each j ≠ i, sample K_{j}[x^{i}]←𝕂 and compute M_{j}[x^{i}]:=K_{j}[x^{i}]+x^{i} ⋅ Δ_{j}. Then send (x^{i},{(M_{j}[x^{i}],K_{i}[x^{j}])}_{j ≠ i}) to every party P_{i}.

(b)
SPDZstyle: Compute M := x ⋅ Δ, and then sample uniform MAC shares M^{1}, …, M^{n} such that ∑_{i ∈ [1, n]}M^{i} = x ⋅ Δ, i.e., ∑_{i ∈ [1, n]}M^{i} = (∑_{i ∈ [1, n]}x^{i})⋅(∑_{i ∈ [1, n]}Δ^{i}).
By [[x]], we denote the authenticated sharing of x.

(a)

Reconstruct(⟦x_{1}⟧, … , ⟦x_{l}⟧, i): This procedure enables only P_{i} to obtain secrets x_{1}, …, x_{ℓ} for some ℓ ∈ ℕ by executing as follows:

(a)
BDOZstyle: Let H : {0, 1}^{*} → {0, 1}^{κ} be a hash function modeled as a random oracle. For each j ≠ i, P_{j} computes τ_{j} := H(M_{i}[x_{1}^{j}],…,M_{i}[x_{ℓ}^{j}]), and then sends (x_{1}^{j}, …, x_{ℓ}^{j}, τ_{j}) to P_{i} over a private channel. Then, for j ≠ i, P_{i} checks that τ_{j} = H(K_{i}[x_{1}^{j}]+x_{1}^{j} ⋅ Δ_{i}, …, K_{i}[x_{ℓ}^{j}]+x_{ℓ}^{j} ⋅ Δ_{i}) holds. The soundness error is bounded by (n − 1)/𝕂+(n − 1)/2^{κ} based on the analysis [112]. Following the work [112], we can define H(m_{1}, …, m_{ℓ})=⨁_{i ∈ [1, ℓ]}F(m_{i}) and use the fixedkey AES to instantiate F, where the computation of fixedkey AES is blazing fast given hardwareinstruction support.

(b)
SPDZstyle: Let [[r]] be a random authenticated share. Every party sends its shares on [[x_{1}]], …, [[x_{ℓ}]], [[r]] to P_{i} over a private channel, and then P_{i} can reconstruct x_{1}, …, x_{ℓ} and r. All parties run a cointossing protocol to generate uniform elements χ_{1}, …, χ_{ℓ} ∈ 𝕂, and compute [[y]] := ∑_{h ∈ [1, ℓ]}χ_{h} ⋅ [[x_{h}]] + [[r]]. Then P_{i} computes y := ∑_{h ∈ [1, ℓ]}χ_{h} ⋅ x_{h} + r and sends it to all other parties. For each j ≠ i, P_{j} sends σ^{j} := M(y)^{j} − y ⋅ Δ^{j} to P_{i}. Then P_{i} computes σ^{i} := M(y)^{i} − y ⋅ Δ^{i} and checks that ∑_{h ∈ [1, n]}σ^{h} = 0.

(a)

Open(⟦x_{1}⟧, … , ⟦x_{l}⟧): This procedure allows all parties to get x_{1}, …, x_{ℓ}.

(a)
BDOZstyle: This is easy to be realized by executing Reconstruct([[x_{1}]], …, [[x_{ℓ}]], i) for i ∈ [1, n], where a private channel is unnecessary.

(b)
SPDZstyle: Every party broadcasts its shares on [[x_{1}]], …, [[x_{ℓ}]] to all other parties, and then computes the values x_{1}, …, x_{ℓ}. To verify the correctness of x_{1}, …, x_{ℓ}, all parties execute the following batchcheck procedure:

(i)
All parties execute a cointossing protocol to sample uniformly random χ_{1}, …, χ_{ℓ} ∈ 𝕂.

(ii)
The parties compute [[y]] := ∑_{h ∈ [1, ℓ]}χ_{h} ⋅ [[x_{h}]].

(iii)
Every party P_{i} computes σ^{i} := M(y)^{i} − y ⋅ Δ^{i}, and then commit σ^{i} to all other parties.

(iv)
Every party P_{i} opens σ^{i} to all other parties.

(v)
Every party P_{i} checks that ∑_{h ∈ [1, n]}σ^{h} = 0.

(i)

(a)
For MPC protocols in the dishonestmajority setting, the dealer is realized distributedly by executing a protocol, where global key Δ_{i} is sampled uniformly at random by party P_{i}. Note that authenticated shares (i.e., additive secret sharing equipped with ITMACs) are still additively homomorphic, as ITMACs are additively homomorphic. That is, given public coefficients c_{1}, …, c_{ℓ}, c ∈ 𝔽, all parties can compute locally [[y]] := ∑_{h ∈ [1, ℓ]}c_{h} ⋅ [[x_{h}]] + c. Authenticated shares of both styles are able to be generated using COT or its arithmetic generalization vector oblivious linearfunction evaluation (VOLE), which are discussed in Section 5.
Figure 1. Framework for semihonest MPC protocols based on the secretsharing approach in both dishonestmajority and honestmajority settings 
3.3. Semihonest protocols
In the semihonest setting, we use a simple framework to unify the stateofart concretely efficient MPC protocols, including 1) the GMW protocol [4] with optimizations [102, 113–115] based on additive secret sharing; 2) the BGW protocol [2] with optimizations [116–119] based on Shamir secret sharing; and 3) the secure threeparty computation (3PC) protocol [87] based on replicated secret sharing. Here, for MPC based on replicated secret sharing, we focus on the threeparty case for the sake of simplicity.
While the original GMW protocol only considers Boolean circuits, we easily extend it to arithmetic circuits over any finite field 𝔽 [120]. Similarly, while the stateoftheart 3PC protocol [87] with semihonest security in the honestmajority setting focuses on the case of Boolean circuits, it is easy to extend this protocol to work over any finite field 𝔽 [101]. Toward more parties (e.g., the number of parties is n = 4 or n = 5), MPC protocols based on replicated secret sharing can be constructed efficiently (see, e.g., [124–126]). In the presence of semihonest adversaries, the GMWlike protocols and the MPC protocols based on replicated secret sharing can be straightforwardly extended to work over a ring such as ℤ_{2k} for k = 32 or k = 64. Furthermore, the BGWlike protocols based on Shamir secret sharing can also work over a general ring (see, e.g., [127]). While integer computations modulo ℤ_{2k} are more natural for modern computers, and may be useful for simplifying implementations and applications such as machine learning (ML), we focus on the case of finite fields for the sake of simplicity.
Figure 2. Semihonest multiplication protocols based on secret sharings of different types 
Below, we present the framework for secretsharingbased MPC protocols in the semihonest setting, which is shown in Figure 1. Specifically, the inputs are shared secretly among all parties, and then the circuit is evaluated layerbylayer where all gates in a layer can be computed in parallel, and thus the communication round is linear to the depth of the circuit. Finally, the output of every party is reconstructed. While addition gates are free without any communication, the main cost of MPC protocols is to compute multiplication gates by executing a semihonest multiplication protocol ${\mathrm{\Pi}}_{\mathsf{Mult}}^{\mathsf{semi}}$. For LSSSs of different kinds, ${\mathrm{\Pi}}_{\mathsf{Mult}}^{\mathsf{semi}}$ is constructed in a different way. We sketch three classical constructions of ${\mathrm{\Pi}}_{\mathsf{Mult}}^{\mathsf{semi}}$ corresponding to three kinds of secret sharings in Figure 2, where the protocols are divided into two phases: the preprocessing phase where the circuit and input are unknown and the online phase where the circuit and input are known to all parties.
Toward additive secret sharing, the stateoftheart protocol adopts Beaver multiplication triples [121] to perform the multiplication of two secret values. In particular, a random Beaver triple ([a],[b],[c]) with c = a ⋅ b ∈ 𝔽 is generated in the preprocessing phase, and then is consumed to compute one multiplication using the Beaver technique in the online phase. If 𝔽 = 𝔽_{2}, then Beaver triples can be computed by OT extension protocols; otherwise, they are able to be computed using OLE protocols. Recently, Mouchet et al. [128] also used the multiparty homomorphic encryption (MHE) scheme to generate Beaver triples with semihonest security in the dishonestmajority setting. When the Beaver technique requires two elements per multiplication gate per party in the online phase, the communication can be further reduced to one element per multiplication gate per party using the technique underlying the Turbospeedz protocol [129]. In particular, the functiondependent preprocessing phase is introduced where the circuit is known but the input is still unknown, and circuitdependent Beaver triples are generated in this phase. Then, in the online phase, public values (i.e., the values obtained by masking actual values with random values) are computed by the parties, and the multiplication is performed with public values and circuitdependent Beaver triples. We describe the GMW protocol with this optimization as follows:

(1)
Consider (Λ_{w}, [λ_{w}]) as the additive secret sharing on a wire w, where Λ_{w} = z_{w} + λ_{w} ∈ 𝔽 is a public value, z_{w} is the actual value on w and λ_{w} is a random element. Here, [λ_{w}] can be generated by having every party share a random value to other parties and then sum all its shares as the resulting share of λ_{w} in the preprocessing phase.

(2)
For each wire w associated with P_{i}’s input x_{w}, P_{i} sends Λ_{w} = x_{w} + λ_{w} to all parties who define (Λ_{w}, [λ_{w}]) as the sharing on wire w.

(3)
For each addition gate (α, β, γ, ADD) with input sharings (Λ_{α}, [λ_{α}]) and (Λ_{β}, [λ_{β}]), the parties locally compute Λ_{γ} = Λ_{α} + Λ_{β} ∈ 𝔽 and [λ_{γ}]=[λ_{α}]+[λ_{β}], where [λ_{γ}] can be computed in the functiondependent preprocessing phase.

(4)
For each multiplication gate (α, β, γ, MULT) with input sharings (Λ_{α}, [λ_{α}]) and (Λ_{β}, [λ_{β}]), all parties generate a random sharing [λ_{αβ}] with λ_{αβ} = λ_{α} ⋅ λ_{β} ∈ 𝔽 by running a semihonest OT/OLE protocol with inputs [λ_{α}],[λ_{β}] in the functiondependent preprocessing phase. Then, the parties compute
$$[{\mathrm{\Lambda}}_{\gamma}]:={\mathrm{\Lambda}}_{\alpha}\xb7{\mathrm{\Lambda}}_{\beta}{\mathrm{\Lambda}}_{\alpha}\xb7[{\lambda}_{\beta}]{\mathrm{\Lambda}}_{\beta}\xb7[{\lambda}_{\alpha}]+[{\lambda}_{\alpha \beta}]+[{\lambda}_{\gamma}],$$
where [λ_{γ}] is a random sharing generated by the parties in the preprocessing phase. The parties execute Open([Λ_{γ}]) to obtain Λ_{γ}, and define (Λ_{γ}, [λ_{γ}]) as the sharing on the output wire γ.
The GMW protocol based on the multiplication protocol ${\mathrm{\Pi}}_{\mathsf{Mult}}^{\mathsf{semi}}$ shown in Figure 2 supports the corruption threshold t = n − 1 with n the number of total parties. If we allow n/2 ≤ t < n − 1 (that is still in the dishonestmajority setting), we can use the TinyKeys approach [114] to improve the efficiency of protocol ${\mathrm{\Pi}}_{\mathsf{Mult}}^{\mathsf{semi}}$ over a binary field. Specifically, for the number of honest parties h > 1, e.g., (h = 6, n = 20) or (h = 120, n = 400), Hazay et al. [114] used the IKNP OT extension protocol [113, 130] with short keys to generate Beaver multiplication triples. The basic idea is that the combination of the short keys of h honest parties will have a large entropy, although the short key of an honest party has only a low entropy. The TinyKeys approach can also be extended to the malicious setting using ITMACs with short keys [131].
Due to the recent development of PCGstyle OT extension protocols [132–134], these protocols outperform the IKNPstyle OT extension protocols [113, 130, 135, 136], and have the sublinear communication compared to the linear communication of the IKNPstyle protocols (see Section 5 for more details). In this case, the efficiency improvement using the TinyKeys approach seems to be significantly smaller, if the recent PCGstyle (instead of IKNPstyle) OT extension protocols are adopted to construct the protocol ${\mathrm{\Pi}}_{\mathsf{Mult}}^{\mathsf{semi}}$.
For Shamir secret sharing, if the number of parties is small (particularly n ≤ 5), the stateoftheart multiplication protocol is the GRR protocol [117] using the degreereduction approach. The GRR protocol works by letting every party locally multiply its shares of the inputs [x],[y], share the result to all other parties (allowing the degree of the polynomial to be reduced from 2t to t), and then locally compute a linear combination of shares as its share of the output [z]. If the number of parties is larger (e.g., n > 5), we mainly adopt the Damgård–Nielsen (DN) protocol [116] to realize the multiplication of two secret values. The original DN protocol [116] described in Figure 2 is informationtheoretically secure, and needs six elements of communication per multiplication gate per party. In the informationtheoretic setting, the communication cost of the DN protocol was first improved by Goyal et al. [119, 137] from 6 elements to 5.5 elements using a simple technique. Recently, the communication of the DN protocol was further improved to 4 elements per multiplication gate per party by Goyal et al. [118]. Inspired by the technique [119, 137], they first modify the original DN protocol [116] shown in Figure 2 to make ${P}_{\mathtt{king}}$ send a random degreet Shamir sharing [ϵ]_{t} (instead of ϵ) to all other parties and then all parties compute [z]_{t} := [ϵ]_{t} − [r]_{t} locally. Their crucial observation is that when ${P}_{\mathtt{king}}$ is an honest party, the corrupted parties only receive random elements from ${P}_{\mathtt{king}}$ in this case. This holds even if the corrupted parties know the whole double sharings ([r]_{t}, [r]_{2t}), since they only receive t shares that are uniformly random and independent of secret z = x ⋅ y. Therefore, we can split the tasks of computing multiplication gates as ${P}_{\mathtt{king}}$ into all parties rather than a fixed party in the original DN protocol. In particular, when we need to compute n multiplication gates, we let every party behave as ${P}_{\mathtt{king}}$ for one multiplication gate. If ${P}_{\mathtt{king}}$ is a corrupted party, we still need a pair of random double sharings. If ${P}_{\mathtt{king}}$ is an honest party, the double sharings do not need to be random. This means that we only need to generate t pairs of random double sharings for n multiplication gates in the preprocessing phase. In the computation setting, we can use the pseudorandom secret sharing approach [99] to further reduce the communication cost, which has been used in previous honestmajority MPC protocols such as [101, 138–140]. For example, the stateoftheart DNstyle protocol [118] can be optimized to two elements per multiplication gate per party using a pseudorandom generator (PRG). In addition, Goyal et al. [118] also proposed a combination of the improved DN multiplication and Beaver triple multiplication to reduce the round complexity by a factor of 2, at the cost of that the communication cost is additionally increased by 0.5 elements per multiplication gate per party. Recently, Abspoel et al. [141] used regenerating codes to construct a singleround multiplication protocol at the cost of increasing the communication complexity by a factor O(n/logn), where the regenerating property [142] of Shamir secret sharing requires that the number of parties n is large and the DN multiplication protocol needs about two rounds.
As for replicated secret sharing in the 3PC setting, the stateoftheart protocol [87, 101] is simple and needs to send only one element per multiplication gate per party. In particular, shares of z = x ⋅ y can be computed by every party locally. Then, every party needs to use a random 0sharing to randomize its share of z, and then sends the result to another party. The random 0sharing [r] is easy to be computed by having every party P_{i} send a uniform key k_{i} to P_{i + 1} for i ∈ [1, 3] and compute r^{i} := F(k_{i − 1}, id)−F(k_{i}, id) using the two keys that it holds where id is an identifier. While Shamir secret sharing is suitable for a large number of parties, replicated secret sharing is mainly used for a small number of parties (e.g., the number of parties n ∈ {3, 4, 5, 7, 9}). In addition, Keller et al. [143] showed that the 3PC protocol [87] can be generalized to a general Q_{2} access structure, which was further improved in [144] to eliminate the restriction of replicated secret sharing (i.e., requiring an exponentiallylarge number of shares for a large number of parties).
3.4. Maliciously secure protocols
The MPC protocols based on secret sharings described in the previous subsection guarantee security in the presence of semihonest adversaries. To achieve malicious security, some checking procedures need to be added. The underlying techniques to assure security against malicious adversaries are different between dishonestmajority MPC and honestmajority MPC. For example, MPC in the dishonestmajority setting needs ITMACs to authenticate values shared among all parties, but this is unnecessary for MPC with honest majority. Thus, we present the development for maliciously secure MPC in two different settings.
Dishonest majority. Goldreich, Micali and Wigderson (GMW) [4] proposed a general compiler to convert a semihonest MPC protocol into a maliciously secure MPC protocol for the same computational task. However, this compiler is nonblackbox using the generic zeroknowledge proofs to prove the correctness of computation in each step, and thus is not concretely efficient. Later, Ishai, Prabhakaran and Sahai (IPS) [145] proposed a blackbox compiler, where an inner MPC protocol with semihonest security computes a circuit in the OThybrid model, and an outer MPC protocol with malicious security in the honestmajority setting is used to guarantee the security of the whole MPC protocol in the presence of malicious adversaries. The IPS compiler was improved in [123] for multiparty setting, and was further optimized in [54, 146] for twoparty setting. However, the concrete efficiency for the maliciously secure MPC protocols based on the IPS compiler is still not sufficiently high. Recently, based on the IPS framework, Hazay et al. [147] proposed a new compiler using twolevel sharings where the outer level is Shamir secret sharing or algebraic geometric (AG) secret sharing [148], and the inner level is additive secret sharing. Their compiler allows an arbitrarysized field with constant communication overhead over the semihonest GMW protocol [4], but the concrete efficiency is still low.
In the dishonestmajority setting, concretely efficient MPC protocols based on ITMACs have the smallest overhead to achieve malicious security. Using ITMACs, we can transform the semihonest GMW protocol shown in Figure 1 to a maliciously secure protocol in the following way:

Replacing all additive secret sharings with authenticated secret sharings defined in Section 3.2.

For each wire w associated with P_{i}’s input x_{w}, the parties generate a random authenticated share [[r_{w}]] in the preprocessing phase, and then P_{i} broadcasts Λ_{w} := x_{w} − r_{w} to all parties who compute [[x_{w}]] := [[r_{w}]] + Λ_{w}.

Replacing the semihonest multiplication protocol ${\mathrm{\Pi}}_{\mathsf{Mult}}^{\mathsf{semi}}$ with a maliciously secure protocol ${\mathrm{\Pi}}_{\mathsf{Mult}}^{\mathsf{mali}}$.
We can also use the Beaver technique [121] to construct protocol ${\mathrm{\Pi}}_{\mathsf{Mult}}^{\mathsf{mali}}$ in the following steps:

Preprocessing phase: All parties generate a random authenticated triple ([[a]], [[b]], [[c]]) with c = a ⋅ b ∈ 𝔽. The generation of authenticated triples can be divided into two steps: 1) computing authenticated shares by executing a correlated OT (COT) or vector OLE (VOLE) protocol with malicious security, where the notion of COT and VOLE can be found in Section 5; 2) generating faulty authenticated triples with authenticated shares and then checking the correctness of these faulty authenticated triples. In the first step, all parties execute a maliciously secure COT/VOLE protocol in a pairwise way, and then run a consistencycheck procedure to check the consistency of shares and global keys among multiple executions. The stateoftheart consistency check adopts the random linear combination approach (see, e.g., [43, 104, 106, 108, 110]), and requires a very small communication overhead. For the second step, multiple approaches can be used for different applications (see below).

Online phase: This phase is similar to the semihonest protocol shown in Figure 2, except that authenticated shares are involved and the corresponding open procedure described in Section 3.2 is used. Similarly, the communication in this phase can be further improved from 2 elements per multiplication gate per party to only one element, using the technique in Turbospeedz [129].
When the Turbospeedz technique [129] and the batchcheck technique shown in Section 3.2 are used, the online phase of the maliciously secure GMWlike protocols [103, 104] has the optimal communication cost without sacrificing the security. Most of MPC studies focus on improving the efficiency of the preprocessing phase. Particularly, generating authenticated triples is the efficiency bottleneck. For the generation of authenticated triples, we consider two cases: 1) large fields (i.e., 𝔽≥2^{ρ}) and 2) binary fields (i.e., 𝔽 = 𝔽_{2}). Note that the techniques for binary fields are able to be used in other cases of small fields (e.g., 𝔽_{28}).
For the case of large fields, the SPDZ framework [103, 149] is the stateoftheart protocol in the dishonestmajority malicious setting. The original SPDZ protocol [103, 149] uses the depth1 homomorphic encryption (HE) scheme (i.e., the underlying HE scheme could support one multiplication) to generate authenticated triples in the preprocessing phase, and can evaluate the circuit fast in the online phase. Later, Keller et al. [43] proposed a SPDZstyle protocol called as MASCOT, which uses the OT extension protocol [136] and Gilboa multiplication idea [150] to generate authenticated triples more efficiently. Subsequently, based on additively homomorphic encryption [151] and latticebased zeroknowledge proofs, Keller et al. [152] presented an optimized SPDZstyle protocol referred to as Overdrive, which significantly improves the communication to generate authenticated triples. Overdrive includes two versions: LowGear for a small number of parties and HighGear for a large number of parties. The performance of HighGear is further improved by Baum et al. [153] via optimizing the underlying zeroknowledge protocol. In these SPDZ protocols, the underlying technique for checking the correctness of faulty authenticated triples is the socalled “sacrifice” technique. The improved sacrifice technique [43] works as follows:

Let ([[a]], [[b]], [[c]]) and $([\phantom{\rule{0.166667em}{0ex}}[\widehat{a}]\phantom{\rule{0.166667em}{0ex}}],[\phantom{\rule{0.166667em}{0ex}}[b]\phantom{\rule{0.166667em}{0ex}}],[\phantom{\rule{0.166667em}{0ex}}[\widehat{c}]\phantom{\rule{0.166667em}{0ex}}])$ be two faulty authenticated triples held by parties P_{1}, …, P_{n}. The parties execute the following procedure to check the correctness of the first triple ([[a]], [[b]], [[c]]) by sacrificing the second triple $([\phantom{\rule{0.166667em}{0ex}}[\widehat{a}]\phantom{\rule{0.166667em}{0ex}}],[\phantom{\rule{0.166667em}{0ex}}[b]\phantom{\rule{0.166667em}{0ex}}],[\phantom{\rule{0.166667em}{0ex}}[\widehat{c}]\phantom{\rule{0.166667em}{0ex}}])$.

(a)
Run a cointtossing protocol to sample a uniformly random element r ∈ 𝔽.

(b)
Compute $[\phantom{\rule{0.166667em}{0ex}}[\u03f5]\phantom{\rule{0.166667em}{0ex}}]:=r\xb7[\phantom{\rule{0.166667em}{0ex}}[a]\phantom{\rule{0.166667em}{0ex}}][\phantom{\rule{0.166667em}{0ex}}[\widehat{a}]\phantom{\rule{0.166667em}{0ex}}]$ locally.

(c)
Execute Open([[ϵ]]) to obtain ϵ.

(d)
Compute $[\phantom{\rule{0.166667em}{0ex}}[\sigma ]\phantom{\rule{0.166667em}{0ex}}]:=r\xb7[\phantom{\rule{0.166667em}{0ex}}[c]\phantom{\rule{0.166667em}{0ex}}][\phantom{\rule{0.166667em}{0ex}}[\widehat{c}]\phantom{\rule{0.166667em}{0ex}}]\u03f5\xb7[\phantom{\rule{0.166667em}{0ex}}[b]\phantom{\rule{0.166667em}{0ex}}]$ locally.

(e)
Run CheckZero([[σ]]) to verify that σ = 0, where CheckZero is the same as Open defined in Section 3.2, except that the values to be opened are 0 and thus are unnecessary to be sent.

When ℓ faulty authenticated triples need to be checked for some integer ℓ, the randomness r can be reused for all ℓ checking procedures, and the procedures Open and CheckZero can be done in a batch (see Section 3.2).

If c = a ⋅ b + e for some adversarially chosen error e and e ≠ 0, then we have the following:
$$\begin{array}{cc}\hfill \sigma & =r\xb7c\widehat{c}\u03f5\xb7b\hfill \\ \hfill & =r\xb7(a\xb7b+e)\widehat{c}(r\xb7a\widehat{a})\xb7b\hfill \\ \hfill & =r\xb7e\widehat{e},\hfill \end{array}$$
where $\widehat{e}=\widehat{c}\widehat{a}\xb7b$ is another error introduced by the adversary. If e ≠ 0, the probability that $\sigma =r\xb7e\widehat{e}$ is equal to 0 is 1/𝔽, as r is sampled uniformly at random after $e,\widehat{e}$ have been determined. Therefore, the checking procedure described as above requires 𝔽 to be a large field. We can also repeat the checking procedure t times to support a small field 𝔽, where 𝔽^{t} ≥ 2^{ρ} and t = ρ if 𝔽 = 𝔽_{2}. However, this will require a large computation and communication overhead.
Recently, Chen et al. [154] integrated the depth2 HE scheme [155, 156] into the SPDZ framework to improve the efficiency of SPDZ protocols for computing matrix multiplication and twodimensional convolution. For other general functions, it is not clear whether their approach can achieve a better efficiency, due to the larger parameters for HE.
While the semihonest GMW protocol over a field can be straightforwardly extended to ring ℤ_{2k}, this is not easy for SPDZstyle protocols with malicious security. Cramer et al. [157] proposed the first concretely efficient MPC protocol over a ring ℤ_{2k} in the SPDZ framework (named as SPDℤ_{2k}), using ITMACs over two different rings where the secret values are in ℤ_{2k} and the MAC tags are in ℤ_{2k + s}. Their protocol SPDℤ_{2k} uses the MASCOT idea to generate authenticated triples, but needs more communication than MASCOT [43]. Later, Damgård et al. [158] implemented SPDℤ_{2k}, designed new protocols for equality test, comparison, and truncation over ring ℤ_{2k}, and demonstrated that these operations in the ML domain using SPDℤ_{2k} are more efficient than the fieldbased SPDZstyle protocols [43, 152]. Subsequently, two improved MPC protocols based on the SPDℤ_{2k} idea have also been proposed [159, 160].
Recently, Boyle et al. [161] proposed several new protocols to generate Beaver multiplication triples and authenticated triples in the PCG framework based on a new variant of the ringLPN assumption. They use distributed point function (DPF) and the sparse feature of the noise in ringLPN to generate Beaver triples in the semihonest twoparty setting with a small communication. Using the programmability of PCG [162], the semihonest protocol for producing Beaver triples in the twoparty setting can be easy to be extended to the multiparty setting. Based on the construction of SPDZstyle authenticated shares, Boyle et al. [161] also extended the semihonest protocol to generate authenticated triples in the twoparty malicious setting. The maliciously secure protocol has a communication that is two orders of magnitude smaller than Overdrive. While the communication efficiency is attractive, it is worth further reducing the computational cost to make the PCG approach more practical. Boyle et al. [161] also gave a candidate construction for generating authenticated triples in the multiparty setting using the threeparty DPF [163], but its concrete efficiency is very low.
For the case of binary field (i.e., 𝔽 = 𝔽_{2}), we mainly consider two types of MPC protocols in the malicious setting: TinyOTstyle [104, 106–110, 164, 165] and MiniMACstyle [164, 166–169]. In particular, the subprotocols for generating authenticated triples underlying in the TinyOTstyle protocols can be used to design constantround MPC protocols with malicious security [106–110]. These TinyOTstyle protocols adopt the BDOZstyle ITMACs [105] to authenticate bits, and use the bucketing approach to eliminate the possible leakage of shares due to the selectivefailure attack, where the adversary can guess a bit share of an honest party with probability 1/2 but will be caught with the same probability. MiniMAC [168] aims to solve the problem that SPDZ [103] has a large communication overhead for binary field 𝔽_{2} (particularly the communication is blown up by a factor of ρ). Specifically, MiniMAC adopts a batch authentication idea: if k instances of the same Boolean circuit need to be computed at once, one can bundle these computations together and view them as the computation of a single Boolean circuit over a large ring 𝔽^{k}, where the addition and multiplication over 𝔽^{k} are componentwise. In MiniMAC, an ITMAC on message x ∈ 𝔽^{k} is defined as $C(\mathbf{x})*\mathrm{\Delta}$ where $\mathrm{\Delta}\in {\mathbb{F}}^{k}$, C is a linear errorcorrecting code with a large minimum distance and * is the componentwise product. MiniMACstyle MPC protocols [164, 166–169] also work for layered Boolean circuits where the gates of a Boolean circuit are partitioned into ordered layers and a layer only consists of gates of the same type. The recent MiniMACstyle protocol [166] adopts an algebraic tool called reverse multiplication friendly embedding (RMFE) [170] that is originally proposed for honestmajority MPC, and obtains a lower communication cost. Besides, for small fields, TinyTablestyle protocols [112, 171, 172] are proposed and very suitable for secure AES or 3DES evaluation using the onetime truth table approach.
Honest majority. In the malicious setting, we only need to check the correctness of multiplication gates, as addition gates are computed locally and always correct. In 2017, Lindell and Nof [101] observed that the semihonest DN protocol [116] has guaranteed the privacy of secret values in the presence of malicious adversaries, and allows the adversary to introduce an additive error in the output, i.e., for two sharings [x],[y], the DN protocol will output a sharing [z] with z = x ⋅ y + d where d is an additive error. This observation also holds for the GRR protocol [117] and the multiplication protocol based on replicated secret sharing [87]. They adopt the Beaver triples and the randomlinearcombination approach to check the correctness of multiplication gates, which introduces a relatively large overhead compared to the semihonest protocol. Subsequently, Chida et al. [138] proposed a different approach to verify the correctness of multiplication gates, where the semihonest multiplication protocol is executed twice and then the parties check the correctness of a multiplication gates using another related multiplication triple. Their MPC protocol still introduces twice the communication overhead compared to the semihonest DN protocol. Concurrently, Nordholt and Veeningen [140] also achieved the twice communication overhead. The studies [101, 138] mainly consider the case of large fields, and also present the correctness check for small fields by repeating the verification procedure which will introduce an large overhead. In the threeparty setting, Furukawa et al. [173] and Araki et al. [174] converted the semihonest protocol for Boolean circuits [87] to maliciously secure protocols using the “CutandChoose” approach, which will introduce a overhead of O(ρ/logN) where N is the number of multiplication gates. This overhead is smaller than the natural repeat approach, but is not optimal.
The MPC protocols described as above allow the corruption threshold t < n/2 where n is the number of parties. If t < n/3 is allowed, the MPC protocol with malicious security can be constructed at essentially the same cost as the bestknown semihonest protocol [139], i.e., the overhead to achieve malicious security is 1 and optimal. Their approach is as follows: 1) for two Shamir sharings [x]_{t} and [y]_{t}, the parties can locally compute the Shamir sharing of [z]_{2t} with z = x ⋅ y; 2) when t < n/3, the opening of [z]_{2t} can be guaranteed to be correct; 3) [z]_{2t} can be used to check the correctness of [z]_{t} that is obtained by running the semihonest DN protocol. If t < n/2, there are two recent techniques to achieve malicious security with an overhead of 1 over the bestknown semihonest protocol.
Comparison of honestmajority MPC protocols based on Shamir secret sharing
Specifically, one can use the distributed zeroknowledge proof with sublinear communication [124] to verify the correctness of multiplication gates. Firstly, Boneh et al. [124] used such zeroknowledge proofs and a variant of the DN protocol with replicated secret sharing to construct a maliciously secure MPC protocol for constant number of parties. At the first time, their approach obtains 1 bit per AND gate per party in terms of the amortized communication cost for the 3PC protocol about Boolean circuits. Their verification protocol requires $O(n\sqrt{N}+n)$ field elements per party of communication and constant rounds using the Fiat–Shamir heuristic, where n is the number of parties. In the threeparty setting, the concrete efficiency of the 3PC protocol by Boneh et al. [124] is significantly improved in [175], which achieves the best efficiency for now. Recently, Boyle et al. [125] used the distributed zeroknowledge proof in a new way, and constructed an MPC protocol with an optimal overhead over the bestknown semihonest protocol for an arbitrary number of parties. Their approach uses a new insight where for any secret sharing of a value x, we can simultaneously view shares of x as a sharing of each secret share x^{i} itself. Their verification protocol [125] for checking multiplication triples needs communication of O(nlogN + n) field elements per party and constant rounds.
Building on the technique [124] of distributed zeroknowledge proofs, Goyal et al. [119, 137] proposed another verification technique for multiplication gates to achieve malicious security with an overhead of 1, and requires O(logN) rounds and communication of (nlogN + n) field elements per party for the verification protocol.
They used a key observation that the semihonest DN protocol can compute the innerproduct of two vectors with the same communication cost [138], and adopted a recursive idea to perform the verification of multiplication gates. Concretely, their verification technique works as follows:

(1)
Given N = 𝒞 multiplication triples {([x_{i}],[y_{i}],[z_{i}])}_{i ∈ [1, N]} to be verified, where these tuples are computed using the semihonest DN protocol, parties P_{1}, …, P_{n} use a randomlinearcombination approach with a uniformly random r to compute the following vectors:
$$\begin{array}{cc}& [\mathbf{x}]:=([{x}_{1}],r\xb7[{x}_{2}],\cdots ,{r}^{N1}\xb7[{x}_{N}])\hfill \\ \hfill & [\mathbf{y}]:=([{y}_{1}],[{y}_{2}],\cdots ,[{y}_{N}])\hfill \\ \hfill & [z]:=\sum _{i\in [1,N]}{r}^{i1}\xb7[{z}_{i}].\hfill \end{array}$$
The verification of multiplication triples is reduced to verify whether z = x ⋅ y for ([x],[y],[z]).

(2)
Let k be a compression parameter. The parties transform the original tuple of dimension N into a new tuple of dimension N/k. Rewrite [x] and [y] as follows:
$$\begin{array}{cc}& [\mathbf{x}]=([{\mathbf{a}}_{1}],[{\mathbf{a}}_{2}],\cdots ,[{\mathbf{a}}_{k}])\hfill \\ \hfill & [\mathbf{y}]=([{\mathbf{b}}_{1}],[{\mathbf{b}}_{2}],\cdots ,[{\mathbf{b}}_{k}]),\hfill \end{array}$$
where {a_{i}, b_{i}}_{i ∈ [1, k]} are vectors of dimension N/k. For i ∈ [1, k − 1], the parties execute the semihonest DN protocol with innerproduct extension to compute [c_{i}] with c_{i} = ⟨a_{i}, b_{i}⟩. Then, they set [c_{k}]=[z]−∑_{i ∈ [1, k − 1]}[c_{i}]. Now, the parties need to verify the correctness of ([a_{i}],[b_{i}],[c_{i}]) for i ∈ [1, k]. This can be done in a batch using the batchwise multiplication verification technique [140, 176] to compress the verification of k innerproduct tuples into one check of a single innerproduct tuple of dimension m/k.

(3)
The parties repeat the second step log_{k}N times so that only a single multiplication triple needs to be checked. This final check can be performed using the randomization and opening approach.
The verification technique by Goyal et al. [119, 137] is originally described for Shamir secret sharing, and can also work for replicated secret sharing as the stateoftheart semihonest multiplication protocol [87, 101] has the same communication cost for computing innerproduct of two vectors.
Both of the stateoftheart verification techniques [125, 137] are based on the technique underlying the distributed zeroknowledge proofs [124]. Both techniques can obtain the same communication complexity, but has a different round complexity where the technique [119] requires O(logN) of rounds and the technique [125] has constant rounds. In terms of concrete communication efficiency, the verification protocol of multiplication gates by Goyal et al. [137] is slightly better than the protocol by Boyle et al. [125].
In Table 1, we compare the communication cost of several known honestmajority MPC protocols based on Shamir secret sharing for evaluating a single arithmetic circuit, where the left part compares the communication cost of semihonest MPC protocols and the right part compares the communication overhead of maliciously secure MPC protocols over semihonest protocols. For a large number of parties, the honestmajority MPC protocols as described above adopt Shamir secret sharing as the underlying LSSS, and thus require O(nlogn) bits per multiplication gate of communication complexity for evaluating a single Boolean circuit, as Shamir secret sharing requires that the size of field 𝔽 is greater than the number n of parties. Recently, based on RMFE [170], Polychroniadou and Song [177] combined Shamir secret sharing with additive secret sharing to reduce the communication complexity to O(n) bits per multiplication gate.
Two recent studies [178, 179] designed largescale MPC protocols, which scale practically to hundreds of thousands of parties. Such MPC protocols are interesting for applications that a large number of parties participate in the protocol execution. For example, in privacypreserving federated learning, thousands of lowresource devices are desired to train a ML model on their collective data. Additionally, when the number of parties is larger, the honestmajority assumption will become more believable. While the honestmajority MPC protocols [101, 116, 118, 119, 125, 137–139] have a total communication complexity O(n𝒞), both concretely efficient MPC protocols [178, 179] adopt packed secret sharing [180] to obtain the total communication complexity O(𝒞), where n is the number of parties and 𝒞 is the size of the circuit to be computed. While the work by Gordon et al. [179] has the total computation complexity O(logn ⋅ 𝒞) for any polynomialsized circuit, the work by Beck et al. [178] obtains the total computation complexity O(𝒞) for highly repetitive circuits (e.g., ML training algorithms). Packed secret sharing is an important tool that has been used to obtain the total communication complexity $\stackrel{~}{O}(\mathcal{C})$ for SIMD circuits^{1} [181–183], and is a generalization of Shamir secret sharing that defines as follows:

Let n be the number of parties and k be the number of secrets that are packed in a single sharing. Let α_{1}, …, α_{n}, β_{1}, …, β_{k} be n + k distinct nonzero elements over a field 𝔽.

A degreed packed Shamir sharing of secret vector x = (x_{1}, …, x_{k})∈𝔽^{k} is a vector (y^{1}, …, y^{n}), which satisfies that there exists a polynomial f(⋅)∈𝔽[X] of degree d, such that for each i ∈ [1, k], f(β_{i})=x_{i} and for all i ∈ [1, n], f(α_{i})=y^{i}. Party P_{i} obtains the ith share y^{i}.

To reconstruct the packed secret vector x, at least d + 1 shares are needed and it can be done by Lagrange interpolation. For a random degreed packed Shamir sharing of x, any d − k + 1 shares are independent of secret x. Thus, for corruption threshold t, we have d ≤ t + k − 1.
Recently, Goyal et al. [184] constructed a largescale MPC protocol, which achieves the total communication complexity O(𝒞) for a single circuit evaluation, using Hall’s Marriage Theorem. In the malicious setting, the MPC protocol by Goyal et al. [184] can achieve an overhead of 1 over the semihonest protocol using the verification technique [119], while the overhead for other recent MPC protocols [178, 179] is more than twice. Since no implementation is provided, the concrete efficiency of their MPC protocol is not clear. All the recent largescale MPC protocols [178, 179, 184] require that the number of corrupted parties t ≤ n(1/2 − ϵ) for 0 < ϵ < 1/2. Besides, Gordon et al. [179] suggested to use the SPDZ technique and a committee of t + 1 parties to design the online protocol, which is usable to reduce the online communication cost as only t + 1 parties instead of n parties run the online protocol. Concurrently, Escudero and Dalskov [185] improved the online communication cost of honestmajority MPC protocols using the Turbospeedz technique and the committee idea, and obtained the minimal online communication (i.e., one field element per multiplication gate per party).
4. Constantround MPC based on garbled circuits
For now, known concretely efficient constantround MPC protocols are constructed based on garbled circuits that are encrypted versions of circuits and can be computed only once. We first consider semihonest protocols, and then show how they are compiled to maliciously secure MPC protocols.
4.1. Semihonest protocols
4.1.1. Secure twoparty computation
The first constantround secure twoparty computation (2PC) protocol was proposed by Yao [6], and achieves semihonest security. The Yao’s 2PC protocol adopts garbled circuit (GC) and OT as the building blocks. Specifically, using a garbling scheme, a garbler ${\mathsf{P}}_{A}$ is able to generate a garbled circuit 𝒢𝒞, an encoding information e and a decoding information d.
Then, an evaluator ${\mathsf{P}}_{B}$ can evaluate 𝒢𝒞 with e, and then obtains the output bits according to d. The garbling scheme enables ${\mathsf{P}}_{B}$ to obtain a function output, but does not reveal any other information on the input to ${\mathsf{P}}_{B}$. We refer the reader to [186, 187] for the formal definition of garbling schemes. Roughly, Yao’s 2PC protocol with semihonest security is described in Figure 3.
Figure 3. Semihonest Yao’s 2PC protocol 
The 2PC protocol can be further optimized using the precomputing OT idea [188], where a random oblivious transfer (ROT) protocol is run in the preprocessing phase, and transform ROT to standard OT with chosen choice bits in the online phase. Besides, a GC can be sent in a pipelined way (i.e., garbled rows for a batch of gates are computed and communicated, and then these are done for the next batch of gates) [189], which allows the GC implementation to scale to an unlimited number of gates using a nearly constant memory. Subsequent studies focus on optimizing the Yao’s 2PC protocol in two aspects: improving the construction of GCs and designing more efficient OT extension protocols. Below, we describe the development of GCs, and postpone that of OT extension to Section 5.
Garbled circuits. The first GC construction was introduced by Yao [6] in 1986, but its formal description and security proof was first presented by Lindell and Pinkas until 2004 [190]. The original Yao GC construction requires 8κ bits per gate. The communication cost can be reduced to 4κ bits per gate using the “pointpermute” technique [1, 191], where the actual bit z_{w} on each wire w is masked by a random bit (a.k.a., permute bit) λ_{w}, and the resulting public value ${\mathrm{\Lambda}}_{w}={z}_{w}\oplus {\lambda}_{w}\in {\{0,1\}}^{}$ allows to be known by the evaluator. In this case, the decoding information d can be defined as the wire masks λ_{w} for all circuitoutput wires w. The garbled row reduction (GRR) technique [192] is able to further reduce the communication to 3κ bits per gate, where a garbled row is always defined as zero by specially setting the 0labels. Later, Pinkas et al. [193] used the polynomialinterpolation approach to further reduce the communication to 2κ bits per gate, where the technique is called 4to2 GRR compared to the 4to3 GRR technique [192]. In 2008, Kolesnikov and Schneider [194] proposed the freeXOR technique that enables XOR gates in the circuit to be garbled with no communication. In particular, the garbler sets L_{w, 1} = L_{w, 0} ⊕ Δ for each wire w where Δ is a fixed offset (a.k.a., global key). For each XOR gate (α, β, γ, ⊕), the garbler also sets L_{γ, 0} = L_{α, 0} ⊕ L_{β, 0} and λ_{γ} = λ_{α} ⊕ λ_{β}. Given the publicvalue and label pairs (Λ_{α}, L_{α, Λα}) and (Λ_{β}, L_{β, Λβ}) on the input wires, the evaluator can compute locally the public value
$${\mathrm{\Lambda}}_{\gamma}:=({z}_{\alpha}\oplus {z}_{\beta})\oplus {\lambda}_{\gamma}=({\mathrm{\Lambda}}_{\alpha}\oplus {\lambda}_{\alpha})\oplus ({\mathrm{\Lambda}}_{\beta}\oplus {\lambda}_{\beta})\oplus {\lambda}_{\gamma}={\mathrm{\Lambda}}_{\alpha}\oplus {\mathrm{\Lambda}}_{\beta}$$
and the label
$${\mathsf{L}}_{\gamma ,{\mathrm{\Lambda}}_{\gamma}}:={\mathsf{L}}_{\gamma ,0}\oplus {\mathrm{\Lambda}}_{\gamma}\xb7\mathrm{\Delta}=({\mathsf{L}}_{\alpha ,0}\oplus {\mathsf{L}}_{\beta ,0})\oplus ({\mathrm{\Lambda}}_{\alpha}\oplus {\mathrm{\Lambda}}_{\beta})\xb7\mathrm{\Delta}=({\mathsf{L}}_{\alpha ,0}\oplus {\mathrm{\Lambda}}_{\alpha}\xb7\mathrm{\Delta})\oplus ({\mathsf{L}}_{\beta ,0}\oplus {\mathrm{\Lambda}}_{\beta}\xb7\mathrm{\Delta})={\mathsf{L}}_{\alpha ,{\mathrm{\Lambda}}_{\alpha}}\oplus {\mathsf{L}}_{\beta ,{\mathrm{\Lambda}}_{\beta}}$$
on the output wire γ. While the 4to2 GRR technique [193] is not compatible with free XOR, the earlier 4to3 GRR technique [192] keeps compatible with free XOR. Afterward, Zahur, Rosulek, and Evans [195] improved the GC construction to 2κ bits per AND gate while keeping the XOR gates for free. The main idea behind their construction is to break an AND gate into two half gates for which the evaluator knows one input (i.e., a public value). We review the halfgate construction as follows:

Construction of GCs: The garbler computes a garbled row for an AND gate (α, β, γ, ∧) as below:
$$\begin{array}{cc}\hfill {G}_{\gamma ,0}:=& \mathsf{H}({\mathsf{L}}_{\alpha ,0},\gamma )\oplus \mathsf{H}({\mathsf{L}}_{\alpha ,1},\gamma )\oplus {\lambda}_{\beta}\xb7\mathrm{\Delta},\hfill \\ \hfill {G}_{\gamma ,1}:=& \mathsf{H}({\mathsf{L}}_{\beta ,0},\gamma )\oplus \mathsf{H}({\mathsf{L}}_{\beta ,1},\gamma )\oplus {\mathsf{L}}_{\alpha ,0}\oplus {\lambda}_{\alpha}\xb7\mathrm{\Delta}.\hfill \end{array}$$
The garbler also computes the 0label on the output wire γ as:
$${\mathsf{L}}_{\gamma ,0}:=\mathsf{H}({\mathsf{L}}_{\alpha ,0},\gamma )\oplus \mathsf{H}({\mathsf{L}}_{\beta ,0},\gamma )\oplus ({\lambda}_{\alpha}\xb7{\lambda}_{\beta}\oplus {\lambda}_{\gamma})\mathrm{\Delta}.$$

Evaluation of circuits: For any AND gate (α, β, γ, ∧), given (Λ_{α}, L_{α, Λα}) and (Λ_{β}, L_{β, Λβ}), the evaluator can evaluate the label on the output wire γ as follows:
$$\begin{array}{cc}\hfill \mathsf{E}val({\mathrm{\Lambda}}_{\alpha},{\mathrm{\Lambda}}_{\beta},{\mathsf{L}}_{\alpha ,{\mathrm{\Lambda}}_{\alpha}},{\mathsf{L}}_{\beta ,{\mathrm{\Lambda}}_{\beta}}):& =\mathsf{H}({\mathsf{L}}_{\alpha ,{\mathrm{\Lambda}}_{\alpha}},\gamma )\oplus \mathsf{H}({\mathsf{L}}_{\beta ,{\mathrm{\Lambda}}_{\beta}},\gamma )\oplus {\mathrm{\Lambda}}_{\alpha}\xb7{G}_{\gamma ,0}\oplus {\mathrm{\Lambda}}_{\beta}\xb7({G}_{\gamma ,1}\oplus {\mathsf{L}}_{\alpha ,{\mathrm{\Lambda}}_{\alpha}})\hfill \\ \hfill & =\mathsf{H}({\mathsf{L}}_{\alpha ,0},\gamma )\oplus \mathsf{H}({\mathsf{L}}_{\beta ,0},\gamma )\oplus ({\mathrm{\Lambda}}_{\alpha}\xb7{\mathrm{\Lambda}}_{\beta}\oplus {\mathrm{\Lambda}}_{\alpha}\xb7{\lambda}_{\beta}\oplus {\mathrm{\Lambda}}_{\beta}\xb7{\lambda}_{\alpha})\xb7\mathrm{\Delta}\hfill \\ \hfill & =\mathsf{H}({\mathsf{L}}_{\alpha ,0},\gamma )\oplus \mathsf{H}({\mathsf{L}}_{\beta ,0},\gamma )\oplus (({\mathrm{\Lambda}}_{\alpha}\oplus {\lambda}_{\alpha})\xb7({\mathrm{\Lambda}}_{\beta}\oplus {\lambda}_{\beta})\oplus {\lambda}_{\alpha}\xb7{\lambda}_{\beta})\xb7\mathrm{\Delta}\hfill \\ \hfill & =\mathsf{H}({\mathsf{L}}_{\alpha ,0},\gamma )\oplus \mathsf{H}({\mathsf{L}}_{\beta ,0},\gamma )\oplus ({\mathrm{\Lambda}}_{\gamma}\oplus {\lambda}_{\alpha}\xb7{\lambda}_{\beta}\oplus {\lambda}_{\gamma})\xb7\mathrm{\Delta}\hfill \\ \hfill & ={\mathsf{L}}_{\gamma ,0}\oplus {\mathrm{\Lambda}}_{\gamma}\xb7\mathrm{\Delta}={\mathsf{L}}_{\gamma ,{\mathrm{\Lambda}}_{\gamma}}.\hfill \end{array}$$
If the garbler sets lsb(Δ)=1, then lsb(L_{w, Λw})=lsb(L_{w, 0} ⊕ Λ_{w} ⋅ Δ)=lsb(L_{w, 0})⊕Λ_{w} for every wire w. Thus, the garbler can send lsb(L_{w, 0}) for the output wire w of each AND gate to the evaluator. Then, the evaluator can compute Λ_{γ} = lsb(L_{γ, Λγ})⊕lsb(L_{γ, 0}). Actually, the communication of bit lsb(L_{w, 0}) for each AND gate can be omitted, if we define a label L_{w, zw} corresponding to the actual bit z_{w} instead of the public value Λ_{w} for every wire w and set λ_{w} = lsb(L_{w, 0}), and thus Λ_{w} = lsb(L_{w, zw})=lsb(L_{w, 0} ⊕ z_{w} ⋅ Δ)=λ_{w} ⊕ z_{w}.
For every circuitoutput wire w, the garbler can send the wire mask ${\lambda}_{w}\in {\{0,1\}}^{}$ to the evaluator, who can compute the output bit z_{w} := Λ_{w} ⊕ λ_{w}.
For security, it is unnecessary to model H as a random oracle, and instead is sufficient to require that H satisfies the notion of circular correlated robustness hash function (circular CRHF) [196]. In this case, we can use a random permutation such as a fixedkey AES to implement CRHFs [197, 198]. Given the hardwareinstruction support, the computational efficiency of GCs can be significantly improved [197, 198]. This makes the efficiency bottleneck for GCs become the size of garbled circuits.
Zahur et al. [195] proved a lower bound of 2κ bits per AND gate in a model of linear garbling, which models the labels as a whole. Recently, Rosulek and Roy [199] broke through the half gates’ lower bound by introducing a new technique called slicing and dicing, while keeping fully compatible with the freeXOR technique. In particular, they improved the communication cost of GCs to 1.5κ + 5 bits per AND gate, when the computation is slightly more than half gates. In terms of techniques, they slice the garbled labels into two halves, and introduce more linear combinations to increase the linearalgebraic dimension in which the garbling scheme can operate. Besides, they also add some random control bits into the construction of GCs, where the control bits determine the linear combinations of labels and garbled ciphertexts, and are outside of the linear garbling model. However, the stateoftheart garbling scheme [199] is more complex and involves many linearalgebraic operations. It may be a challenging task to give a simple description of their garbling scheme, i.e., describe the garbling scheme as the clean composition of some simpler components similar to the halfgate construction.
In Table 2, we summarize the communication and computation costs of the known efficient garbling schemes by following the comparison table shown in [199], where the flexibleXOR technique [200] and fast 4to2 GRR technique [201] are also compared. Our survey only considers the garbling schemes on Boolean circuits, which allows to obtain the minimal size of garbled circuits. We refer the reader to [202–205] for garbling arithmetic circuits.
Comparison of concretely efficient garbling schemes
4.1.2. Secure multiparty computation
In the multiparty setting, constantround MPC has to deal with the case that multiple parties collude to cheat an honest party. Therefore, we cannot let only one party construct garbled circuits, and instead make all parties jointly construct a garbled circuit in a distributed manner. We use distributed garbling schemes to generate multiparty garbled circuits. The first distributed garbling scheme was introduced by Beaver, Micali, and Rogaway [1] in 1990. Based on the distributed garbling, they presented a constantround MPC protocol in the dishonestmajority setting, but this protocol has a very low concrete efficiency. In the semihonest setting, we focus on the case of allbutone corruption (i.e., n − 1 out of n parties allow to be corrupted). We describe several work that construct more efficient constantround MPC protocols in the honestmajority malicious setting in Section 4.2.
Surprisingly, in the dishonestmajority setting, the BMR garbling was first optimized until 2016 using the freeXOR technique [206]. Based on the optimized BMR garbled circuits, they proposed an efficient constantround MPC protocol with semihonest security. In particular, their improved BMR garbled circuit [206] is defined as follows:

Every party P_{i} with i ∈ [1, n] has the following secret values:

(a)
A global key Δ_{i} ∈ {0, 1}^{κ}.

(b)
For each wire w in the circuit, a share of a mask bit ${\lambda}_{w}\in {\{0,1\}}^{}$.

(c)
For each wire w, two garbled labels L_{w, 0}^{i}, L_{w, 1}^{i} ∈ {0, 1}^{κ} such that L_{w, 0}^{i} ⊕ L_{w, 1}^{i} = Δ_{i}.

(a)

For each AND gate (α, β, γ, ∧), for each $u,v\in {\{0,1\}}^{}$, all parties jointly compute the following:
$$\begin{array}{cc}\hfill {G}_{\gamma ,u,v}^{j}:=& \left(\underset{i\in [1,n]}{\u2a01}\mathsf{H}({\mathsf{L}}_{\alpha ,u}^{i},{\mathsf{L}}_{\beta ,v}^{i},\gamma \Vert j)\right)\oplus {\mathsf{L}}_{\gamma ,0}^{j}\oplus ((u\oplus {\lambda}_{\alpha})\xb7(v\oplus {\lambda}_{\beta})\oplus {\lambda}_{\gamma}))\xb7{\mathrm{\Delta}}_{j}.\hfill \end{array}$$
The multiparty garbled circuit consists of (G_{γ, u, v}^{1}, …, G_{γ, u, v}^{n}) for the output wire γ of each AND gate and each $u,v\in {\{0,1\}}^{}$.
While the BMR garbled circuit is symmetric that allows every party to evaluate the circuit, Wang, Ranellucci and Katz [109] proposed an asymmetric distributed garbling which only allows one party (e.g., P_{1}) to evaluate the circuit. The WRK garbled circuit is defined as follows:

Every party P_{i} holds the same secret values as in the BMR garbled circuits.

For each gate (α, β, γ, T) and $u,v\in {\{0,1\}}^{}$, let r_{γ, u, v} = (u ⊕ λ_{α})⋅(v ⊕ λ_{β})⊕λ_{γ}, and r^{i}_{γ, u, v} be the ith share of r_{γ, u, v}. Every pair of parties (P_{i}, P_{j}) hold the additive shares K_{i}[r^{j}_{γ, u, v}] and M_{i}[r^{j}_{γ, u, v}] of r^{j}_{γ, u, v} ⋅ Δ_{i}, such that K_{i}[r^{j}_{γ, u, v}]⊕M_{i}[r^{j}_{γ, u, v}]=r^{j}_{γ, u, v} ⋅ Δ_{i}.

For each i ≠ 1, for each AND gate (α, β, γ, ∧) and $u,v\in {\{0,1\}}^{}$, P_{i} computes the following:
$$\begin{array}{cc}& \mathsf{H}({\mathsf{L}}_{\alpha ,u}^{i},{\mathsf{L}}_{\beta ,v}^{i},\gamma )\oplus ({\left\{{\mathsf{M}}_{j}[{r}_{\gamma ,u,v}^{i}]\right\}}_{j\ne i},{\mathsf{L}}_{\gamma ,u,v}^{i}\oplus (\underset{j\ne i}{\u2a01}{\mathsf{K}}_{i}[{r}_{\gamma ,u,v}^{j}])\oplus {r}_{\gamma ,u,v}^{i}\xb7{\mathrm{\Delta}}_{i}),\hfill \end{array}$$
where the output length of H is nκ bits, while its output length is κ bits in the BMR garbled circuit.
Recently, Yang et al. [110] partially used the halfgate technique to further reduce the size of the WRK garbled circuit from 4n𝒞κ bits to (4n − 6)𝒞κ bits. The size of the BMR garbled circuit is 4n𝒞κ bits, and is larger than the WRK garbled circuit. The MPC protocols based on BMR garbled circuits will have 1–2 less online rounds than those based on WRK garbled circuits, if all parties obtain the output. The constantround MPC protocols based on distributed garbling achieve optimal online communication cost. The main task for improving constantround MPC is to reduce the communication cost in the preprocessing phase, while keeping the computation fast. However, the known constantround MPC protocols that are concretely efficient has O(n^{2}) computation complexity in the online phase. For a large number of parties, this becomes expensive. In 2017, BenEfraim et al. [207] constructed a constantround MPC protocol in the BMR framework, which achieves the computation complexity of O(1) in the online phase. This was done using keyhomomorphic pseudorandom functions that can be constructed under the DDH/LWE assumption. Their protocol in the online phase is more efficient than the stateoftheart semihonest MPC protocol [206] with O(n^{2}) computation complexity when the number of parties is at least 100. However, their approach is not compatible with the freeXOR optimization [194], which will introduce a large overhead in the preprocessing phase. Recently, BenEfraim et al. [208] used an encryption scheme that is both keyhomomorphic and messagehomomorphic based on the LPN assumption to construct a BMRlike garbled circuit that is compatible with freeXOR. Their LPNbased technique can obtain faster online computation when n ≥ 100, but requires a rather expensive preprocessing phase. If the number of honest parties is relaxed to h = n/c for some constant 1 < c < n, the preprocessing phase can be accelerated significantly using the techniques in [106, 109].
4.2. Maliciously secure protocols
In the malicious setting, we first consider the twoparty case, and then discuss the multiparty case in the dishonestmajority and honestmajority settings, respectively.
4.2.1. Secure twoparty computation
For constantround 2PC protocols, before 2017, one popular approach for designing maliciously secure protocols is to use the “CutandChoose” (C&C) technique. There are two different flavors to use such technique. The first one is the circuitlevel C&C approach that was introduced by Lindell and Pinkas [209] and optimized in [210–224], where many garbled circuits are prepared, a random subset of them are opened and verified, and the remaining unchecked circuits are evaluated. In the singleexecution setting where a circuit is computed at once on an input, ρ garbled circuits need to be prepared for statistical security 2^{−ρ} and the most efficient 2PC protocol in this setting is by Wang et al. [224]. In the amortized setting where the same circuit is evaluated multiple times on different inputs, only O(ρ/logτ) garbled circuits need to be prepared for amortizing over τ executions, and the bestknown 2PC protocol in this setting is by Rindal and Rosulek [221]. The second one is the gatelevel C&C approach that was introduced by Nielsen and Orlandi [225] and called LEGO, where a lot of individual garbled AND gates are prepared, a random subset of them are opened and verified, and the remaining unchecked garbled gates are soldered to a garbled fault tolerant circuit using the XORhomomorphic commitments. Subsequently, the LEGO protocol was optimized in [226–231]. Compared to the circuitlevel C&C approach, the gatelevel C&C approach has a lower asymptotic complexity O(ρ/log𝒞) and supports the functionindependent preprocessing where both circuit and input are unknown (where such preprocessing is not supported by the circuitlevel C&C approach), but is less efficient in the amortized setting and has also lower efficiency for some functions in the singleexecution setting.
In 2017, the milestone work by Wang, Ranellucci and Katz [108] proposed the authenticated garbling approach to construct highlyefficient 2PC protocols, where a single “authenticated” garbled circuit is constructed and transmitted. Their approach works in the following framework:

(1)
Functionindependent preprocessing phase: The parties run the TinyOTlike protocol to generate random authenticated bit shares and authenticated AND triples based on the BDOZstyle ITMACs, where authenticated shares can be produced by executing the OT extension protocol. An authenticated AND triple is defined as ([[a]], [[b]], [[c]]) with $a,b,c\in {\{0,1\}}^{}$ and c = a ∧ b.

(2)
Functiondependent preprocessing phase: In this phase in which the circuit is known, the parties generate an authenticated garbled circuit in a distributed way. In the process of generating authenticated garbled circuits, the key observation is that we can use the same global key for garbled circuits and authenticated shares, and thus the MAC tags and local keys involved in authenticated shares are naturally set as the shares to be used for constructing garbled circuits.

(3)
Online phase: The party P_{1} evaluates the circuit and obtains the output.
Wang et al. [108] proposed and adopted the WRK garbled circuit, and thus only one party P_{1} can evaluate the circuit. Concurrently, a similar approach is proposed by Hazay, Scholl, and SoriaVazquez [106] based on the BMR garbled circuit. Later, Katz et al. [107] significantly optimized the 2PC protocol by 1) applying the halfgate technique into distributed garbling, and 2) improving the communication and computation of the TinyOTlike protocol. The 2PC protocol [107] can generate a garbled circuit with 2κ + 1 bits per AND gate in the preprocessing phase, and performs the circuit authentication separately in a batch in the online phase. For now, the stateoftheart approach for maliciously secure 2PC is to adopt the distributed garbling approach [106–108], and is significantly outperform both C&C approaches. An interesting future work is to further reduce the size of distributed garbled circuits by Katz et al. [107].
4.2.2. Secure multiparty computation
Dishonest majority. For constantround MPC protocols tolerating allbutone malicious corruption, several studies [232–234] adopt the cutandchoose approach or the combination approach of BMR and SPDZ to construct MPC protocols. However, their concrete efficiency is very low. In this setting, the bestknown MPC protocols [106, 109–111] follow the distributed garbling framework [106, 108] based on TinyOTlike protocols. These MPC protocols have the same structure as that of 2PC protocols [107, 108], but need to execute a consistencycheck procedure to check the consistency of shares or global keys among multiple executions. Recently, Poddar et al. [235] applied the constantround MPC protocol [109] with malicious security to build a system called Senate that allows n parties to collaboratively run analytical SQL queries while keeping individual data private. The stateoftheart constantround MPC protocol with malicious security was proposed by Yang et al. [110], and can be used to further improve the performance of the above application. While the halfgate optimization is totally applied in the construction of distributed garbling in the twoparty setting [107], this is only done partially in the multiparty setting [110]. It is a challenge to totally apply the halfgate technique (or even the recent slicinganddicing technique [199]) to multiparty garbled circuits.
Honest majority. In the honestmajority setting, constantround MPC protocols can be constructed based on replicated secret sharing using less communication and computation (see, e.g, [236–239]). In the threeparty setting with at most one malicious corruption, Mohassel et al. [239] proposed the currently most efficient 3PC protocol with three rounds by constructing a single Yaostyle garbled circuit, where the maliciously secure 3PC protocol has the essentially same cost as the semihonest Yao’s 2PC protocol. Concurrently, Ishai et al. [238] constructed a tworound 3PC protocol while three garbled circuits need to be sent. In the fourparty setting with at most one malicious corruption, the stateoftheart protocol was proposed by Byali et al. [236], and has five rounds of communication and needs to send a single Yaostyle garbled circuit. This protocol can achieve the stronger security property, i.e., GOD. In the fiveparty setting with at most two malicious corruptions, Chandran et al. [237] presented the bestknown MPC protocol with 8 rounds of communication. They adopted the BMR garbled circuit to prevent collusion, and proposed a attested OT primitive to make the whole MPC protocol only rely on symmetrickey primitives without the need of OT protocols. In terms of communication cost, their maliciously secure protocol requires 60% less communication than the semihonest MPC protocol with dishonest majority [206], and its semihonest variant needs 8× less communication. Their construction [237] can be also extended to n parties with the corruption threshold $t\le \sqrt{n}$. Later, building upon the work [237], secure fiveparty computation (5PC) with fairness or GOD was also constructed in [240] with a small overhead over the 5PC protocol [237] satisfying security with abort.
5. Oblivious transfer and oblivious linearfunction evaluation
In this section, we describe the recent development and techniques of oblivious transfer (OT) and its important variants (i.e., random OT and correlated OT). Furthermore, we present the arithmetic generalization of OT called oblivious linearfunction evaluation (OLE) and its key variant (i.e., vector OLE). While OT is mainly used in MPC protocols for Boolean circuits, OLE is mainly applied in MPC protocols for arithmetic circuits. In this survey, we mainly review the stateoftheart techniques to construct (correlated) OT, and give a concise overview of the techniques to design (vector) OLE. Note that OLE has the same importance as OT. Additionally, vector OLE can be designed in the same framework as correlated OT for the stateofart technique based on learning parity with noise (LPN). We note that homomorphic encryption (HE) is a key technique to generate (vector) OLE correlations, although it is not described in detail in this section. The recent techniques based on LPN variants allow to obtain sublinear communication complexity, compared to linear communication complexity based on HE.
5.1. Oblivious transfer
Oblivious transfer (OT) [95, 96] is a fundamental cryptographic primitive between a sender S and a receiver R, which enables R to obtain only one of the two input messages of S, while S learns nothing on the R’s choice bit. It can be used to construct not only the Yao’s 2PC protocol but also a lot of other MPC protocols with both semihonest and malicious security. In addition, OT can also be used to design a lot of cryptographic protocols of other kinds. OT protocols can be constructed from different cryptographic assumptions, including decisional Diffie–Hellman (DDH) [241–245], computational Diffie–Hellman (CDH) [244, 246–248], learning with errors (LWE) [242, 245, 249–251], learning parity with noise (LPN) [247] and commutative supersingular isogeny Diffie–Hellman (CSIDH) [252]. However, when a large number of OT correlations need to be generated (particularly for MPC applications), these OT protocols based on public key operations are very expensive. To deal with this problem, Beaver [253] introduced the notion of OT extension, in which a small number of base OTs are extended efficiently to a large number of OTs (even any polynomial number of OTs) using fast operations. The first OT extension protocol by Beaver [253] uses the pseudorandom generator (PRG) in a nonblackbox way, and thus is only theoretically interesting. For now, concretely efficient OT extension protocols are divided into two styles: one based on the IKNP framework [130] and the other in the PCG framework [162, 254]. While the IKNPstyle protocols adopt the symmetrickey primitive PRG to perform extension and support chosen choice bits, the PCGstyle protocols utilize the sparse feature of the noise in the LPN problem [255] to realize extension and only allow random choice bits.^{2} OT extension of both styles adopts the following structure from weak OTs to standard OTs:
$$\begin{array}{c}\hfill \phantom{\rule{0.333333em}{0ex}}\text{Correlated OT (COT)}\phantom{\rule{4pt}{0ex}}\Rightarrow \phantom{\rule{4pt}{0ex}}\phantom{\rule{0.333333em}{0ex}}\text{Random OT (ROT)}\phantom{\rule{4pt}{0ex}}\Rightarrow \phantom{\rule{0.333333em}{0ex}}\text{OT},\end{array}$$
where COT requires two messages (m_{0}, m_{1}) of the sender satisfying the fixed correlation (i.e., m_{0} ⊕ m_{1} = Δ for a fixed string Δ), ROT only allows to output two uniformly random messages, and OT allows to input arbitrary two messages. Both transformations (i.e., COT ⇒ ROT and ROT ⇒ OT) are standard and recalled as follows:

COT ⇒ ROT: Given a CRHF H : {0, 1}^{2κ} → {0, 1}^{κ} and a COT correlation (K[b],(b, M[b])) with M[b]=K[b]⊕b ⋅ Δ, where K[b],Δ ∈ {0, 1}^{κ} are two random strings held by the sender and $b\in {\{0,1\}}^{},\mathsf{M}[b]\in {\{0,1\}}^{\kappa}$ are held by the receiver, a ROT correlation ((r_{0}, r_{1}),(b, r_{b})) can be computed without any interaction as below:
$${r}_{0}:=\mathsf{H}(\mathsf{K}[b],i),\phantom{\rule{1em}{0ex}}{r}_{1}:=\mathsf{H}(\mathsf{K}[b]\oplus \mathrm{\Delta},i),\phantom{\rule{1em}{0ex}}{r}_{b}:=\mathsf{H}(\mathsf{M}[b],i),$$
where i is an index associated with the COT correlation. While the index i can be omitted in the semihonest setting, it is necessary for malicious security [198].

ROT ⇒ OT: Given a ROT correlation ((r_{0}, r_{1}),(b, r_{b})) where the sender obtains two random strings r_{0}, r_{1} and the receiver gets a choice bit b and the string r_{b}, a standard OT correlation ((m_{0}, m_{1}),(b, m_{b})) can be constructed using the “onetime padding” technique as follows:

The sender sends τ_{0} = m_{0} ⊕ r_{0} and τ_{1} = m_{1} ⊕ r_{1} to the receiver, who computes m_{b} = τ_{b} ⊕ r_{b}.

Therefore, we can focus on designing concretely efficient COT protocols, and then transform them to standard OT protocols. In addition, COT protocols are able to be used to generate BDOZstyle authenticated shares using the TinyOTlike protocols [104, 106–110] as well as SPDZstyle authenticated shares using the bitdecomposition idea [43, 150]. For GCs with freeXOR, the garbled labels for every wire in the circuit satisfy the COT correlation, and thus can be transmitted obliviously from a garbler to a evaluator using a COT protocol, i.e., COT can also be straightforwardly used in MPC protocols.
The semihonest IKNP protocol [130] (improved in [113]) works roughly as follows: 1) execute a baseOT protocol (relying on publickey operations) to generate κ ROT correlations in the setup phase, by switching the role of the sender and receiver and then 2) extend κ ROT correlations to a large number of COT correlations in the extension phase, using PRG and switching column vectors into row vectors. The extended phase can be executed iteratively to generate an unlimited number of COT correlations, when using the same setup phase [113]. Later, the IKNPstyle OT extension protocols with malicious security were proposed in [135, 136]. Using the randomlinearcombination approach, the maliciously secure protocol by Keller, Orsini, and Scholl [136] achieves the best efficiency in the IKNP framework, and has the communication cost matching that of the bestknown semihonest protocol [113]. While the IKNPstyle OT extension protocols enjoy fast computation, they require linear communication cost (i.e., κ bits per COT correlation).
Another style of OT extension protocols lies in the pseudorandom correlation generator (PCG) framework [162, 254].^{3} In general, the PCGstyle OT extension protocols [132, 134, 162, 256] are able to generate COT correlations with sublinear communication (i.e., $\stackrel{~}{O}(\sqrt{N})$ for producing N COT correlations), but need more computation than IKNPstyle protocols. To simplify the following description, we now give an informal definition of COT in a vector form. Specifically, sender S obtains a uniform global key Δ ∈ 𝔽_{2κ} and a random vector v ∈ 𝔽_{2κ}^{N}, while receiver R holds a uniform choicebit vector u ∈ 𝔽_{2}^{N} and a vector w ∈ 𝔽_{2κ}^{N} such that w = v + Δ ⋅ u.
For both semihonest and malicious security, the stateoftheart PCGstyle COT protocols [132, 134] are constructed in the following three layers:

(1)
SPCOT: Construct a singlepoint COT (SPCOT) protocol, a variant of COT where the Hamming weight of the choicebit vector u is exactly 1 (i.e., HW(u)=1). We can use a point α ∈ [1, N] to represent the location of the single nonzero entry, meaning that u_{α} = 1 and u_{i} = 0 for i ≠ α. We can construct the SPCOT protocol using the following approach:

Semihonest security: The bestknown SPCOT protocol [132] in the semihonest setting adopts the designing idea of the puncturable pseudorandom function (PPRF) construction based on the GGM tree [257].^{4} In particular, a PPRF is a special pseudorandom function F, which can generate a normal key k and a punctured key k{α} for an input α, such that k can be used to evaluate F at each point, and k{α} allows to evaluate F at every point except for α without leaking any information about F(k, α) [258, 259]. Using the binarytree structure of GGMPPRF, sender S can transmit k{α} to the receiver R without knowing any information on α, by executing the OT protocol logN times in parallel. We refer the reader to [132, 260] for details. Using key k, S can compute vector v as v_{i} := F(k, i)∈𝔽_{2κ} for i ∈ [1, N]. With k{α}, R is able to compute w_{i} := F(k, i)∈𝔽_{2κ} for i ≠ α. To define value w_{α}, S could send τ = Δ + ∑_{i ∈ [1, N]}v_{i} ∈ 𝔽_{2κ} to R, who can compute w_{α} := τ + ∑_{i ≠ α}w_{i}. Since w_{i} = v_{i} for each i ∈ [1, N], i ≠ α, we have that w_{α} = τ + ∑_{i ≠ α}w_{i} = Δ + ∑_{i ∈ [1, N]}v_{i} + ∑_{i ≠ α}v_{i} = v_{α} + Δ, where addition is performed over binary field 𝔽_{2κ}. Therefore, we obtain that w = v + Δ ⋅ u holds, where R defines u as u_{α} = 1 and u_{i} = 0 for i ≠ α.

Malicious security: The above SPCOT protocol allows a malicious sender S to send incorrect messages in the OT protocol executions, so that the punctured key obtained by receiver R does not correspond to the punctured point α. The deviation of the outputs of two parties can be detected by the receiver by executing a consistencycheck procedure. The highlevel idea for the stateoftheart consistency check [134] is as follows:
 (a)
From v + w = Δ ⋅ u, we apply a random linear combination defined by uniformly random coefficients χ_{1}, …, χ_{N} ∈ 𝔽_{2κ} sampled by R into two sides of the equation. According to u_{α} = 1 and u_{i} = 0 for i ≠ α, we obtain the following result:
$$\sum _{i\in [1,N]}{\chi}_{i}\xb7{v}_{i}+\sum _{i\in [1,N]}{\chi}_{i}\xb7{w}_{i}={\chi}_{\alpha}\xb7\mathrm{\Delta}.$$
 (b)
Using the approach underlying the MASCOT protocol [43], S and R can compute the additive shares of χ_{α} ⋅ Δ:
$$Y+Z={\chi}_{\alpha}\xb7\mathrm{\Delta},$$
where it needs extra κ COT correlations.
 (c)
Combining two equations, we have the following:
$$\begin{array}{cc}\hfill V:=& \sum _{i\in [1,N]}{\chi}_{i}\xb7{v}_{i}+Y\hfill \\ \hfill & =\sum _{i\in [1,N]}{\chi}_{i}\xb7{w}_{i}+Z:=W.\hfill \end{array}$$(1)
The remaining task is to check V = W by running an equalitytest protocol. Since V and W are unnecessary to be kept secret, the equalitytest protocol can be constructed in a highly efficient manner using a cryptographic hash function [69, 134].
 (a)


(2)
MPCOT: Construct a multipoint COT (MPCOT) protocol, a variant of COT with HW(u)=t for a parameter t > 1. Based on the SPCOT protocol, an MPCOT protocol can be constructed in a fairly straightforward way:

Given the length N of MPCOT vectors, two parties S and R can execute the SPCOT protocol t times with each the outputting length N/t. Then, for i ∈ [1, t], S obtains v_{i} ∈ 𝔽_{2κ}^{N/t}, and R gets w_{i} ∈ 𝔽_{2κ}^{N/t} and u_{i} ∈ 𝔽_{2}^{N/t} with HW(u_{i})=1. Sender S defines v := (v_{1}, …, v_{t})∈𝔽_{2κ}^{N}, and receiver R sets w := (w_{1}, …, w_{t})∈𝔽_{2κ}^{N} and u := (u_{1}, …, u_{t})∈𝔽_{2}^{N} where HW(u)=∑_{i ∈ [1, t]}HW(u_{i})=t.

The MPCOT protocol described as above needs tlogN/t OT correlations to execute the SPCOT subprotocol. These OT correlations (thousands of OT correlations for concrete parameters t, N [132, 134]) can be generated using the IKNPstyle OT extension protocol [113, 136]. For malicious security, extra tκ COT correlations are required. This can be optimized to κ COT correlations by combining t consistency checks into a single check (see [134] for details).

In the malicious setting, a malicious sender S may use different Δ in the t SPCOT protocol executions. Thus, we need a consistencycheck procedure to guarantee the consistency of Δ. The stateoftheart consistency check [134] guarantees the consistency of Δ for free, as the SPCOT correlations are always assured to use the same Δ as the extra κ COT correlations, which have guaranteed the consistency of Δ.


(3)
COT from LPN: This procedure extends MPCOT correlations to COT correlations with uniform choice bits, based on the LPN assumption. For both semihonest and malicious security, this procedure is the same, and only involves local computation.

Based on the MPCOT protocol, two parties S and R can generate a lengthN MPCOT vector (s, (r, e)) such that r = s + Δ ⋅ e ∈ 𝔽_{2κ}^{N}. Here, we can view e ∈ 𝔽_{2}^{N} as the noise vector of an LPN problem, such that e is divided into t consecutive subvectors of length N/t where each subvector has a single nonzero entry at a random position. Such distribution is called as a regular noise distribution. As analyzed and observed in previous work [114, 132, 162, 254, 261], no known attack exploits a regular noise distribution, and performs significantly better than a uniform noise distribution where e is a uniform vector such that HW(e)=t.

Based on LPN assumptions of two different flavors, S and R can generate COT correlations in the following two ways:
 (a)
Dual LPN: Informally, the dualLPN assumption with a regular noise distribution 𝒟_{t} states that:
$$\begin{array}{c}\hfill \mathbf{e}\xb7\mathbf{H}\stackrel{x}{\approx}\mathbf{u},\end{array}$$
where e ← 𝒟_{t}, H ∈ 𝔽_{2}^{N × n} is a matrix created by a code generation algorithm, u ∈ 𝔽_{2}^{n} is a uniform vector and N = c ⋅ n for a compression parameter c > 1 (e.g., c = 2 or 4). The dualLPN assumption is also known as the regular syndrome decoding (RSD) assumption, which is introduced in [261] as the assumption underlying the security of the candidate fast syndromebased (FSB) hash function for the SHA3 competition. Given an MPCOT vector (s, (r, e)), S and R output a COT vector (v, (u, w)) as follows:
$$\mathbf{v}=\mathbf{s}\xb7\mathbf{H}\in {\mathbb{F}}_{{2}^{\kappa}}^{n},\phantom{\rule{1em}{0ex}}\mathbf{u}=\mathbf{e}\xb7\mathbf{H}\in {\mathbb{F}}_{2}^{n},\phantom{\rule{1em}{0ex}}\mathbf{w}=\mathbf{r}\xb7\mathbf{H}\in {\mathbb{F}}_{{2}^{\kappa}}^{n}.$$
 (b)
Primal LPN: Informally, the primalLPN assumption with a regular noise distribution 𝒟_{t} states that:
$$\begin{array}{c}\hfill \mathbf{a}\xb7\mathbf{A}+\mathbf{e}\stackrel{c}{\approx}\mathbf{u},\end{array}$$
where a ← 𝔽_{2}^{k} is a uniform vector, A ∈ 𝔽_{2}^{k × n} is a matrix created by a code generation algorithm, e ← 𝒟_{t}, u ∈ 𝔽_{2}^{n} is a uniform vector and k < n. In this case, two parties S and R additionally need a lengthk COT vector (b, (a, c)) such that c = b + Δ ⋅ a ∈ 𝔽_{2κ}^{k} and a ∈ 𝔽_{2}^{k} is a uniform vector. Then, given an MPCOT vector (s, (r, e)), S and R can output vector v and two vectors (u, w), respectively, as follows:
$$\mathbf{v}=\mathbf{b}\xb7\mathbf{A}+\mathbf{s}\in {\mathbb{F}}_{{2}^{\kappa}}^{n},\phantom{\rule{1em}{0ex}}\mathbf{u}=\mathbf{a}\xb7\mathbf{A}+\mathbf{e}\in {\mathbb{F}}_{2}^{n},\phantom{\rule{1em}{0ex}}\mathbf{w}=\mathbf{c}\xb7\mathbf{A}+\mathbf{r}\in {\mathbb{F}}_{{2}^{\kappa}}^{n}.$$
In general, the COT protocol based on dual LPN enjoys a lower communication but has a slower computation, while that based on primal LPN enjoys a faster computation but has a higher communication.
 (a)

Bootstrapped iterations: To generate an unlimited number of COT correlations, two parties can execute the COT protocol iteratively in a bootstrapped mode. In particular, let M be the number of all setup COT correlations to execute the whole COT protocol, where $M=tlog\frac{N}{t}$ for dual LPN and $M=k+tlog\frac{n}{t}$ for primal LPN in the semihonest setting, and M is further increased by κ for malicious security. Every iteration produces n COT correlations using the setup COT correlations, and outputs n − M COT correlations where the remaining M COT correlations are stored and bootstrapped as the refreshed setup COT correlations to be used in the next iteration. In the first iteration, M setup COT correlations can be generated using the IKNPstyle OT extension protocol [113, 136]. When a huge number of COT correlations are required and many iterations are executed, the setup cost for generating setup COT correlations in the first iteration can be amortized to negligible.

Figure 4. Structure of the PCGbased COT protocols. When κ = 128, we need to use publickey operations to compute 128 base ROT correlations based on the DDH, CDH, or LWE assumptions. We can use the IKNPstyle OT extension protocol to generate COT correlations in an order of magnitude 10^{3} − 10^{4}, and then extend them to COT correlations in an order of magnitude 10^{5} − 10^{7} (or even more) based on the LPN assumption 
In Figure 4, we present the structure of the PCGbased COT protocol described as above. According to the bestknown implementations, the IKNPstyle protocols are highly efficient to compute thousands of COT correlations, and the PCGstyle protocols will be more efficient if millions of COT correlations are required even if the network bandwidth is large enough.
Recently, Rindal et al. [133] proposed a new variant of the dualLPN assumption, using a structured and sparse matrix H generated a new LDPC code. When applying the new dualLPN problem into the semihonest COT protocol by Boyle et al. [132], they showed that the COT protocol based on dual LPN can simultaneously achieve lower communication and faster computation than the bestknown COT protocol based on primal LPN [134], as the new structured LPDC codes [133] support fast encoding operation. Based on the new dualLPN assumption [133], the COT protocol [132] could even obtain 37% less computation than the bestknown IKNPstyle protocol [113]. However, the efficiency gain builds upon an aggressive dualLPN problem based on heuristically designed linear codes. Rindal et al. [133] analyzed two key properties of the underlying linear codes (including large minimum distance) under the linear test framework to establish a degree of confidence about the hardness of the new dualLPN problem. More analyses on the new dualLPN problem are encouraged to establish more confidence on the security of their COT protocol. When applying the stateoftheart consistency check by Yang et al. [134] into the semihonest COT protocol [132] based on the new dualLPN assumption [133], we can obtain the currently most efficient COT protocol with malicious security. This consistency check along with the check technique by Boyle et al. [132] allows the malicious sender to guess some positions of nonzero entries of noise vector e in a selective failure manner, i.e., an incorrect guess will be caught. This means that the adversary is allowed to query (on average) onebit information on the noise vector. In this case, it is worth analyzing whether the current parameter selection of the underlying LPN assumptions has already been sufficient to achieve the κbit security level (e.g., κ = 128).
Recently, Boyle et al. [256] proposed the notion of pseudorandom correlation function (PCF), and gave an efficient PCF construction for generating COT correlations under a variabledensity variant of the LPN assumption (VDLPN). While PCG only allows to generate a fixed length of correlated randomness (e.g., COT) in an all at once way and does not support the stateful incremental evaluation enabled by PRG in a "streamcipher" mode, PCF can produce correlated randomness onthefly and offer the ability to securely generate virtually unbounded number of correlated randomness. In particular, PCF allows two parties to generate two short correlated keys k_{0} and k_{1} in the setup phase, and then use the keys to compute COT correlations onthefly, i.e., v_{i} = PCF(k_{0}, x_{i}) and (u_{i}, w_{i})=PCF(k_{1}, x_{i}) for a uniform string x_{i} such that w_{i} = v_{i} + Δ ⋅ u_{i} where Δ can be involved in key k_{0}. Boyle et al. [256] only presented the semihonest construction to distribute the short keys for computing COT correlations, which may have an efficiency advantage than the PCG approach when the number N of resulting COT correlations is very huge (e.g., N ≈ 2^{48} or even larger).
5.2. Oblivious linearfunction evaluation
OLE. Oblivious linearfunction evaluation (OLE) is an arithmetic generalization of OT, and is particularly useful for designing MPC protocols for arithmetic circuits over large fields [120, 146, 262–264]. In particular, OLE directly gives a twoparty additive sharing of the multiplication of two secret values. Therefore, by a pairwise OLE protocol execution, we can use OLE to generate Beaver multiplication triples without authentication in the multiparty setting. OLE can be constructed using OT extension and Gilboa multiplication approach [43, 150], and has a cheap computation cost but a much high communication cost. There exists a standard approach to design OLE using additively homomorphic encryption (AHE) based on RLWE, which has been used in Overdrive [152] and the recent work [265], where a receiver R sends Enc(x) to sender S, and then S computes Enc(y)=u ⋅ Enc(x)+v and sends it to R who decrypts to obtain y = u ⋅ x + v ∈ 𝔽 for a large field 𝔽. Here, the AHE needs to satisfy the circuit privacy property. In addition, OLE can also be constructed from somewhat homomorphic encryption [103, 149], but will require a larger communication. Without relying on homomorphic encryption, OLE is also able to be built directly from RingLWE [266, 267]. Besides, we can also construct OLE protocols from OT and noisy ReedSolomon encodings [97, 264, 268], or Paillier encryption [269]. Among all the OLE protocols, the protocols [152, 265] based on AHE obtain the best communication efficiency, and the protocol [266] from RLWE has the optimal one round of communication.
Recently, Boyle et al. [162] proposed an OLE construction based directly on LPN, which has very lower communication cost than the above OLE protocols but needs the computational cost of at least O(N^{2}) for generating N OLE correlations. Later, they [161] solved the computational problem using a variant of the ringLPN assumption, and constructed an OLE protocol for computing a large number of OLE correlations. This OLE protocol has very lower communication cost than the protocols based on RLWE, and provides a computational complexity of $\stackrel{~}{O}(N)$. Their PCG approach based on ringLPN is a nice approach to generate a large number of OLE correlations (e.g., N = 2^{20}). For a small number of OLE correlations, the approaches based on RLWE may be better. Based on ringLPN, the resulting OLE correlations are random (i.e., u, v, x ∈ 𝔽 are uniformly random), but are sufficient to design MPC protocols where only random multiplication triples need to be generated in the preprocessing phase.
VOLE. Vector oblivious linearfunction evaluation (VOLE) is an arithmetic generalization of COT to a large field and defined as follows:

A sender holds a uniform global key Δ ∈ 𝔽.

For each VOLE execution, the sender obtains a vector v ∈ 𝔽^{N}, and a receiver gets two vectors w, u ∈ 𝔽^{N}, such that w = v + Δ ⋅ u.
We have a standard transformation from COT to OT using CRHFs [130]. This is not the case for VOLE and OLE, as the underlying field 𝔽 is large and the sender cannot enumerate all possible values w.r.t. x ∈ 𝔽. Similar to OLE, VOLE can be built based on OT extension [43] or AHE [152, 265], where the latter has a lower communication. The VOLE protocols [152, 265] based on AHE have the communication complexity linear to the output length of VOLE. Based on the LPN assumption, the PCG approach [254] can construct VOLE protocols with sublinear communication, and is the most promising approach to produce a large number of VOLE correlations (e.g., N ≥ 10^{5}). Subsequently, this approach was further optimized in [69, 132–134, 162, 256, 260]. The efficiency and security comparisons among these VOLE protocols based on LPN is similar to the COT case shown in the previous subsection.
The stateoftheart VOLE protocols [69, 133] adopt the same framework as the bestknown COT protocols [133, 134] based on dualLPN or primalLPN, except that an additional VOLE correlation needs to be generated in a singlepoint VOLE protocol execution as the single nonzero element is uniform in large field 𝔽 rather than equal to 1. Additionally, for VOLE, we need to use the LPN assumption over a large field 𝔽 instead of 𝔽_{2}. We are able to use the VOLE protocols [152, 265] based on AHE to generate the VOLE correlations in the setup phase. Besides, we can use the PCF approach to generate VOLE correlations under the VDLPN assumption [256], and may have an efficiency advantage than the PCG approach if the number of resulting VOLE correlations is very huge. Similar to the case of COT, we can use the stateoftheart consistency check [69, 134] to construct maliciously secure VOLE protocols.
6. MPC application to machine learning
Recent advances in machine learning (ML) have driven a lot of reallife applications, such as healthcare, financial risk analysis, facial recognition, image and video analysis for selfdriving cars, recommendation systems, text translation, voice assistants, image classification, etc. The level of accuracy as required is high for missioncritical applications (e.g., healthcare). Accuracy is mainly governed by two factors: 1) the large amount of computing power that is demanded to train deep learning models; 2) the variance in datasets, which comes from collecting data from multiple diverse sources and is generally infeasible for a single company to achieve.
Toward this, multiple companies (e.g., Microsoft, Amazon, Google) provide with machine learning as a service (MLaaS), which works in the following two different ways:

Inference: A company offers a trained ML model, and a customer is able to query a feature input to obtain the inference result.

Training: Multiple companies work together to train a high accuracy model using their datasets.
In the first scenario, companies want to keep the ML model secret as it may take a lot of money to train a model, and customers wish to protect the privacy of their inputs where the input information may be sensitive such as personal health data or faces. In the second scenario, companies would not be willing to share their data since data are proprietary information of a company and these companies may be competitive, and are prohibited from sharing client information due to privacy laws. Here, we say that an ML model is kept secret, meaning that the model parameters are hidden, but the model structure (e.g., which functions are used) is still known. It is a challenge to protect the privacy of model structure while keeping PPML concretely efficient.
Therefore, to address the above privacy concerns in ML applications, privacypreserving machine learning (PPML) is highly desirable, and has emerged as a flourishing research area. In particular, PPML allows ML computations over private data, while ensuring the privacy of the data. Due to the privacyprotection requirement, PPML makes the already computeintensive ML algorithms more demanding in terms of high computation power and large communication cost. However, many everyday users have no such computation and communication capacities to execute PPML. Thus, it may be economical and convenient for users to securely outsource an ML task to a set of powerful and specialized cloud servers in a payperuse manner, where the security is guaranteed if at most t servers of n servers collude to cheat (either t < n or t < n/2 depending on the concrete MPC protocols used). In this case, the inference and training can be realized in the following way:

Outsourcing inference: A company may host its trained ML model in a secretshared way to n (untrusted) servers. A customer can secretly share its feature input among the same n servers. The servers can compute an inference result in a shared fashion and return the result to the customer.

Outsourcing training: Multiple companies can secretly share their datasets to a set of (untrusted) servers, who cooperatively train a common model on their joint datasets while keeping their individual dataset private.
MPC is one of key techniques to realize PPML, and is the most promising approach to perform PPML in the above outsourced computation setting based on secret sharings. A series of PPML protocols have been built upon MPC techniques. We can partition these PPML protocols into two categories: one is in the dishonestmajority setting, and the other is in the honestmajority setting. We surveyed the known PPML protocols based on MPC, and compare them in Table 3. All PPML protocols shown in Table 3 along with other PPML protocols [30, 34, 270–276] are customized in the following ways:

Based on the known MPC protocols, improve the ML algorithms to make them more MPCfriendly.

According to the definitions of ML algorithms, tailor the known MPC protocols.
These customized PPML protocols can obtain high efficiency for specific learning tasks. Recently, Zheng et al. [35] designed a platform for privacypreserving training and inference of generic ML tasks, which supports new neuralnetwork architectures but has a lower efficiency.
Comparison of various PPML protocols
In the dishonestmajority setting, the PPML protocols focus on the twoparty case, except for two protocols Helen [36] and Cerebro [35]. Both Helen and Cerebro implemented the inference and training of ML algorithms among 4 parties and 2–12 parties, respectively, and allow the adversary to be semihonest or malicious. For 12 parties tolerating 11 semihonest corruptions, the recent PPML protocol Cerebro [35] can perform an inference of the decision tree with 12 layers in average time about 20 s. In the semihonest setting with six parties, Cerebro can implement the logistic regression training in about 16 minutes, and the linear regression training in about 100 s. According to the experimental results in Cerebro [35], the maliciously secure PPML protocol is 61–3300× slower than the semihonest version. In the multiparty setting with dishonest majority, the model for ML inference is small, and the dataset and neuralnetwork architecture for ML training is also small. More efficiency optimizations need to be exploited to support larger datasets and models. The maliciously secure protocols need to be further improved to reduce the overhead over the semihonest protocols. Now, we turn our attention to the twoparty case. Most of the twoparty PPML protocols consider the semihonest adversaries. The only exception is QuantizedNN [283], which uses SPDℤ_{2k} [157, 158] and Overdrive [152] to design maliciously secure protocols, where SPDℤ_{2k} and Overdrive have been implemented in the MPSPDZ library [17]. Their maliciously secure protocol [283] is roughly 3–9× slower than the semihonest protocol. In the semihonest twoparty setting, most of PPML protocols focus on ML inference except for SecureML [24] and QUOTIENT [18]. Nevertheless, SecureML and QUOTIENT only implemented the small dataset MNIST that has 60,000 training samples and 10 different classes. For twoparty ML inference with semihonest security, the stateoftheart PPML protocol CrypTFlow2 [28] is able to perform private inference over complex deep neural networks (DNNs) like ResNet50 (50 layers, 23.5 million parameters) and DenseNet121 (121 layers, 8.5 million parameters), which can be trained over a largescale dataset ImageNet that contains more than 1,000,000 training samples and 1000 different classes. Their implementation [28] needs about 546 s and 32 GB of communication for ResNet50, and 463 s and 35 GB of communication for DenseNet121. In the twoparty setting, it seems to have been highly efficient for ML inference with semihonest security, but the ML inference against malicious adversaries and the ML training still have a low efficiency, which needs to be addressed in the future work.
In the honestmajority setting, the known PPML protocols only consider the threeparty and fourparty cases tolerate one corruption. In this setting, we can achieve a relatively high efficiency for private inference and training. By accelerating semihonest 3PC with GPU, CryptGPU [31] can perform one private inference over the ImageNetscale ResNet50 (resp., ResNet152) using 9.3 s and 3.1 GB of communication (resp., 25.8 s and 6.6 GB of communication). The private training implemented by CryptGPU is able to support VGG16 (16 layers, 138 million parameters), which is trained over a Tiny ImageNet dataset that contains 100,000 training samples and more than 200 different classes. Their implementation reports the running time and communication for a single iteration of private training, which are 13.9 s and 7.6 GB respectively. For malicious security, the bestknown PPML protocol Falcon [292] can run a private inference over a neuralnetwork VGG16 trained with Tiny ImageNet using 12.1 s of running time and 0.4 GB of communication. However, Falcon with malicious security takes over 3 years and about 1012 TB of communication to train a VGG16 model over the Tiny ImageNet dataset. When a majority of parties are honest, multiple PPML protocols can also achieve stronger security property than security with abort (i.e., fairness and GOD) using a small overhead. In this case, the PPML protocols in the fourparty setting have a better performance than those in the threeparty setting, but require a stronger assumption about the number of honest parties. Among these PPML protocols achieving fairness or GOD, Tetrad [294] has the best efficiency for now. Particularly, Tetrad takes 183 s and 35 GB of communication to train a VGG16 model over a small dataset CIFAR10 that includes 50,000 training samples and 10 different classes. Overall, in the threeparty/fourparty setting, private inference has been practical and can scale to complex models and large datasets, even in the presence of malicious adversaries. In the same setting, private training provides a high efficiency and supports a moderatesized dataset for semihonest security, but has a very low efficiency for malicious security. Besides, it will be an interesting future work to design honestmajority PPML protocols with at least five parties and two corrupted parties.
For ML applications, we need to handle multiple differenttype functions. For example, in DNNs, we need to compute Matrix Multiplication, Convolution etc., for linear layers, and ReLU, Max Pooling, Sigmoid, SoftMax etc., for nonlinear layers. Therefore, we need to construct mixedmode MPC protocols, which support both arithmetic circuits and Boolean circuits and allow to convert between arithmetic and Boolean circuits. Additionally, for division operations or a function represented as a circuit that has a large depth, we may need to use the garbled circuit approach to achieve better efficiency. In the dishonestmajority setting, the ABYlike protocols [7, 25] developed the techniques to realize the conversion among arithmetic sharing, Boolean sharing and Yao’s GCs in the presence of semihonest adversaries. The ABYlike protocols focus on the case that the circuit evaluation is executed between two parties. In the multiparty setting, the recent work [295] proposes the semihonest protocols to support arithmetic sharing, Boolean sharing, Yao’s GCs, and conversions between any two represents. However, their protocols need a trusted party to distribute all correlated randomness among the parties evaluating the circuits, which makes the protocols have a weaker security guarantee. For malicious security, the conversion between distributed garbled circuits and SPDZstyle authenticated sharings can be realized using the doubly authenticated bits (daBits) technique [158, 296–298] or the more efficient extended daBits (edaBits) technique [299]. Specifically, a daBit consists of a pair of random sharings ([r]_{2}, [r]_{M}), where $r\in {\{0,1\}}^{}$ and either M = p for a prime p or M = 2^{k}. The daBits technique was first presented by Rotaru and Wood [298] for the case of M = p. Then, the performance was further improved for the case of M = p in [296, 297, 299], and daBits over a ring ℤ_{2k} were also shown in [158, 299], where the known implementation [296] takes about 11.8 KB for generating one daBit with a large prime p and can generate about 2150 daBits per second in the twoparty malicious setting. The stateoftheart edaBits protocol [299] adopts the “CutandBucketing” technique to check the consistency of values in two different domains, where an edaBit consists of a set of random sharings ([r_{m − 1}]_{2}, …, [r_{0}]_{2}) in the binary domain and a sharing [r]_{M} in the arithmetic domain, such that r = ∑_{i ∈ [0, m)}r_{i} ⋅ 2^{i}modM. In the twoparty malicious setting, the edaBits approach will reduce the communication cost by a factor of 2× for implementing comparison of 63bit integers, compared to the daBits technique [299]. The “CutandBucketing” technique for malicious security leads to at least a factor of 3 overhead over the semihonest protocol. It is an interesting open problem to construct a concretely efficient edaBits protocol with malicious security, which achieves an overhead of 2 or even smaller. In the honestmajority setting, the protocols against malicious adversaries, which allow to convert between the arithmetic, Boolean, and garbling worlds, can be constructed more efficiently [19, 294], where the techniques underlying the constantround MPC protocols (e.g., [236, 239]) can be used and adapted.
On the other hand, the recent studies by Boyle et al. [300, 301] proposed a new approach to construct mixedmode MPC protocols based on function secret sharing (FSS), which is useful for ML applications with optimal online communication and round complexity. Their FSS approach supports arithmetic operations that are mixed with nonarithmetic operations. In particular, for a nonarithmetic function g such as ReLU, two parties can obtain two succinct FSS keys to evaluate function g_{r}(x)=g(x + r) where r is a randomness shared by the parties. In general, the FSSbased approach requires more communication in the preprocessing phase than the GC or GMW approach, unless the FSS keys are distributed by a trusted dealer, or the input length is relatively small. This naturally leaves a future work to reduce the preprocessing cost for distributing the FSS keys by a concretely efficient 2PC protocol. For online communication cost and rounds, the FSSbased approach outperforms the GC and GMW approaches. Their FSSbased approach can be also secure against malicious adversaries [300]. For now, Boyle et al. [300, 301] only proposed efficient constructions for functions including comparison (e.g., ReLU), splines (e.g., used in sigmoid), bitdecomposition, zero test, and arithmetic/logical shifts. There are still many functions used in ML and scientific computation (e.g., exponentiation, tanh, and reciprocal of square root), whose concretely efficient FSSbased 2PC protocols are unknown. Besides, Boyle et al. [300, 301] only gave twoparty constructions. It is an interesting future work to construct concretely efficient FSSbased MPC protocols with optimal online communication and rounds for multiple parties (i.e., n ≥ 3). While prior work uses a uniform bitwidth for the whole ML inference, the recent work by Rathee et al. [27] proposed the mixed bitwidths approach, i.e., operating in low bitwidths and going to high bitwidths only when necessary. They designed new protocols to switch between bitwidths and operations on values of differing bitwidths. Their approach is interesting and able to obtain better efficiency. While the work [27] only considers private ML inference in the twoparty setting, it is worth further developing the mixed bitwidths approach to private ML training and the multiparty setting.
7. Conclusion and future work
We have described the (recent) development of concretely efficient MPC protocols along with the key techniques underlying these MPC protocols. Particularly, we present the highlevel ideas in the recent MPC protocols and OT/OLE protocols. As an example of MPC applications, we discuss privacypreserving machine learning, and summarize related work as well as conversion and FSSbased techniques. It is desired that this survey will help new researchers (who are interesting for MPC) understand the recent development of concretely efficient MPC rapidly, and to preliminarily understand some key techniques as a starting point of MPC study.
To deploy MPC on a large scale, standardization is a necessary step. Nevertheless, this is not an easy task, as there exists many different kinds of MPC protocols that have different advantages in terms of security and efficiency. Besides, there are many techniques and different assumptions that are used in the design of MPC. These make the MPC standardization procedure becomes hard. Of course, we can first standardize a batch of MPC protocols in the same setting, and then standardize the next batch in the other setting. When standardization is a longtime procedure and needs to take a large amount of financial resources, this approach is very expensive. Furthermore, how to keep compatibility of multiple MPC protocols in different standardization procedures is a problem. All of these need to be addressed and solved in the future work. Recently, ISO is preparing the standardization process for MPC based on secret sharing [302]. Besides, NIST will standardize multiparty threshold cryptography in the future [303], where MPC is a key technique to realize AES encryption/decryption, EdDSA signing, the distributed keygeneration of RSA, etc. NIST also intends to accompany the progress of emerging technologies in the area of privacy enhancing cryptography [304], which includes MPC, ZK, HE, etc.
We have summarized some open problems and future work in the previous sections. In the following, we conclude this work by further listing several open problems and future work for concretely efficient MPC protocols.

Constantround 2PC: The recent breakthrough work by Rosulek and Roy [199] reduced the size of garbled circuits from 2κ bits per AND gate to 3κ/2 + 5 bits per AND gate. A natural open problem is whether one can do better, e.g., about 4κ/3 bits per AND gate while keeping compatibility with freeXOR and high computational efficiency. If this seems to be impossible, one can attempt to prove that ≈3κ/2 bits per AND gate is optimal in a more inclusive model than the linear garbling model in [195]. When the work [199] focuses on the semihonest adversary, another open problem is to extend the slicinganddicing technique in [199] to twoparty distributed garbling that can be used to design maliciously secure 2PC protocols by combining with BDOZstyle ITMACs.

Constantround MPC: We conclude three future work for designing constantround MPC.

(a)
Dishonest majority for garbling: For multiparty distributed garbling based on only symmetric primitives, the stateoftheart technique by Yang et al. [110] achieves (4n − 6)𝒞κ bits in terms of the size of a garbled circuit. It is a challenging task to further reduce it to about 2n𝒞κ bits based on still symmetric primitives. In other words, is it possible to totally apply the halfgate technique to multiparty distributed garbling?

(b)
Dishonest majority for AND triples: Currently, we use a TinyOTlike protocol to generate authenticated AND triples, which requires an overhead of at least 3 to achieve malicious security over the corresponding semihonest protocol, where the overhead is from the usage of the bucketing technique. It is an interesting open problem that designs an authenticatedANDtriple protocol achieving an overhead of 2 (or even smaller) using a novel technique.

(c)
Honest majority: If the number of parties n > 5, Chandran et al. [237] presented a constantround MPC protocol with corruption threshold $t\le \sqrt{n}$. It is an interesting future work that constructing a constantround concreteefficient MPC protocol tolerating t < n/2 corrupted parties when n > 5.

(a)

SPDZ: The efficiency bottleneck for SPDZstyle protocols is to generate authenticated triples over a large field. The stateoftheart protocol [161] based on a variant of the ringLPN assumption obtains a relatively low communication complexity, which is two orders of magnitude smaller than Overdrive [152]. However, this protocol has a computation complexity of O(NlogN) for encoding (while fast Fourier transform (FFT) is used) which is large for large N, where N is the number of resulting authenticated triples. An important future work is to reduce the computation complexity while keeping small communication complexity for the ringLPNbased protocol.

LPN variants for MPC: COT and OLE as well as their variants are key building blocks for MPC in the dishonestmajority setting. To design the COT and (V)OLE protocols with low communication, several LPN variants have already been proposed, including LPN with a regular noise distribution [114, 132], LPN with static leakage [132], ringLPN with reducible polynomials and a regular noise distribution [161]. An important future work is to further analyze the LPN variants proposed in the MPC context, which allows to establish more confidence on the hardness of these LPN problems.

Largescale MPC with honest majority: For honestmajority MPC in the malicious setting, several recent work [178, 179, 184] designed largescale MPC protocols, which scales practically to hundreds of thousands of parties. However, their concrete efficiency is still not high. Constructing largescale maliciously secure MPC protocols with higher concrete efficiency as well as giving an efficient implementation scaling to thousands of parties will be an interesting future work.
Conflict of interest
The authors declare that they have no conflict of interest.
Data Availability
No data are associated with this article.
Authors’ Contributions
Dengguo Feng mainly surveyed the MPC protocols based on linear secret sharing schemes and the privacypreserving machine learning protocols building upon MPC techniques. Kang Yang mainly surveyed constantround MPC protocols and the oblivious transfer and oblivious linearfunction evaluation protocols. The authors discussed the recent development and future work of MPC, and then jointly wrote this paper.
Acknowledgments
We thank the anonymous reviewers for their helpful comments.
Funding
This work was supported in part by the National Key Research and Development Program of China (Grant No. 2018YFB0804105), and in part by the National Natural Science Foundation of China (Grant Nos. 62102037, 61932019).
We note that OTs with random choice bits can be transformed into OTs with chosen choice bits at the cost of additionally communicating 1 bit per OT, using the precomputing OT technique [188].
Concurrently, Schoppmann et al. [260] used the same approach to design an arithmetic variant of SPCOT.
References
 Beaver D, Micali S and Rogaway P. The round complexity of secure protocols (extended abstract). In: 22nd ACM STOC. ACM Press, 1990, 503–13. [Google Scholar]
 BenOr M, Goldwasser S and Wigderson A. Completeness theorems for noncryptographic faulttolerant distributed computation (extended abstract). In: 20th ACM STOC. ACM Press, 1988, 1–10. [Google Scholar]
 Chaum D, Crépeau C and Damgård I. Multiparty unconditionally secure protocols (extended abstract). In: 20th ACM STOC. ACM Press, 1988, 11–19. [Google Scholar]
 Goldreich O, Micali S and Wigderson A. How to play any mental game or A completeness theorem for protocols with honest majority. In: Aho A (ed.). 19th ACM STOC. ACM Press, 1987, 218–29. [Google Scholar]
 Rabin T and BenOr M. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: 21st ACM STOC. ACM Press, 1989, 73–85. [Google Scholar]
 Yao ACC. How to generate and exchange secrets (extended abstract). In: 27th FOCS. IEEE Computer Society Press, 1986, 162–7. [Google Scholar]
 Demmler D, Schneider T and Zohner M. ABY  A framework for efficient mixedprotocol secure twoparty computation. In: NDSS 2015. The Internet Society, 2015. [Google Scholar]
 Wang X, Malozemoff AJ and Katz J. EMPtoolkit: Efficient MultiParty Computation Toolkit. https://github.com/emptoolkit, 2016. [Google Scholar]
 Alexandra Institute. FRESCO  A FRamework for Efficient Secure COmputation. https://github.com/aicis/fresco. [Google Scholar]
 Multiparty.org Development Team. Javascript Implementation of Federated Functionalities, 2020. https://github.com/multiparty/jiff. [Google Scholar]
 Data61. Mpspdz. https://github.com/data61/MPSPDZ, 2019. [Google Scholar]
 Schoenmakers B. MPyC: Secure Multiparty Computation in Python https://github.com/lschoe/mpyc. [Google Scholar]
 Aly A, Keller M and Orsini E et al. SCALEMAMBA v1.14: Documentation, 2021. https://github.com/KULeuvenCOSIC/SCALEMAMBA. [Google Scholar]
 Bogdanov D, Laur S and Willemson J. Sharemind: A framework for fast privacypreserving computations. In: Jajodia S and López J (eds.). ESORICS 2008, volume 5283 of LNCS. Heidelberg: Springer, 2008, 192–206. [Google Scholar]
 Songhori EM, Hussain SU and Sadeghi AR et al. TinyGarble: highly compressed and scalable sequential garbled circuits. In: 2015 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2015, 411–28. [CrossRef] [Google Scholar]
 Hastings M, Hemenway B and Noble D et al. SoK: General purpose compilers for secure multiparty computation. In: 2019 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2019, 1220–37. [Google Scholar]
 Keller M. MPSPDZ: A versatile framework for multiparty computation. In: Ligatti J, Ou X, Katz J and Vigna G (eds.). ACM CCS 20. ACM Press, 2020, 1575–90. [CrossRef] [Google Scholar]
 Agrawal N, Shahin Shamsabadi A and Kusner MJ et al. QUOTIENT: Twoparty secure neural network training and prediction. In: Cavallaro L, Kinder J, Wang X, Katz J (eds.). ACM CCS 2019. ACM Press, 2019, 1231–47. [Google Scholar]
 Chaudhari H, Rachuri R and Suresh A. Trident: Efficient 4PC framework for privacy preserving machine learning. In: NDSS 2020. The Internet Society, 2020. [Google Scholar]
 Juvekar C, Vaikuntanathan V and Chandrakasan A. GAZELLE: A low latency framework for secure neural network inference. In: Enck W and Felt AP (eds.). USENIX Security 2018. USENIX Association, 2018, 1651–69. [Google Scholar]
 Kumar N, Rathee M and Chandran N et al. CrypTFlow: secure TensorFlow inference. In: 2020 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2020, 336–53. [CrossRef] [Google Scholar]
 Mishra P, Lehmkuhl R and Srinivasan A et al. Delphi: A cryptographic inference service for neural networks. In: Capkun S and Roesner F (eds.). USENIX Security 2020. USENIX Association, 2020, 2505–22. [Google Scholar]
 Mohassel P and Rindal P. ABY^{3}: A mixed protocol framework for machine learning. In: Lie D, Mannan M, Backes M and Wang XF (eds.). ACM CCS 2018. ACM Press, 2018, 35–52. [Google Scholar]
 Mohassel P and Zhang Y. SecureML: A system for scalable privacypreserving machine learning. In: 2017 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2017, 19–38. [CrossRef] [Google Scholar]
 Patra A, Schneider T and Suresh A et al. ABY2.0: Improved Mixedprotocol Secure Twoparty Computation. Cryptology ePrint Archive, Report 2020/1225, 2020. https://eprint.iacr.org/2020/1225. [Google Scholar]
 Patra A and Suresh A. BLAZE: Blazing fast privacypreserving machine learning. In: NDSS 2020. The Internet Society, 2020. [Google Scholar]
 Rathee D, Rathee M and Goli RKK et al. SIRNN: A Math Library for Secure RNN Inference. Cryptology ePrint Archive, Report 2021/459, 2021. https://eprint.iacr.org/2021/459. [Google Scholar]
 Rathee D, Rathee M and Kumar N et al. CrypTFlow2: practical 2party secure inference. In: Ligatti J, Ou X, Katz J and Vigna G (eds.). ACM CCS 20. ACM Press, 2020, 325–42. [CrossRef] [Google Scholar]
 Riazi M S, Samragh M and Chen H et al. XONN: XNORbased oblivious deep neural network inference. In: Heninger N and Traynor P (eds.). USENIX Security 2019. USENIX Association, 2019, 1501–18. [Google Scholar]
 Schoppmann P, Gascón A and Raykova M et al. Make some ROOM for the zeros: data sparsity in secure distributed machine learning. In: Cavallaro L, Kinder J, Wang XF and Katz J (eds.). ACM CCS 2019. ACM Press, 2019, 1335–50. [Google Scholar]
 Tan S, Knott B and Tian Y et al. CryptGPU: fast privacypreserving machine learning on the GPU. In: IEEE Symposium on Security and Privacy, 2021. [Google Scholar]
 Brunetta C, Tsaloli G and Liang B et al. Noninteractive, secure verifiable aggregation for decentralized, privacypreserving learning. Cryptology ePrint Archive, Report 2021/654, 2021. https://eprint.iacr.org/2021/654. [Google Scholar]
 Fereidooni H, Marchal S and Miettinen M et al. SAFELearn: Secure Aggregation for private FEderated Learning. Cryptology ePrint Archive, Report 2021/386, 2021. https://eprint.iacr.org/2021/386. [Google Scholar]
 Han K, Jeong J and Sohn JH et al. Efficient privacy preserving logistic regression inference and training. Cryptology ePrint Archive, Report 2020/1396, 2020. https://eprint.iacr.org/2020/1396. [Google Scholar]
 Zheng W, Deng R and Chen W et al. Cerebro: A Platform for Multiparty Cryptographic Collaborative Learning. Cryptology ePrint Archive, Report 2021/759, 2021. https://eprint.iacr.org/2021/759. [Google Scholar]
 Zheng Q, Popa RA and Gonzalez JE et al. Helen: maliciously secure coopetitive learning for linear models. In: 2019 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2019, 724–38. [CrossRef] [Google Scholar]
 Bogdanov D, Niitsoo M and Toft T et al. Highperformance secure multiparty computation for data mining applications. Int J Inf Secur 2012; 11: 403–18. [CrossRef] [Google Scholar]
 Burkhart M, Strasser M and Many D et al. SEPIA: Privacypreserving aggregation of multidomain network events and statistics. In: USENIX Security 2010. USENIX Association, 2010, 223–40. [Google Scholar]
 Cramer R, Damgård IB and Nielsen JB. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015. [CrossRef] [Google Scholar]
 Lindell Y and Pinkas B. Privacy preserving data mining. J Cryptol 2002; 15: 177–206. [Google Scholar]
 BenDavid A, Nisan N and Pinkas B. FairplayMP: A system for secure multiparty computation. In: Ning P, Syverson PF and Jha S (eds.). ACM CCS 2008. ACM Press, 2008, 257–66. [Google Scholar]
 Bogetoft P, Christensen DL and Damgård I et al. Secure multiparty computation goes live. In: Dingledine R and Golle P (eds.). FC 2009, volume 5628 of LNCS. Heidelberg: Springer, 2009, 325–43. [Google Scholar]
 Keller M, Orsini E and Scholl P. MASCOT: Faster malicious arithmetic secure computation with oblivious transfer. In: Weippl ER, Katzenbeisser S, Kruegel C, Myers AC and Halevi S (eds.). ACM CCS 2016. ACM Press, 2016, 830–42. [Google Scholar]
 Cho H, Wu DJ and Berger B. Secure genomewide association analysis using multiparty computation. Nat Biotechnol 2018; 36: 547–51. [CrossRef] [PubMed] [Google Scholar]
 Jagadeesh KA, Wu DJ and Birgmeier JA et al. Deriving genomic diagnoses without revealing patient genomes. Science 2017; 357: 692–5. [CrossRef] [PubMed] [Google Scholar]
 Jha S, Kruger L and Shmatikov V. Towards practical privacy for genomic computation. In: 2008 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2008, 216–30. [CrossRef] [Google Scholar]
 Archer DW, Bogdanov D and Lindell Y et al. From keys to databases  realworld applications of secure multiparty computation. Comput J 2018; 61: 1749–71. [Google Scholar]
 Almashaqbeh G and Solomon R. Sok: Privacypreserving computing in the blockchain era. Cryptology ePrint Archive, Report 2021/727, 2021. https://eprint.iacr.org/2021/727. [Google Scholar]
 Atapoor S, Smart NP and Alaoui YT. Private liquidity matching using MPC. Cryptology ePrint Archive, Report 2021/475, 2021. https://eprint.iacr.org/2021/475. [Google Scholar]
 Banerjee A, Clear M and Tewari H. zkhawk: Practical private smart contracts from MPCbased hawk. Cryptology ePrint Archive, Report 2021/501, 2021. https://eprint.iacr.org/2021/501. [Google Scholar]
 Dolev S and Wang Z. Sodsmpc: FSM based anonymous and private quantumsafe smart contracts. Cryptology ePrint Archive, Report 2020/1346, 2020. https://eprint.iacr.org/2020/1346. [Google Scholar]
 El Defrawy K and Lampkins J. Founding digital currency on secure computation. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS’14. Association for Computing Machinery, 2014, 1–14. [Google Scholar]
 Green M and Miers I. Bolt: Anonymous payment channels for decentralized currencies. In: Thuraisingham BM, Evans D, Malkin T and Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 473–89. [Google Scholar]
 Ames S, Hazay C and Ishai Y et al. Ligero: Lightweight sublinear arguments without a trusted setup. In: Thuraisingham BM, Evans D, Malkin T and Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 2087–2104. [Google Scholar]
 Bhadauria R, Fang Z and Hazay C et al. Ligero++: A new optimized sublinear IOP. In: Ligatti J, Ou X, Katz J and Vigna G (eds.). ACM CCS 20. ACM Press, 2020, 2025–38. [CrossRef] [Google Scholar]
 Chase M, Derler D and Goldfeder S et al. Postquantum zeroknowledge and signatures from symmetrickey primitives. In: Thuraisingham BM, Evans D, Malkin T and Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 1825–1842. [Google Scholar]
 De Saint Guilhem CD, Orsini E and Tanguy T. Limbo: Efficient zeroknowledge mpcithbased arguments. Cryptology ePrint Archive, Report 2021/215, 2021. https://ia.cr/2021/215. [Google Scholar]
 Giacomelli I, Madsen J and Orlandi C. ZKBoo: Faster zeroknowledge for Boolean circuits. In: Holz T and Savage S (eds.). USENIX Security 2016. USENIX Association, 2016, 1069–83. [Google Scholar]
 Gvili Y, Scheffler S and Varia M. Booligero: Improved sublinear zero knowledge proofs for Boolean circuits. Cryptology ePrint Archive, Report 2021/121, 2021. https://eprint.iacr.org/2021/121. [Google Scholar]
 Ishai Y, Kushilevitz E and Ostrovsky R et al. Zeroknowledge from secure multiparty computation. In: Johnson DS and Feige U (eds.). 39th ACM STOC. ACM Press, 2007, 21–30. [Google Scholar]
 Katz J, Kolesnikov V and Wang X. Improved noninteractive zero knowledge with applications to postquantum signatures. In: Lie D, Mannan M, Backes M and Wang XF (eds.). ACM CCS 2018. ACM Press, 2018, 525–37. [Google Scholar]
 Baum C, Braun L and MunchHansen A et al. Appenzeller to brie: Efficient zeroknowledge proofs for mixedmode arithmetic and . Cryptology ePrint Archive, Report 2021/750, 2021. https://eprint.iacr.org/2021/750. [Google Scholar]
 Baum C, Malozemoff AJ and Rosen M et al. Mac’n’cheese: Zeroknowledge proofs for arithmetic circuits with nested disjunctions. Cryptology ePrint Archive, Report 2020/1410, 2020. https://eprint.iacr.org/2020/1410. [Google Scholar]
 Dittmer S, Ishai Y and Ostrovsky R. Linepoint zero knowledge and its applications. Cryptology ePrint Archive, Report 2020/1446, 2020. https://eprint.iacr.org/2020/1446. [Google Scholar]
 Frederiksen TK, Nielsen JB and Orlandi C. Privacyfree garbled circuits with applications to efficient zeroknowledge. In: Oswald E and Fischlin M (eds.). EUROCRYPT 2015, Part II, volume 9057 of LNCS. Heidelberg: Springer, 2015, 191–219. [Google Scholar]
 Heath D and Kolesnikov V. Stacked garbling for disjunctive zeroknowledge proofs. In: Canteaut A and Ishai Y (eds.). EUROCRYPT 2020, Part III, volume 12107 of LNCS. Heidelberg: Springer, 2020, 569–98. [Google Scholar]
 Jawurek M, Kerschbaum F and Orlandi C. Zeroknowledge using garbled circuits: how to prove nonalgebraic statements efficiently. In: Sadeghi AR, Gligor VD and Yung M (eds.). ACM CCS 2013. ACM Press, 2013, 955–66. [Google Scholar]
 Kondi Y and Patra A. Privacyfree garbled circuits for formulas: size zero and informationtheoretic. In: Katz J and Shacham H (eds.). CRYPTO 2017, Part I, volume 10401 of LNCS. Heidelberg: Springer, 2017, 188–222. [CrossRef] [Google Scholar]
 Weng C, Yang K, Katz J and Wang X. Wolverine: Fast, Scalable, and Communicationefficient Zeroknowledge Proofs for Boolean and Arithmetic Circuits. IEEE Computer Society Press, 2021. [Google Scholar]
 Weng C, Yang K and Xie X et al. Mystique: Efficient Conversions for Zeroknowledge Proofs with Applications to Machine Learning. Cryptology ePrint Archive, Report 2021/730, 2021. https://eprint.iacr.org/2021/730. [Google Scholar]
 Yang K, Sarkar P and Weng C et al. Quicksilver: Efficient and Affordable Zeroknowledge Proofs for Circuits and Polynomials Over Any Field. Cryptology ePrint Archive, Report 2021/076, 2021. https://eprint.iacr.org/2021/076. [Google Scholar]
 Canetti R, Gennaro R and Goldfeder S et al. UC noninteractive, proactive, threshold ECDSA with identifiable aborts. In: Ligatti J, Ou X, Katz J and Vigna G (eds.). ACM CCS 20. ACM Press, 2020, 1769–87. [CrossRef] [Google Scholar]
 Chen M, Cohen R and Doerner J et al. Multiparty generation of an RSA modulus. In: Micciancio D and Ristenpart T (eds.). CRYPTO 2020, Part III, volume 12172 of LNCS. Heidelberg: Springer, 2020, 64–93. [Google Scholar]
 Chen M, Hazay C and Ishai Y et al. Diogenes: Lightweight scalable RSA modulus generation with a dishonest majority. Cryptology ePrint Archive, Report 2020/374, 2020. https://eprint.iacr.org/2020/374. [Google Scholar]
 Doerner J, Kondi Y and Lee E et al. Secure twoparty threshold ECDSA from ECDSA assumptions. In: 2018 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2018, 980–997. [CrossRef] [Google Scholar]
 Doerner J, Kondi Y and Lee E et al. Threshold ECDSA from ECDSA assumptions: The multiparty case. In: 2019 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2019, 1051–66. [Google Scholar]
 Frederiksen TK, Lindell Y and Osheter V et al. Fast distributed RSA key generation for semihonest and malicious adversaries. In: Shacham H and Boldyreva A (eds.). CRYPTO 2018, Part II, volume 10992 of LNCS. Heidelberg: Springer, 2018, 331–61. [Google Scholar]
 Hazay C, Mikkelsen G and Rabin T et al. Efficient RSA key generation and threshold paillier in the twoparty setting. J Cryptol 2019; 32: 265–323. [CrossRef] [Google Scholar]
 Lindell Y and Nof A. Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody. In: Lie D, Mannan M, Backes M and Wang XF (eds.). ACM CCS 2018. ACM Press, 2018, 1837–54. [Google Scholar]
 Garimella G, Pinkas B and Rosulek M et al. Oblivious keyvalue stores and amplification for private set intersection. In: Malkin T and Peikert C (eds.). Advances in Cryptology  CRYPTO 2021, volume 12826 of LNCS. Springer International Publishing, 2021, 395–425. [CrossRef] [Google Scholar]
 Pinkas B, Rosulek M and Trieu N et al. SpOTlight: lightweight private set intersection from sparse OT extension. In: Boldyreva A and Micciancio D (eds.). CRYPTO 2019, Part III, volume 11694 of LNCS. Heidelberg: Springer, 2019, 401–31. [CrossRef] [Google Scholar]
 Pinkas B, Rosulek M and Trieu N et al. PSI from PaXoS: fast, malicious private set intersection. In: Canteaut A and Ishai Y (eds.). EUROCRYPT 2020, Part II, volume 12106 of LNCS. Heidelberg: Springer, 2020, 739–67. [CrossRef] [Google Scholar]
 Pinkas B, Schneider T and Tkachenko O et al. Efficient circuitbased PSI with linear communication. In: Ishai Y and Rijmen V (eds.). EUROCRYPT 2019, Part III, volume 11478 of LNCS. Heidelberg: Springer, 2019, 122–53. [Google Scholar]
 Pinkas B, Schneider T and Weinert C et al. Efficient circuitbased PSI via cuckoo hashing. In: Nielsen JB and Rijmen V (eds.). EUROCRYPT 2018, Part III, volume 10822 of LNCS. Heidelberg: Springer, 2018, 125–57. [CrossRef] [Google Scholar]
 Rindal P and Schoppmann P. VOLEPSI: fast OPRF and CircuitPSI from VectorOLE. In: Canteaut A and Standaert FX (eds.). Advances in Cryptology  EUROCRYPT 2021, volume 12697 of LNCS. Springer International Publishing, 2021, 901–30. [CrossRef] [Google Scholar]
 Cleve R. Limits on the security of coin flips when half the processors are faulty (extended abstract). In: 18th ACM STOC. ACM Press, 1986, 364–69. [Google Scholar]
 Araki T, Furukawa J and Lindell Y et al. Highthroughput semihonest secure threeparty computation with an honest majority. In: Weippl ER, Katzenbeisser S, Kruegel C, Myers AC and Halevi S (eds.). ACM CCS 2016. ACM Press, 2016, 805–17. [Google Scholar]
 Lindell Y. Secure multiparty computation. Commun ACM 2020; 64: 86–96. [Google Scholar]
 Orsini E. Efficient, actively secure MPC with a dishonest majority: a survey. In: Bajard JC and Topuzoğlu A (eds.). International Workshop on the Arithmetic of Finite Fields  WAIFI 2020, volume 12542 of LNCS. Springer International Publishing, 2021, 42–71. [Google Scholar]
 Canetti R. Universally composable security: A new paradigm for cryptographic protocols. In: 42nd FOCS. IEEE IEEE Computer Society Press, 2001, 136–145. [Google Scholar]
 Goldreich O. Foundations of Cryptography: Volume 2  Basic Applications. Cambridge University Press, 2004. [Google Scholar]
 Canetti C. Security and composition of multiparty cryptographic protocols. J Cryptol 2000; 13: 143–202. [CrossRef] [Google Scholar]
 Kushilevitz E, Lindell Y and Rabin T. Informationtheoretically secure protocols and security under composition. In: Kleinberg JM (ed.). 38th ACM STOC. ACM Press, May 2006, 109–18. [Google Scholar]
 Goldwasser S and Lindell Y. Secure multiparty computation without agreement. J Cryptol 2005; 18: 247–87. [CrossRef] [Google Scholar]
 Even S, Goldreich O and Lempel A. A randomized protocol for signing contracts. Commun ACM 1985; 28: 637–47. [CrossRef] [Google Scholar]
 Rabin MO. How to Exchange Secrets by Oblivious Transfer. Technical Report TR81, Aiken Computation Laboratory, Harvard University, 1981. [Google Scholar]
 Naor M and Pinkas B. Oblivious transfer and polynomial evaluation. In: 31st ACM STOC. ACM Press, 1999, 245–54. [Google Scholar]
 Shamir A. How to share a secret. Commun ACM 1979; 22: 612–3. [CrossRef] [Google Scholar]
 Cramer R, Damgård I and Ishai Y. Share conversion, pseudorandom secretsharing and applications to secure computation. In: Kilian J (ed.). TCC 2005, volume 3378 of LNCS. Heidelberg: Springer, 2005, 342–62. [Google Scholar]
 Ito M, Saito A and Nishizeki T. Secret sharing scheme realizing general access structure. Electron Commun Jpn III 1989; 72: 56–64. [CrossRef] [Google Scholar]
 Lindell Y and Nof A. A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honestmajority. In: Thuraisingham BM, Evans D, Malkin T and Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 259–76. [Google Scholar]
 Dessouky G, Koushanfar F and Sadeghi AR et al. Pushing the communication barrier in secure computation using lookup tables. In: NDSS 2017. The Internet Society, 2017. [Google Scholar]
 Damg˚ard I, Pastro V, Smart NP and Zakarias S. Multiparty computation from somewhat homomorphic encryption. In: SafaviNaini R and Canetti R (eds.). CRYPTO 2012, volume 7417 of LNCS. Heidelberg: Springer, 2012, 643–62. [Google Scholar]
 Nielsen JB, Nordholt PS and Orlandi C et al. A new approach to practical activesecure twoparty computation. In: SafaviNaini R and Canetti R (eds.). CRYPTO 2012, volume 7417 of LNCS. Heidelberg: Springer, 2012, 681–700. [Google Scholar]
 Bendlin R, Damg˚ard I and Orlandi C et al. Semihomomorphic encryption and multiparty computation. In: Paterson KG (ed.). EUROCRYPT 2011, volume 6632 of LNCS. Heidelberg: Springer, 2011, 169–88 [Google Scholar]
 Hazay C, Scholl P and SoriaVazquez E. Low cost constant round MPC combining BMR and oblivious transfer. In: Takagi T and Peyrin T (eds.). ASIACRYPT 2017, Part I, volume 10624 of LNCS. Heidelberg: Springer, 2017, 598–628. [Google Scholar]
 Katz J, Ranellucci S and Rosulek M et al. Optimizing authenticated garbling for faster secure twoparty computation. In: Shacham H and Boldyreva A (eds.). CRYPTO 2018, Part III, volume 10993 of LNCS. Heidelberg: Springer, 2018, 365–91. [Google Scholar]
 Wang X, Ranellucci S and Katz J. Authenticated garbling and efficient maliciously secure twoparty computation. In: Thuraisingham BM, Evans D, Malkin T and Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 21–37. [Google Scholar]
 Wang X, Ranellucci S and Katz J. Globalscale secure multiparty computation. In: Thuraisingham BM, Evans D, Malkin T and Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 39–56. [Google Scholar]
 Yang K, Wang X and Zhang J. More efficient MPC from improved triple generation and authenticated garbling. In: Ligatti J, Ou X, Katz J and Vigna G (eds.). ACM CCS 20. ACM Press, 2020, 1627–46. [CrossRef] [Google Scholar]
 Zhu R, Cassel D and Sabry A et al. NANOPI: extremescale activelysecure multiparty computation. In: Lie D, Mannan M, Backes M and Wang XF (eds.). ACM CCS 2018. ACM Press, 2018, 862–79. [Google Scholar]
 Damg˚ard I, Nielsen JB, Nielsen M and Ranellucci S. The TinyTable protocol for 2party secure computation, or: Gatescrambling revisited. In: Katz J and Shacham H (eds.). CRYPTO 2017, Part I, volume 10401 of LNCS. Heidelberg: Springer, 2017, 167–87. [Google Scholar]
 Asharov G, Lindell Y and Schneider T et al. More efficient oblivious transfer and extensions for faster secure computation. In: Sadeghi AR, Gligor VD, Yung M (eds.). ACM CCS 2013. ACM Press, 2013, 535–48. [Google Scholar]
 Hazay C, Orsini E and Scholl P et al. TinyKeys: A new approach to efficient multiparty computation. In: Shacham H and Boldyreva A (eds.). CRYPTO 2018, Part III, volume 10993 of LNCS. Heidelberg: Springer, 2018, 3–33. [Google Scholar]
 Schneider T and Zohner M. GMW vs. Yao? Efficient secure twoparty computation with low depth circuits. In: Sadeghi AR (ed.). FC 2013, volume 7859 of LNCS. Heidelberg: Springer, 2013, 275–92. [Google Scholar]
 Damg˚ard I and Nielsen JB. Scalable and unconditionally secure multiparty computation. In: Menezes A (ed.). CRYPTO 2007, volume 4622 of LNCS. Heidelberg: Springer, 2007, 572–90. [Google Scholar]
 Gennaro R, Rabin MO and Rabin T. Simplified VSS and fasttrack multiparty computations with applications to threshold cryptography. In: Coan BA and Afek Y (eds.). 17th ACM PODC. ACM, 1998, 101–111. [Google Scholar]
 Goyal V, Li H and Ostrovsky R et al. ATLAS: Efficient and scalable MPC in the honest majority setting. In: Advances in Cryptology – CRYPTO 2021. Springer, 2021. [Google Scholar]
 Goyal V and Song Y. Malicious security comes free in honestmajority MPC. Cryptology ePrint Archive, Report 2020/134, 2020. https://eprint.iacr.org/2020/134. [Google Scholar]
 Genkin D, Ishai Y and Prabhakaran M et al. Circuits resilient to additive attacks with applications to secure computation. In: Shmoys DB (ed.). 46th ACM STOC. ACM Press, 2014, 495–504. [Google Scholar]
 Beaver D. Efficient multiparty protocols using circuit randomization. In: Feigenbaum J (ed.). CRYPTO’91, volume 576 of LNCS. Heidelberg: Springer, 1992, 420–32. [Google Scholar]
 Beerliov´aTrub´ıniov´a Z and Hirt M. Perfectlysecure MPC with linear communication complexity. In: Canetti R (ed.). TCC 2008, volume 4948 of LNCS. Heidelberg: Springer, 2008, 213–30 [Google Scholar]
 Lindell Y, Oxman E and Pinkas B. The IPS compiler: optimizations, variants and concrete efficiency. In: Rogaway P (ed.). CRYPTO 2011, volume 6841 of LNCS. Heidelberg: Springer, 2011, 259–76. [Google Scholar]
 Boneh D, Boyle E and CorriganGibbs H et al. Zeroknowledge proofs on secretshared data via fully linear PCPs. In: Boldyreva A and Micciancio D (eds.). CRYPTO 2019, Part III, volume 11694 of LNCS. Heidelberg: Springer, 2019, 67–97. [Google Scholar]
 Boyle E, Gilboa N and Ishai Y et al. Efficient fully secure computation via distributed zeroknowledge proofs. In: Advances in Cryptology – ASIACRYPT 2020, volume 12493 of LNCS. Springer International Publishing, 2020, 244–76. [CrossRef] [Google Scholar]
 Dalskov A, Escudero D and Keller M. Fantastic four: Honestmajority fourparty secure computation with malicious security. Cryptology ePrint Archive, Report 2020/1330, 2020. https://eprint.iacr.org/2020/1330. [Google Scholar]
 Abspoel M, Cramer R and Damg˚ard I et al. Efficient informationtheoretic secure multiparty computation over ℤ/p^{k}ℤ via galois rings. In: Hofheinz D and Rosen R (eds.). TCC 2019, Part I, volume 11891 of LNCS. Heidelberg: Springer, 2019, 471–501. [Google Scholar]
 Mouchet C, TroncosoPastoriza J and Bossuat JP et al. Multiparty Homomorphic Encryption from Ringlearningwith errors. Cryptology ePrint Archive, Report 2020/304, 2020. https://ia.cr/2020/304. [Google Scholar]
 BenEfraim A, Nielsen M and Omri E. Turbospeedz: Double your online SPDZ! Improving SPDZ using function dependent preprocessing. In: Deng RH, GauthierUma˜na V, Ochoa M and Yung M (eds.). ACNS 19, volume 11464 of LNCS. Heidelberg: Springer, 2019, 530–49. [Google Scholar]
 Ishai Y, Kilian J and Nissim K et al. Extending oblivious transfers efficiently. In: Boneh D (ed.). CRYPTO 2003, volume 2729 of LNCS. Heidelberg: Springer, August 2003, 145–61. [Google Scholar]
 Hazay C, Orsini E and Scholl P et al. Concretely efficient largescale MPC with active security (or, TinyKeys for TinyOT). In: Peyrin T and Galbraith S (eds.). ASIACRYPT 2018, Part III, volume 11274 of LNCS. Heidelberg: Springer, 2018, 86–117. [Google Scholar]
 Boyle E, Couteau G and Gilboa N et al. Efficient tworound OT extension and silent noninteractive secure computation. In: Cavallaro L, Kinder J, Wang X F and Katz J (eds.). ACM CCS 2019. ACM Press, 2019, 291–308. [Google Scholar]
 Rindal P, Raghuraman S and Couteau G. Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In: Advances in Cryptology – CRYPTO 2021, volume 12827 of LNCS. Springer International Publishing, 2021, 502–34. [Google Scholar]
 Yang K, Weng C, Lan X and et al. Ferret: fast extension for correlated OT with small communication. In: Ligatti J, Ou X, Katz J and Vigna G (eds.). ACM CCS 20. ACM Press, 2020, 1607–26. [CrossRef] [Google Scholar]
 Asharov G, Lindell Y and Schneider T et al. More efficient oblivious transfer extensions with security for malicious adversaries. In: Oswald E and Fischlin M (eds.). EUROCRYPT 2015, Part I, volume 9056 of LNCS. Heidelberg: Springer, 2015, 673–701. [Google Scholar]
 Keller M, Orsini E and Scholl P. Actively secure OT extension with optimal overhead. In: Gennaro R and Robshaw MJB (eds.). CRYPTO 2015, Part I, volume 9215 of LNCS. Heidelberg: Springer, 2015, 724–41. [Google Scholar]
 Goyal V, Song Y and Zhu C. Guaranteed output delivery comes free in honest majority MPC. In: Micciancio D and Ristenpart T (eds.). CRYPTO 2020, Part II, volume 12171 of LNCS. Heidelberg: Springer, 2020, 618–46. [Google Scholar]
 Chida K, Genkin D and Hamada K et al. Fast largescale honestmajority MPC for malicious adversaries. In: Shacham H and Boldyreva A (eds.). CRYPTO 2018, Part III, volume 10993 of LNCS. Heidelberg: Springer, 2018, 34–64. [Google Scholar]
 Furukawa J and Lindell Y. Twothirds honestmajority MPC for malicious adversaries at almost the cost of semihonest. In: Cavallaro L, Kinder J, Wang XF and Katz J (eds.). ACM CCS 2019. ACM Press, 2019, 1557–71. [Google Scholar]
 Nordholt PS and Veeningen M. Minimising communication in honestmajority MPC by batchwise multiplication verification. In: Preneel B and Vercauteren F (eds.). ACNS 18, volume 10892 of LNCS. Heidelberg: Springer, 2018, 321–39. [Google Scholar]
 Abspoel M, Cramer R and Escudero D et al. Improved singleround secure multiplication using regenerating codes. Cryptology ePrint Archive, Report 2021/253, 2021. https://eprint.iacr.org/2021/253. [Google Scholar]
 Guruswami V and Wootters M. Repairing ReedSolomon codes. In: Wichs D and Mansour Y (eds.). 48th ACM STOC. ACM Press, 2016, 216–26. [Google Scholar]
 Keller M, Rotaru D and Smart NP et al. Reducing communication channels in MPC. In: Catalano D and De Prisco R (eds.). SCN 18, volume 11035 of LNCS. Heidelberg: Springer, 2018, 181–99. [Google Scholar]
 Smart NP and Wood T. Error detection in monotone span programs with application to communicationefficient multiparty computation. In: Matsui M (ed.). CTRSA 2019, volume 11405 of LNCS. Heidelberg: Springer, 2019, 210–29. [Google Scholar]
 Ishai Y, Prabhakaran M and Sahai A. Founding cryptography on oblivious transfer – efficiently. In: Wagner D (ed.). CRYPTO 2008, volume 5157 of LNCS. Heidelberg: Springer, 2008, 572–91. [Google Scholar]
 Hazay C, Ishai Y and Marcedone A et al. LevioSA: Lightweight secure arithmetic computation. In: Cavallaro L, Kinder J, Wang XF and Katz J (eds.). ACM CCS 2019. ACM Press, 2019, 327–44. [Google Scholar]
 Hazay C, Venkitasubramaniam M and Weiss M. The price of active security in cryptographic protocols. In: Canteaut A and Ishai Y (eds.). EUROCRYPT 2020, Part II, volume 12106 of LNCS. Heidelberg: Springer, 2020, 184–215. [Google Scholar]
 Chen H and Cramer R. Algebraic geometric secret sharing schemes and secure multiparty computations over small fields. In: Dwork C (ed.). CRYPTO 2006, volume 4117 of LNCS. Heidelberg: Springer, 2006, 521–536. [Google Scholar]
 Damg˚ard I, Keller M and Larraia E et al. Practical covertly secure MPC for dishonest majority – or: Breaking the SPDZ limits. In: Crampton J, Jajodia S and Mayes K (eds.). ESORICS 2013, volume 8134 of LNCS. Heidelberg: Springer, 2013, 1–18. [Google Scholar]
 Gilboa N. Two party RSA key generation. In: Wiener MJ (ed.). CRYPTO’99, volume 1666 of LNCS. Heidelberg: Springer, 1999, 116–29. [Google Scholar]
 Brakerski Z, Gentry C and Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser S (ed.). ITCS 2012. ACM, 2012, 309–325. [Google Scholar]
 Keller M, Pastro V and Rotaru D. Overdrive: making SPDZ great again. In: Nielsen JB and Rijmen V (eds.). EUROCRYPT 2018, Part III, volume 10822 of LNCS. Heidelberg: Springer, 2018, 158–89. [Google Scholar]
 Baum C, Cozzo D and Smart NP. Using TopGear in overdrive: A more efficient ZKPoK for SPDZ. In: Paterson KG and Stebila D (eds.). SAC 2019, volume 11959 of LNCS. Heidelberg: Springer, 2019, 274–302. [Google Scholar]
 Chen H, Kim M and Razenshteyn I et al. Maliciously secure matrix multiplication with applications to private deep learning. Cryptology ePrint Archive, Report 2020/451, 2020. https://eprint.iacr.org/2020/451. [Google Scholar]
 Brakerski Z. Fully homomorphic encryption without modulus switching from classical GapSVP. In: SafaviNaini R and Canetti R (eds.). CRYPTO 2012, volume 7417 of LNCS. Heidelberg: Springer, 2012, 868–86. [Google Scholar]
 Fan J and Vercauteren F. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144, 2012. http://eprint.iacr.org/2012/144. [Google Scholar]
 Cramer R, Damg˚ard I and Escudero D et al. SPD ℤ_{2}k : Efficient MPC mod 2^{k} for dishonest majority. In: Shacham H and Boldyreva A (eds.). CRYPTO 2018, Part II, volume 10992 of LNCS. Heidelberg: Springer, 2018, 769–98. [Google Scholar]
 Damg˚ard I, Escudero D and Frederiksen TK et al. New primitives for activelysecure MPC over rings with applications to private machine learning. In: 2019 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2019, 1102–20. [CrossRef] [Google Scholar]
 Catalano D, Di Raimondo M and Fiore D et al. Monℤ_{2}k a: Fast maliciously secure two party computation on ℤ_{2}k . In: Kiayias A, Kohlweiss M, Wallden P and Zikas V (eds.). PKC 2020, Part II, volume 12111 of LNCS. Heidelberg: Springer, 2020, 357–86. [Google Scholar]
 Orsini E, Smart NP and Vercauteren F. Overdrive2k: efficient secure MPC over ℤ_{2}k from somewhat homomorphic encryption. In: Jarecki S (ed.). CTRSA 2020, volume 12006 of LNCS. Heidelberg: Springer, 2020, 254–83. [Google Scholar]
 Boyle E, Couteau G and Gilboa N et al. Efficient pseudorandom correlation generators from ringLPN. In: Micciancio D and Ristenpart T (eds.). CRYPTO 2020, Part II, volume 12171 of LNCS. Heidelberg: Springer, 2020, 387–416. [Google Scholar]
 Boyle E, Couteau G and Gilboa N et al. Efficient pseudorandom correlation generators: Silent OT extension and more. In: Boldyreva A and Micciancio D (eds.). CRYPTO 2019, Part III, volume 11694 of LNCS. Heidelberg: Springer, 2019, 489–518. [Google Scholar]
 Boyle E, Gilboa N and Ishai Y. Function secret sharing. In: Oswald E and Fischlin M (eds.). EUROCRYPT 2015, Part II, volume 9057 of LNCS. Heidelberg: Springer, 2015, 337–367. [Google Scholar]
 Frederiksen TK, Keller M and Orsini E et al. A unified approach to MPC with preprocessing using OT. In: Iwata T and Cheon JH (eds.). ASIACRYPT 2015, Part I, volume 9452 of LNCS. Heidelberg: Springer, 2015, 711–35. [Google Scholar]
 Larraia E, Orsini E and Smart N P. Dishonest majority multiparty computation for binary circuits. In: Garay JA and Gennaro R (eds.). CRYPTO 2014, Part II, volume 8617 of LNCS. Heidelberg: Springer, 2014, 495–512. [Google Scholar]
 Cascudo I, Gundersen JS. A secretsharing based MPC protocol for Boolean circuits with good amortized complexity. In: Theory of Cryptography, volume 12551 of LNCS. Springer International Publishing, 2020, 652–82. [CrossRef] [Google Scholar]
 Damg˚ard I, Lauritsen R and Toft T. An empirical study and some improvements of the MiniMac protocol for secure computation. In: Abdalla M and De Prisco R (eds.). SCN 14, volume 8642 of LNCS. Heidelberg: Springer, 2014, 398–415. [Google Scholar]
 Damg˚ard I and Zakarias S. Constantoverhead secure computation of Boolean circuits using preprocessing. In: Sahai A (ed.). TCC 2013, volume 7785 of LNCS. Heidelberg: Springer, 2013, 621–41. [Google Scholar]
 Frederiksen TK, Pinkas B and Yanai A. Committed MPC – maliciously secure multiparty computation from homomorphic commitments. In: Abdalla M and Dahab R (eds.). PKC 2018, Part I, volume 10769 of LNCS. Heidelberg: Springer, 2018, 587–619. [Google Scholar]
 Cascudo I, Cramer R and Xing C et al. Amortized complexity of informationtheoretically secure MPC revisited. In: Shacham H and Boldyreva A (eds.). CRYPTO 2018, Part III, volume 10993 of LNCS. Heidelberg: Springer, 2018, 395–426. [Google Scholar]
 Couteau G. A note on the communication complexity of multiparty computation in the correlated randomness model. In: Ishai Y and Rijmen V (eds.). EUROCRYPT 2019, Part II, volume 11477 of LNCS. Heidelberg: Springer, 2019, 473–503. [Google Scholar]
 Keller M, Orsini E and Rotaru D et al. Faster secure multiparty computation of AES and DES using lookup tables. In: Gollmann D, Miyaji A and Kikuchi H (eds.). ACNS 17, volume 10355 of LNCS. Heidelberg: Springer, 2017, 229–49. [Google Scholar]
 Furukawa J, Lindell Y and Nof A et al. Highthroughput secure threeparty computation for malicious adversaries and an honest majority. In: Coron JS and Nielsen JB (eds.). EUROCRYPT 2017, Part II, volume 10211 of LNCS. Heidelberg: Springer, 2017, 225–55. [Google Scholar]
 Araki T, Barak A and Furukawa J et al. Optimized honestmajority MPC for malicious adversaries – Breaking the 1 billiongate per second barrier. In: 2017 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2017, 843–62. [CrossRef] [Google Scholar]
 Boyle E, Gilboa N and Ishai Y et al. Practical fully secure threeparty computation via sublinear distributed zeroknowledge proofs. In: Cavallaro L, Kinder J, Wang XF and Katz J (eds.). ACM CCS 2019. ACM Press, 2019, 869–86. [Google Scholar]
 BenSasson E, Fehr S and Ostrovsky R. Nearlinear unconditionallysecure multiparty computation with a dishonest minority. In: SafaviNaini R and Canetti R (eds.). CRYPTO 2012, volume 7417 of LNCS. Heidelberg: Springer, 2012, 663–80. [Google Scholar]
 Polychroniadou A and Song Y. Constantoverhead unconditionally secure multiparty computation over binary fields. In: Canteaut A and Standaert FX (eds.). Advances in Cryptology – EUROCRYPT 2021, volume 12697 of LNCS. Springer International Publishing, 2021, 812–41. [CrossRef] [Google Scholar]
 Beck G, Goel A and Jain A et al. OrderC secure multiparty computation for highly repetitive circuits. In: Advances in Cryptology – EUROCRYPT 2021, volume 12697 of LNCS. Springer International Publishing, 2021, 663–93. [CrossRef] [Google Scholar]
 Gordon SD, Starin D and Yerukhimovich A. The more the merrier: Reducing the cost of large scale MPC. In: Advances in Cryptology – EUROCRYPT 2021, volume 12697 of LNCS. Springer International Publishing, 2021, 694–723. [CrossRef] [Google Scholar]
 Franklin MK and Yung M. Communication complexity of secure computation (extended abstract). In: 24th ACM STOC. ACM Press, 1992, 699–710. [Google Scholar]
 Damg˚ard I, Ishai Y and Krøigaard M. Perfectly secure multiparty computation and the computational overhead of cryptography. In: Gilbert H (ed.). EUROCRYPT 2010, volume 6110 of LNCS. Heidelberg: Springer, 2010, 445–65. [Google Scholar]
 Garay JA, Ishai Y and Ostrovsky R et al. The price of low communication in secure multiparty computation. In: Katz J and Shacham H (eds.). CRYPTO 2017, Part I, volume 10401 of LNCS. Heidelberg: Springer, 2017, 420–46. [Google Scholar]
 Genkin D, Ishai Y and Polychroniadou A. Efficient multiparty computation: From passive to active security via secure SIMD circuits. In: Gennaro R and Robshaw MJB (eds.). CRYPTO 2015, Part II, volume 9216 of LNCS. Heidelberg: Springer, 2015, 721–741. [Google Scholar]
 Goyal V, Polychroniadou A and Song Y. Unconditional communicationefficient MPC via Hall’s marriage theorem. Cryptology ePrint Archive, Report 2021/834, 2021. https://eprint.iacr.org/2021/834. [Google Scholar]
 Escudero D and Dalskov A. Honest majority MPC with abort with minimal online communication. Cryptology ePrint Archive, Report 2020/1556, 2020. https://eprint.iacr.org/2020/1556. [Google Scholar]
 Ashur T, Cohen E and Hazay C et al. A new framework for garbled circuits. Cryptology ePrint Archive, Report 2021/739, 2021. https://eprint.iacr.org/2021/739. [Google Scholar]
 Bellare M, Hoang VT and Rogaway P. Foundations of garbled circuits. In: Yu T, Danezis G and Gligor VD (eds.). ACM CCS 2012. ACM Press, 2012, 784–96. [CrossRef] [Google Scholar]
 Beaver D. Precomputing oblivious transfer. In: Coppersmith D (ed.). CRYPTO’95, volume 963 of LNCS. Heidelberg: Springer, 1995, 97–109. [Google Scholar]
 Huang Y, Evans D and Katz J et al. Faster secure twoparty computation using garbled circuits. In: USENIX Security 2011. USENIX Association, 2011. [Google Scholar]
 Lindell Y and Pinkas B. A proof of security of Yao’s protocol for twoparty computation. J Cryptol 2009; 22: 161–88. [CrossRef] [Google Scholar]
 Malkhi D, Nisan N and Pinkas B et al. Fairplay – secure twoparty computation system. In: Blaze M (ed.). USENIX Security 2004. USENIX Association, 2004, 287–302. [Google Scholar]
 Naor M, Pinkas B and Sumner R. Privacy preserving auctions and mechanism design. In: Proceedings of the 1st ACM Conference on Electronic Commerce – EC’99. New York, NY: ACM, 1999, 129–39. [Google Scholar]
 Pinkas B, Schneider T and Smart NP et al. Secure twoparty computation is practical. In: Matsui M (ed.). ASIACRYPT 2009, volume 5912 of LNCS. Heidelberg: Springer, 2009, 250–67. [Google Scholar]
 Kolesnikov V and Schneider T. Improved garbled circuit: Free XOR gates and applications. In: Aceto L, Damg˚ard I, Goldberg LA, Halld´orsson MM, Ing´olfsd´ottir A and Walukiewicz I (eds.). ICALP 2008, Part II, volume 5126 of LNCS. Heidelberg: Springer, 2008, 486–498. [Google Scholar]
 Zahur S, Rosulek M and Evans D. Two halves make a whole – reducing data transfer in garbled circuits using half gates. In: Oswald E and Fischlin M (eds.). EUROCRYPT 2015, Part II, volume 9057 of LNCS. Heidelberg: Springer, 2015, 220–50. [Google Scholar]
 Choi SG, Katz J and Kumaresan R et al. On the security of the “freeXOR” technique. In: Cramer R (ed.). TCC 2012, volume 7194 of LNCS. Heidelberg: Springer, 2012, 39–53. [Google Scholar]
 Bellare M, Hoang VT and Keelveedhi S et al. Efficient garbling from a fixedkey blockcipher. In: IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2013, 478–92. [Google Scholar]
 Guo C, Katz J, Wang X and Yu Y. Efficient and secure multiparty computation from fixedkey block ciphers. In: 2020 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2020, 825–41. [CrossRef] [Google Scholar]
 Rosulek M and Roy L. Three halves make a whole? Beating the halfgates lower bound for garbled circuits. In: Malkin T and Peikert C (eds.). Advances in Cryptology – CRYPTO 2021, volume 12825 of LNCS. Springer International Publishing, 2021, 94–124. [CrossRef] [Google Scholar]
 Kolesnikov V, Mohassel P and Rosulek M. FleXOR: Flexible garbling for XOR gates that beats freeXOR. In: Garay JA and Gennaro R (eds.). CRYPTO 2014, Part II, volume 8617 of LNCS. Heidelberg: Springer, 2014, 440–57. [Google Scholar]
 Gueron S, Lindell Y and Nof A et al. Fast garbling of circuits under standard assumptions. In: Ray I, Li N and Kruegel C (eds.). ACM CCS 2015. ACM Press, 2015, 567–78. [Google Scholar]
 Applebaum B, Ishai Y and Kushilevitz E. How to garble arithmetic circuits. In: Ostrovsky R (ed.). 52nd FOCS. IEEE Computer Society Press, 2011, 120–9. [Google Scholar]
 Ball M, Carmer B and Malkin T et al. Garbled neural networks are practical. Cryptology ePrint Archive, Report 2019/338, 2019. https://eprint.iacr.org/2019/338. [Google Scholar]
 Ball M, Malkin T and Rosulek M. Garbling gadgets for Boolean and arithmetic circuits. In: Weippl ER, Katzenbeisser S, Kruegel C, Myers AC and Halevi S (eds.). ACM CCS 2016. ACM Press, 2016, 565–77. [Google Scholar]
 BenEfraim A. On multiparty garbling of arithmetic circuits. In: Peyrin T and Galbraith S (eds.). ASIACRYPT 2018, Part III, volume 11274 of LNCS. Heidelberg: Springer, 2018, 3–33. [CrossRef] [Google Scholar]
 BenEfraim A, Lindell Y and Omri E. Optimizing semihonest secure multiparty computation for the Internet. In: Weippl ER, Katzenbeisser S, Kruegel C, Myers AC and Halevi S (eds.). ACM CCS 2016. ACM Press, 2016, 578–90. [Google Scholar]
 Aner BenEfraim A, Lindell Y and Omri E. Efficient scalable constantround MPC via garbled circuits. In: Takagi T and Peyrin T (eds.). ASIACRYPT 2017, Part II, volume 10625 of LNCS. Heidelberg: Springer, 2017, 471–98. [CrossRef] [Google Scholar]
 BenEfraim A, Cong K and Omri E et al. Large scale, actively secure computation from LPN and freeXOR garbled circuits. In: Advances in Cryptology – EUROCRYPT 2021, volume 12697 of LNCS. Springer International Publishing, 2021. [Google Scholar]
 Lindell Y and Pinkas B. An efficient protocol for secure twoparty computation in the presence of malicious adversaries. In: Naor M (ed.). EUROCRYPT 2007, volume 4515 of LNCS. Heidelberg: Springer, 2007, 52–78. [CrossRef] [Google Scholar]
 Afshar A, Mohassel P and Pinkas B et al. Noninteractive secure computation based on cutandchoose. In: Nguyen PQ and Oswald E (eds.). EUROCRYPT 2014, volume 8441 of LNCS. Heidelberg: Springer, 2014, 387–404. [CrossRef] [Google Scholar]
 Brandão LTAN. Secure twoparty computation with reusable bitcommitments, via a cutandchoose with forgeandlose technique – (extended abstract). In: Sako K and Sarkar P (eds.). ASIACRYPT 2013, Part II, volume 8270 of LNCS. Heidelberg: Springer, 2013, 441–63. [Google Scholar]
 Frederiksen TK, Jakobsen TP and Nielsen JB. Faster maliciously secure twoparty computation using the GPU. In: Abdalla M and De Prisco R (eds.). SCN 14, volume 8642 of LNCS. Heidelberg: Springer, 2014, 358–79. [Google Scholar]
 Huang Y, Katz J and Evans D. Efficient secure twoparty computation using symmetric cutandchoose. In: Canetti R and Garay JA (eds.). CRYPTO 2013, Part II, volume 8043 of LNCS. Heidelberg: Springer, 2013, 18–35. [CrossRef] [Google Scholar]
 Huang Y, Katz Y and Kolesnikov V et al. Amortizing garbled circuits. In: Garay JA and Gennaro R (eds.). CRYPTO 2014, Part II, volume 8617 of LNCS. Heidelberg: Springer, 2014, 458–75. [CrossRef] [Google Scholar]
 Kreuter B and Shen CH. Billiongate secure computation with malicious adversaries. In: Kohno T (ed.). USENIX Security 2012. USENIX Association, 2012, 285–300. [Google Scholar]
 Lindell Y. Fast cutandchoose based protocols for malicious and covert adversaries. In: Canetti R and Garay J A (eds.). CRYPTO 2013, Part II, volume 8043 of LNCS. Heidelberg: Springer, 2013, 1–17. [Google Scholar]
 Lindell Y and Pinkas B. Secure twoparty computation via cutandchoose oblivious transfer. In: Yuval I (ed.). TCC 2011, volume 6597 of LNCS. Heidelberg: Springer, 2011, 329–46. [Google Scholar]
 Lindell Y and Riva B. Cutandchoose Yaobased secure computation in the online/offline and batch settings. In: Garay JA and Gennaro R (eds.). CRYPTO 2014, Part II, volume 8617 of LNCS. Heidelberg: Springer, 2014, 476–494. [CrossRef] [Google Scholar]
 Lindell Y and Riva B. Blazing fast 2PC in the offline/online setting with security for malicious adversaries. In: Ray I, Li N and Kruegel C (eds.). ACM CCS 2015. ACM Press, 2015, 579–590. [Google Scholar]
 Nielsen JB and Orlandi C. Cross and clean: amortized garbled circuits with constant overhead. In: Hirt M and Smith AD (eds.). TCC 2016B, Part I, volume 9985 of LNCS. Heidelberg: Springer, 2016, 582–603. [Google Scholar]
 Rindal P and Rosulek M. Faster malicious 2party secure computation with online/offline dual execution. In: Holz T and Savage S (eds.). USENIX Security 2016. USENIX Association, 2016, 297–314. [Google Scholar]
 Shelat A and Shen CH. Twooutput secure computation with malicious adversaries. In: Paterson KG (ed.). EUROCRYPT 2011, volume 6632 of LNCS. Heidelberg: Springer, 2011, 386–405. [CrossRef] [Google Scholar]
 Shelat A and Shen CH. Fast twoparty secure computation with minimal assumptions. In: Sadeghi AR, Gligor VD and Yung M (eds.). ACM CCS 2013. ACM Press, 2013, 523–34. [Google Scholar]
 Wang X, Malozemoff AJ and Katz J. Faster secure twoparty computation in the singleexecution setting. In: Coron JS and Nielsen JB (eds.). EUROCRYPT 2017, Part III, volume 10212 of LNCS. Heidelberg: Springer, 2017, 399–424. [Google Scholar]
 Nielsen JB and Orlandi C. LEGO for twoparty secure computation. In: Reingold O (ed.). TCC 2009, volume 5444 of LNCS. Heidelberg: Springer, 2009, 368–86. [Google Scholar]
 Frederiksen TK, Jakobsen TP and Nielsen JB et al. TinyLEGO: An interactive garbling scheme for maliciously secure twoparty computation. Cryptology ePrint Archive, Report 2015/309, 2015. http://eprint.iacr.org/2015/309. [Google Scholar]
 Frederiksen TK, Jakobsen TP and Nielsen JB et al. MiniLEGO: Efficient secure twoparty computation from general assumptions. In: Johansson T and Nguyen PQ (eds.). EUROCRYPT 2013, volume 7881 of LNCS. Heidelberg: Springer, 2013, 537–56. [CrossRef] [Google Scholar]
 Huang Y and Zhu R. Revisiting LEGOs: Optimizations, analysis, and their limit. Cryptology ePrint Archive, Report 2015/1038, 2015. http://eprint.iacr.org/2015/1038. [Google Scholar]
 Kolesnikov V, Nielsen JB and Rosulek M et al. DUPLO: Unifying cutandchoose for garbled circuits. In: Thuraisingham BM, Evans D, Malkin T and Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 3–20. [Google Scholar]
 Nielsen J B, Schneider T and Trifiletti R. Constant round maliciously secure 2PC with functionindependent preprocessing using LEGO. In: NDSS 2017. The Internet Society, 2017. [Google Scholar]
 Zhu R and Huang Y. JIMU: faster LEGObased secure computation using additive homomorphic hashes. In: Takagi T and Peyrin T (eds.). ASIACRYPT 2017, Part II, volume 10625 of LNCS. Heidelberg: Springer, 2017, 529–72. [CrossRef] [Google Scholar]
 Choi SG, Katz J and Malozemoff AJ et al. Efficient threeparty computation from cutandchoose. In: Garay JA and Gennaro R (eds.). CRYPTO 2014, Part II, volume 8617 of LNCS. Heidelberg: Springer, 2014, 513–30. [CrossRef] [Google Scholar]
 Lindell Y, Pinkas B and Smart NP et al. Efficient constant round multiparty computation combining BMR and SPDZ. In: Gennaro R and Robshaw MJB (eds.). CRYPTO 2015, Part II, volume 9216 of LNCS. Heidelberg: Springer, 2015, 319–338. [CrossRef] [Google Scholar]
 Lindell Y, Smart NP and SoriaVazquez E. More efficient constantround multiparty computation from BMR and SHE. In: Hirt M and Smith AD (eds.). TCC 2016B, Part I, volume 9985 of LNCS. Heidelberg: Springer, 2016, 554–81. [Google Scholar]
 Poddar R, Kalra S and Yanai A et al. Senate: a maliciouslysecure MPC platform for collaborative analytics. In: 30th USENIX Security Symposium (USENIX Security 21). USENIX Association, 2021, 2129–46. [Google Scholar]
 Byali M, Joseph A and Patra A et al. Fast secure computation for small population over the Internet. In: Lie D, Mannan M, Backes M and Wang XF (eds.). ACM CCS 2018. ACM Press, 2018, 677–694. [Google Scholar]
 Chandran N, Garay JA and Mohassel P et al. Efficient, constantround and actively secure MPC: Beyond the threeparty case. In: Thuraisingham BM, Evans D, Malkin T, Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 277–294. [Google Scholar]
 Ishai Y, Kumaresan R and Kushilevitz E et al. Secure computation with minimal interaction, revisited. In: Gennaro R and Robshaw MJB (eds.). CRYPTO 2015, Part II, volume 9216 of LNCS. Heidelberg: Springer, 2015, 359–78. [CrossRef] [Google Scholar]
 Mohassel P, Rosulek M and Zhang Y. Fast and secure threeparty computation: the garbled circuit approach. In: Ray I, Li N and Kruegel C (eds.). ACM CCS 2015. ACM Press, 2015, 591–602. [Google Scholar]
 Byali M, Hazay C and Patra A et al. Fast actively secure fiveparty computation with security beyond abort. In: Cavallaro L, Kinder J, Wang XF and Katz J (eds.). ACM CCS 2019. ACM Press, 2019, 1573–1590. [Google Scholar]
 Canetti R, Sarkar P and Wang X. Blazing fast OT for threeround UC OT extension. In: Kiayias A, Kohlweiss M, Wallden P and Zikas V (eds.). PKC 2020, Part II, volume 12111 of LNCS. Heidelberg: Springer, 2020, 299–327. [Google Scholar]
 Masny D and Rindal P. Endemic oblivious transfer. In: Cavallaro L, Kinder J, Wang XF and Katz J (eds.). ACM CCS 2019. ACM Press, 2019, 309–326. [Google Scholar]
 McQuoid I, Rosulek M and Roy L. Minimal symmetric PAKE and 1outofN OT from programmableonce public functions. In: Ligatti J, Ou X, Katz J and Vigna G (eds.). ACM CCS 20. ACM Press, 2020, 425–42. [CrossRef] [Google Scholar]
 McQuoid I, Rosulek M and Roy L. Batching Base Oblivious Transfers. Cryptology ePrint Archive, Report 2021/682, 2021. https://eprint.iacr.org/2021/682. [Google Scholar]
 Peikert C, Vaikuntanathan V and Waters B. A framework for efficient and composable oblivious transfer. In: Wagner D (ed.). CRYPTO 2008, volume 5157 of LNCS. Heidelberg: Springer, 2008, 554–71. [CrossRef] [Google Scholar]
 Chou T and Orlandi C. The simplest protocol for oblivious transfer. In: Progress in Cryptology – LATINCRYPT 2015, volume 9230 of LNCS. Springer International Publishing, 2015, 40–58. [Google Scholar]
 Döttling N, Garg S and Hajiabadi M et al. Tworound oblivious transfer from CDH or LPN. In: Canteaut A and Ishai Y (eds.). EUROCRYPT 2020, Part II, volume 12106 of LNCS. Heidelberg: Springer, 2020, 768–97. [CrossRef] [Google Scholar]
 Naor M and Pinkas B. Efficient oblivious transfer protocols. In: Kosaraju SR (ed.). In: 12th SODA. ACMSIAM, 2001, 448–57. [Google Scholar]
 Branco P, Ding J and Goulão M et al. A framework for universally composable oblivious transfer from oneround keyexchange. In: Albrecht M (ed.). IMA International Conference on Cryptography and Coding – IMACC 2019, volume 11929 of LNCS. Springer International Publishing, 2019, 78–101. [Google Scholar]
 David B and Dowsley R. Efficient composable oblivious transfer from CDH in the global random oracle model. Cryptology ePrint Archive, Report 2020/1291, 2020. https://eprint.iacr.org/2020/1291. [Google Scholar]
 Quach W. UCsecure OT from LWE, Revisited. Cryptology ePrint Archive, Report 2020/819, 2020. https://eprint.iacr.org/2020/819. [Google Scholar]
 Lai YF, Galbraith SD and de Saint Guilhem CD. Compact, Efficient and UCsecure Isogenybased Oblivious Transfer. Cryptology ePrint Archive, Report 2020/1012. 2020. https://eprint.iacr.org/2020/1012. [Google Scholar]
 Beaver D. Correlated pseudorandomness and the complexity of private computations. In: 28th ACM STOC. ACM Press, 1996, 479–488. [Google Scholar]
 Boyle E, Couteau G and Gilboa N et al. Compressing vector OLE. In: Lie D, Mannan M, Backes M and Wang XF (eds.). ACM CCS 2018. ACM Press, 2018, 896–912. [Google Scholar]
 Blum A, Furst ML and Kearns MJ et al. Cryptographic primitives based on hard learning problems. In: Stinson DR (ed.). CRYPTO’93, volume 773 of LNCS. Heidelberg: Springer, 1994, 278–91. [Google Scholar]
 Boyle E, Couteau G and Gilboa N et al. Correlated pseudorandom functions from variabledensity LPN. Cryptology ePrint Archive, Report 2020/1417, 2020. https://eprint.iacr.org/2020/1417. [Google Scholar]
 Goldreich O, Goldwasser S and Micali S. How to construct random functions. J ACM 1986; 33:792–807. [CrossRef] [Google Scholar]
 Boneh D and Waters B. Constrained pseudorandom functions and their applications. In: Sako K and Sarkar P (eds.). ASIACRYPT 2013, Part II, volume 8270 of LNCS. Heidelberg: Springer, 2013, 280–300. [Google Scholar]
 Kiayias A, Papadopoulos S and Triandopoulos N et al. Delegatable pseudorandom functions and applications. In: Sadeghi AR, Gligor VD and Yung M (eds.). ACM CCS 2013. ACM Press, 2013, 669–84. [Google Scholar]
 Schoppmann P, Gascón A and Reichert L et al. Distributed vectorOLE: Improved constructions and implementation. In: Cavallaro L, Kinder J, Wang XF, Katz J (eds.). ACM CCS 2019. ACM Press, 2019, 1055–72. [Google Scholar]
 Augot D, Finiasz M and Sendrier N. A fast provably secure cryptographic hash function. Cryptology ePrint Archive, Report 2003/230, 2003. http://eprint.iacr.org/2003/230. [Google Scholar]
 Applebaum B, Damgård I and Ishai Y et al. Secure arithmetic computation with constant computational overhead. In: Katz J, Shacham H (eds.). CRYPTO 2017, Part I, volume 10401 of LNCS. Heidelberg: Springer, 2017, 223–54. [CrossRef] [Google Scholar]
 Döttling N, Ghosh S and Nielsen JB et al. TinyOLE: Efficient actively secure twoparty computation from oblivious linear function evaluation. In: Thuraisingham BM, Evans D, Malkin T and Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 2263–76. [Google Scholar]
 Ishai Y, Prabhakaran M and Sahai A. Secure arithmetic computation with no honest majority. Theory of Cryptography, volume 5444 of LNCS. Berlin, Heidelberg: Springer, 2009. 294–314. [Google Scholar]
 De Castro L, Juvekar C and Vaikuntanathan V. Fast vector oblivious linear evaluation from ring learning with errors. Cryptology ePrint Archive, Report 2020/685, 2020. https://eprint.iacr.org/2020/685. [Google Scholar]
 Baum C, Escudero D and PedrouzoUlloa A et al. Efficient protocols for oblivious linear function evaluation from ring – LWE. In: Galdi C and Kolesnikov V (eds.). SCN 20, volume 12238 of LNCS. Heidelberg: Springer, 2020, 130–49. [Google Scholar]
 Branco P, Döttling N and Mateus P. Tworound oblivious linear evaluation from learning with errors. Cryptology ePrint Archive, Report 2020/635, 2020. https://eprint.iacr.org/2020/635. [Google Scholar]
 Ghosh S, Nielsen JB and Nilges T. Maliciously secure oblivious linear function evaluation with constant overhead. In: Takagi T and Peyrin T (eds.). ASIACRYPT 2017, art I, volume 10624 of LNCS. Heidelberg: Springer, 2017, 629–59. [CrossRef] [Google Scholar]
 Chase M, Dodis Y and Ishai Y et al. Reusable noninteractive secure computation. In: Boldyreva A and Micciancio D (eds.). CRYPTO 2019, Part III, volume 11694 of LNCS. Heidelberg: Springer, 2019, 462–488. [CrossRef] [Google Scholar]
 Abspoel M, Escudero D and Volgushev N. Secure training of decision trees with continuous attributes. Proc Priv Enhancing Technol 2020; 2021:167–87. [CrossRef] [Google Scholar]
 Adams S, Choudhary C and De Cock M et al. Privacypreserving training of tree ensembles over continuous data. Cryptology ePrint Archive, Report 2021/754, 2021. https://eprint.iacr.org/2021/754. [Google Scholar]
 Attrapadung N, Hamada K and Ikarashi D et al. Adam in private: Secure and fast training of deep neural networks with adaptive moment estimation. Cryptology ePrint Archive, Report 2021/736, 2021. https://eprint.iacr.org/2021/736. [Google Scholar]
 Braun L, Demmler D and Schneider T et al. MOTION – A framework for mixedprotocol multiparty computation. Cryptology ePrint Archive, Report 2020/1137, 2020. https://eprint.iacr.org/2020/1137. [Google Scholar]
 Knott B, Venkataraman S and Hannun A et al. CrypTen: secure multiparty computation meets machine learning. In: Proceedings of the NeurIPS Workshop on PrivacyPreserving Machine Learning, 2020. [Google Scholar]
 Nikolaenko V, Weinsberg U and Ioannidis S et al. Privacypreserving ridge regression on hundreds of millions of records. In: 2013 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 2013, 334–48. [CrossRef] [Google Scholar]
 Wang Q, Ma Q and Li J et al. Enable Dynamic Parameters Combination to Boost Linear Convolutional Neural Network for Sensitive Data Inference. Cryptology ePrint Archive, Report 2020/961, 2020. https://eprint.iacr.org/2020/961. [Google Scholar]
 Liu J, Juuti M and Lu Y et al. Oblivious neural network predictions via MiniONN transformations. In: Thuraisingham BM, Evans D, Malkin T and Xu D (eds.). ACM CCS 2017. ACM Press, 2017, 619–31. [Google Scholar]
 Chandran N, Gupta D and Rastogi A et al. EzPC: Programmable and efficient secure twoparty computation for machine learning. In: 2019 IEEE European Symposium on Security and Privacy (EuroS&P), 2019, 496–511. [CrossRef] [Google Scholar]
 Simonyan K and Zisserman A. Very Deep Convolutional Networks for Largescale Image Recognition, 2015. https://arxiv.org/pdf/1409.1556.pdf [Google Scholar]
 Boemer F, Cammarota R and Demmler D et al. MP2ML: A mixedprotocol machine learning framework for private inference. In: Proceedings of the 15th International Conference on Availability, Reliability and Security – ARES’20. ACM, 2020. [Google Scholar]
 Dowlin N, GiladBachrach R and Laine K et al. CryptoNets: Applying neural networks to encrypted data with high throughput and accuracy. In: ^{Proceedings of the 33rd International Conference on International Conference on Machine Learning  ICML’16}, 2016, 201–210. https://JMLR.org. [Google Scholar]
 Huang G, Liu Z and Van Der Maaten L et al. Densely connected convolutional networks. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, 2261–69. [CrossRef] [Google Scholar]
 Dalskov A, Escudero D and Keller M. Secure evaluation of quantized neural networks. Proc Priv Enh Technol 2020; 2020:355–75. [Google Scholar]
 Howard AG, Zhu M and Chen B et al. MobileNets: Efficient convolutional neural networks for mobile vision applications, 2017. [Google Scholar]
 Spagnolo F, Perri S and Frustaci F et al. Energyefficient architecture for CNNs inference on heterogeneous FPGA. J Low Power Electron Appl 2020; 10:1. [Google Scholar]
 Riazi M S, Weinert C and Tkachenko O et al. Chameleon: a hybrid secure computation framework for machine learning applications. In: Kim J, Ahn GJ, Kim S, Kim Y, López J and Kim T (eds.). ASIACCS 18. ACM Press, 2018, 707–21. [CrossRef] [Google Scholar]
 Krizhevsky A, Sutskever I and Hinton G E. Imagenet classification with deep convolutional neural networks. Commun ACM 2017; 60:84–90. [CrossRef] [Google Scholar]
 Chaudhari H, Choudhury A and Patra A, ASTRA: High throughput 3PC over rings with application to secure prediction. In: Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop – CCSW’19. ACM, 2019, 81–92. [Google Scholar]
 Wagh S, Gupta D and Chandran N. SecureNN: 3party secure computation for neural network training. Proc Priv Enh Technol 2019; 2019:26–49. [Google Scholar]
 Koti N, Pancholi M and Patra A et al. SWIFT: superfast and robust privacypreserving machine learning. In: 30th USENIX Security Symposium (USENIX Security 21). USENIX Association, 2021. [Google Scholar]
 He K, Zhang X and Ren S et al. Deep residual learning for image recognition. In: 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, 770–78. [CrossRef] [Google Scholar]
 Wagh S, Tople S and Benhamouda F et al. FALCON: Honestmajority Maliciously Secure Framework for Private Deep Learning, 2021. https://arxiv.org/abs/2004.02229 [Google Scholar]
 Byali M, Chaudhari H and Patra A et al. Flash: Fast and robust framework for privacypreserving machine learning. Cryptology ePrint Archive, Report 2019/1365, 2019.https://eprint.iacr.org/2019/1365. [Google Scholar]
 Koti N, Patra A and Rachuri R et al. Tetrad: Actively Secure 4 PC for Secure Training and Inference. Cryptology ePrint Archive, Report 2021/755, 2021.https://eprint.iacr.org/2021/755. [Google Scholar]
 Carpov S, Deforth K and Gama N et al. Manticore: Efficient framework for scalable secure multiparty computation protocols. Cryptology ePrint Archive, Report 2021/200, 2021. https://eprint.iacr.org/2021/200. [Google Scholar]
 Aly A, Orsini E and Rotaru D et al. Zaphod: Efficiently combining LSSS and garbled circuits in SCALE. In: Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC’19. ACM, 2019, 33–44. [CrossRef] [Google Scholar]
 Rotaru D, Smart NP and Tanguy T et al. Actively Secure Setup for SPDZ. Cryptology ePrint Archive, Report 2019/1300, 2019. https://eprint.iacr.org/2019/1300. [Google Scholar]
 Rotaru D and Wood T. MArBled circuits: mixing arithmetic and Boolean circuits with active security. In: Hao F, Ruj S and Sen Gupta S (eds.). INDOCRYPT 2019, volume 11898 of LNCS. Heidelberg: Springer, 2019, 227–49. [CrossRef] [Google Scholar]
 Escudero D, Ghosh S and Keller M et al. Improved primitives for MPC over mixed arithmeticbinary circuits. In: Micciancio D and Ristenpart T (eds.). CRYPTO 2020, Part II, volume 12171 of LNCS. Heidelberg: Springer, 2020, 823–852. [CrossRef] [Google Scholar]
 Boyle E, Chandran N and Gilboa N et al. Function secret sharing for mixedmode and fixedpoint secure computation. In: Advances in Cryptology – EUROCRYPT 2021, volume 12697 of LNCS. Springer International Publishing, 2021, 871–900. [CrossRef] [Google Scholar]
 Boyle E, Gilboa N and Ishai Y. Secure computation with preprocessing via function secret sharing. In: Hofheinz D and Rosen A (eds.). TCC 2019, Part I, volume 11891 of LNCS. Heidelberg: Springer, 2019, 341–371. [Google Scholar]
 ISO/IEC JTC 1/SC 27. ISO/IEC WD 49222.3 Information security – Secure multiparty computation – Part 2: Mechanisms based on secret sharing, 2021. https://www.iso.org/standard/80514.html. [Google Scholar]
 National Institute of Standards and Technology (NIST). Multi party Threshold Cryptography, 2021. https://csrc.nist.gov/Projects/ThresholdCryptography. [Google Scholar]
 National Institute of Standards and Technology (NIST). Privacyenhancing Cryptography, 2021. https://csrc.nist.gov/Projects/pec. [Google Scholar]
Dengguo Feng received his Ph.D. degree in communication engineering and information system from Xidian University in 1995. He is currently a Professor and Ph.D. supervisor. His main research interests include network and information security, trusted computing and information assurance.
Kang Yang received his Ph.D. degree from the Institute of Software, Chinese Academy of Sciences in 2017. He is currently an Associated Professor with the State Key Laboratory of Cryptology, Beijing, China. His research interests include secure multiparty computation, zeroknowledge proofs and so on.
All Tables
All Figures
Figure 1. Framework for semihonest MPC protocols based on the secretsharing approach in both dishonestmajority and honestmajority settings 

In the text 
Figure 2. Semihonest multiplication protocols based on secret sharings of different types 

In the text 
Figure 3. Semihonest Yao’s 2PC protocol 

In the text 
Figure 4. Structure of the PCGbased COT protocols. When κ = 128, we need to use publickey operations to compute 128 base ROT correlations based on the DDH, CDH, or LWE assumptions. We can use the IKNPstyle OT extension protocol to generate COT correlations in an order of magnitude 10^{3} − 10^{4}, and then extend them to COT correlations in an order of magnitude 10^{5} − 10^{7} (or even more) based on the LPN assumption 

In the text 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.