We provide new two-round multiparty secure computation (MPC) protocols in the dishonest majority setting assuming the minimal assumption that two-round oblivious transfer (OT) exists. If the assumed two-round OT protocol is secure against semi-honest adversaries (in the plain model) then so is our two-round MPC protocol. Similarly, if the assumed two-round OT protocol is secure against malicious adversaries (in the common random/reference string model) then so is our two-round MPC protocol. Previously, two-round MPC protocols were only known under relatively stronger computational assumptions.
1 Introduction
Can a group of n mutually distrusting parties compute a joint function of their private inputs without revealing anything more than the output to each other? This is the classical problem of secure computation in cryptography. Yao [57] and Goldreich, Micali, and Wigderson [43] provided protocols for solving this problem in the two-party computation (2PC) and the multiparty computation (MPC) cases, respectively.
A remarkable aspect of the 2PC protocol based on Yao’s garbled circuit construction is its simplicity and the fact that it requires only two-rounds of communication. Moreover, this protocol can be based just on the minimal assumption that two-round 1-out-of-2 oblivious transfer (OT) exists. Two-round OT can itself be based on a variety of computational assumptions such as the Decisional Diffie-Hellman Assumption [1, 16, 52, 54], quadratic residuosity assumption [46, 54], or the learning-with-errors assumption [54].
In contrast, much less is known about the assumptions that two-round MPC can be based on (constant-round MPC protocols based on any OT protocol are well-known [14]). In particular, two-round MPC protocols (for an arbitrary polynomial number of parties) are only known under assumptions such as indistinguishability obfuscation [36, 37] (or, witness encryption [38, 45]), or LWE [22, 33, 51, 53].1 In summary, there is a significant gap between assumptions known to be sufficient for two-round MPC and the assumptions that known to be sufficient for two-round 2PC (or, two-round OT). This brings us to the following main question:
What are the minimal assumptions under which two-round MPC can be constructed?
1.1 Our Result
In this work, we give two-round MPC protocols assuming only the necessary assumption that two-round OT exists. This result was first realized based on bilinear pairings in [40] and was later refined to its current form in [41]. In more detail, our main theorem is
Theorem 1.1 (Main Theorem).
Let \(\mathcal {X} \in \lbrace\)semi-honest in plain model, malicious in common random/reference sting model\(\rbrace\). Assuming the existence of a two-round \(\mathcal {X}\)-OT protocol, there exists a compiler that transforms any polynomial round, \(\mathcal {X}\)-MPC protocol into a two-round, \(\mathcal {X}\)-MPC protocol.
Previously, such compilers [36, 45] were only known under comparatively stronger computational assumptions such as indistinguishability obfuscation [12, 37] or witness encryption [38]. Additionally, two-round MPC protocols assuming the learning-with-errors assumptions were known [22, 51, 53] in the CRS model satisfying semi-malicious security.2 We now discuss instantiations of the above compiler with known protocols (with larger round complexity) that yield two-round MPC protocols in various settings under minimal assumptions.
Semi-Honest Case. Plugging in the semi-honest secure MPC protocol by Goldreich, Micali, and Wigderson [43], we get the following result:
Corollary 1.2.
Assuming the existence of a semi-honest, two-round oblivious transfer in the plain model, there exists a semi-honest, two-round multiparty computation protocol in the plain model.
Previously, two-round plain model semi-honest MPC protocols were only known assuming indistinguishability obfuscation [12, 37], or witness encryption [38]. Thus, using two-round plain model OT [1, 46, 52] based on standard number theoretic assumptions such as DDH or QR, this work yields the first two-round semi-honest MPC protocol for a polynomial number of parties in the plain model under the same assumptions.
Malicious Case. Plugging in the maliciously secure MPC protocol by Kilian [49] or by Ishai, Prabhakaran, and Sahai [48] based on any oblivious transfer, we get the following corollary:
Corollary 1.3.
Assuming the existence of UC secure, two-round oblivious transfer against static, malicious adversaries, there exists a UC secure, two-round multiparty computation protocol against static, malicious adversaries.
Previously, all known two-round maliciously secure MPC protocols required additional use of non-interactive zero-knowledge proofs. As a special case, using a DDH based two-round OT protocol (e.g., [54]), this work yields the first two-round malicious MPC protocol in the common random string model under the DDH assumption.
Concurrent Work to [41]. In a concurrent and independent work to [41], Benhamouda and Lin [17] also construct two-round secure multiparty computation from two-round oblivious transfer. Their construction against semi-honest adversaries is proven under the minimal assumption that two-round, semi-honest oblivious transfer exists. However, their construction against malicious adversaries additionally requires the existence of non-interactive zero-knowledge proofs. In the plain model, they also provide a construction of a five-round maliciously secure MPC from five-round maliciously secure oblivious transfer. In another concurrent work, Boyle et al. [21] obtain a construction of two-round multiparty computation based on DDH in the public key infrastructure model.
1.2 Subsequent Works
The idea of “garbled protocols” introduced in this work has been used in the subsequent works of Ananth et al. [2, 3], Applebaum et al. [5, 6], Garg et al. [39] to give an unconditionally secure protocol for computing \({\mathsf {NC}}^1\) circuits in the honest majority setting. This problem has been open for nearly two decades [47]. The two-round semi-honest MPC protocol (which can be shown to be semi-malicious secure if underlying OT is semi-malicious secure) has been used in the works by Badrinarayanan et al. [10] and Choudari et al. [32] to construct round-optimal MPC protocol in the plain model from minimal cryptographic hardness assumptions. The protocol given in this work makes non-black-box use of a two-round oblivious transfer. This non-black-box access has been shown to be necessary by Applebaum et al. [4] who gave a black-box separation between two-round oblivious transfer and two-round secure MPC. The techniques introduced have also led to the development of two-round MPC protocols (using a strong form of setup) that make black-box use of a DDH-hard group (or, a QR-hard group) in [39]. In another sequence of works, Benhamouda and Lin [18] and Bartusek et al. [13] expanded our techniques to construct two-round MPC protocols where the first message could be reused many times to compute different functions on the same input.
2 Technical Overview
Towards demonstrating the intuition behind our result, in this section, we show how to reduce the round complexity of a very simple “toy” protocol to two. Additionally, we sketch how these ideas extend to the general setting and also work in the malicious case. We postpone the details to later sections.
Background: “Garbled Circuits that talk.”. The starting point of this work is the construction of a two-round MPC by Gordon et al. [45] based on Witness encryption [38]. Building on [36], the key idea behind [45] is a new method for enabling “garbled circuits to talk.” It is natural to imagine how “garbled circuits that can talk” might be useful for reducing the round complexity of any protocol. By employing this technique, a party can avoid multiple rounds of interaction just by sending a garbled circuit that interacts with the other parties on its behalf. At a technical level, a garbled circuit can “speak” by just outputting a value. However, the idea of enabling garbled circuits to “listen” without incurring any additional interaction poses new challenges. A bit more precisely, “listen” means that a garbled circuit can take as input a bit obtained via a joint computation on its secret state and the secret states of two or more other parties.
In [45], this idea was implemented by a witness encryption scheme. The key contribution of this work is a realization of the intuition of “garbled circuits that talk” using any two-round OT protocols rather than the heavy hammer of general-purpose witness encryption. At the heart of our construction is the following novel use of two-round OT protocols: in our MPC protocol multiple instances of the underlying two-round OT protocol are executed and the secret receiver’s random coins used in some of these executed OT instances are revealed to the other parties. As we explain later, this is done carefully so that the security of the MPC protocol is not jeopardized.
A “toy” protocol for successive ANDs. Stripping away the technical details, we highlight our core new idea in the context of a “toy” example, where a garbled circuit will need to listen to one bit. Later, we briefly sketch how this core idea can be used to reduce the round complexity of any arbitrary round MPC protocol to two. Recall that, in one-round, each party sends a message depending on its secret state and the messages received in prior rounds.
Consider three parties \(P_1, P_2\), and \(P_3\) with inputs \(\alpha ,\beta ,\) and \(\gamma\) (which are single bits), respectively. Can we realize a protocol such that the parties learn \(f(\alpha ,\beta ,\gamma) = (\alpha ,\alpha \wedge \beta ,\alpha \wedge \beta \wedge \gamma)\) and nothing more? Can we realize a two-round protocol for the same task? Here is a very simple three-round information theoretic protocol \(\Phi\) (in the semi-honest setting) for this task: In the first round, \(P_1\) sends its input \(\alpha\) to \(P_2\) and \(P_3\). In the second round, \(P_2\) computes \(\delta = \alpha \wedge \beta\) and sends it to \(P_1\) and \(P_3\). Finally, in the third round, \(P_3\) computes \(\gamma \wedge \delta\) and sends it to \(P_1\) and \(P_2\).
Compiling \(\Phi\) into a two-round protocol. The key challenge that we face is that the third party’s message depends on the second party’s message, and the second party’s message depends on the first party’s message. We will now describe our approach to overcome this three-way dependence using two-round oblivious transfer and thus, transform this protocol \(\Phi\) into a two-round protocol.
We assume the following notation for a two-round OT protocol. In the first round, the receiver with choice bit \(\beta\) generates \(c = \mathsf {OT}_1(\beta ;\omega)\) using \(\omega\) as the randomness and passes c to the sender. Then in the second round, the sender responds with its OT response \(d = \mathsf {OT}_2(c, s_0,s_1)\) where \(s_0\) and \(s_1\) are its input strings. Finally, using the OT response d and its randomness \(\omega\), the receiver recovers \(s_\beta\). In our protocol below, we will use a circuit \(C[\gamma ]\) that has a bit \(\gamma\) hardwired in it and that on input a bit \(\delta\) outputs \(\gamma \wedge \delta\). At a high level in our protocol, we will have \(P_2\) and \(P_3\) send extra messages in the first and the second rounds, respectively, so that the third-round can be avoided. Here is our protocol:
—
Round 1:\(P_1\) sends \(\alpha\) to \(P_2\) and \(P_3\). \(P_2\) prepares \(c_0 = \mathsf {OT}_1(0 \wedge \beta ; \omega _0)\) and \(c_1 = \mathsf {OT}_1(1 \wedge \beta ; \omega _1)\) and sends \((c_0,c_1)\) to \(P_2\) and \(P_3\).
—
Round 2:\(P_2\) sends \((\alpha \wedge \beta ,\omega _\alpha)\) to \(P_1\) and \(P_3\). \(P_3\) garbles \(\mathsf {C}[\gamma ]\) obtaining \(\tilde{\mathsf {C}}\) and input labels \(\mathsf {lab}_0\) and \(\mathsf {lab}_1\). It computes \(d = \mathsf {OT}_2 (c_\alpha , \mathsf {lab}_0,\mathsf {lab}_1)\) and sends \((\tilde{\mathsf {C}},d)\) to \(P_1\) and \(P_2\).
—
Output Evaluation: Every party recovers \(\mathsf {lab}_{\delta }\) where \(\delta = \alpha \wedge \beta\) from d using \(\omega _\alpha\). Next, it evaluates the garbled circuit \(\tilde{\mathsf {C}}\) using \(\mathsf {lab}_\delta\) which outputs \(\gamma \wedge \delta\) as desired.
Intuitively, in the protocol above \(P_2\) sends two first OT messages \(c_0\) and \(c_1\) that are prepared assuming \(\alpha\) is 0 and assuming \(\alpha\) is 1, respectively. Note that \(P_3\) does not know \(\alpha\) at the beginning of the first-round, but \(P_3\) does know it at the end of the first-round. Thus, \(P_3\) just uses \(c_\alpha\) while discarding \(c_{1-\alpha }\) in preparing its messages for the second-round. This achieves the three-way dependency while only using two-rounds. Furthermore, \(P_2\)’s second-round message reveals the randomness \(\omega _\alpha\) enabling all parties (and not just \(P_2\) and \(P_3\)) to obtain the label \(\mathsf {lab}_\delta\) which can then be used for the evaluation of \(\tilde{\mathsf {C}}\). In summary, via this mechanism, the garbled circuit \(\tilde{\mathsf {C}}\) was able to “listen” to the bit \(\delta\) that \(P_3\) did not know when generating the garbled circuit.
The above description highlights our ideas for reducing the round complexity of an incredibly simple toy protocol where only one bit was being “listened to.” Moreover, the garbled circuit “speaks” or outputs \(\gamma \wedge \delta\), which is obtained by all parties. In the above “toy” example, \(P_3\)’s garbled circuit computes a gate that takes only one bit as input. To compute a gate with two bit inputs, \(P_2\) will need to send four first OT messages in the first round instead of two.
Squashing arbitrary protocols. Our approach to enable garbled circuits to “listen to” a larger number of bits with complex dependencies is as follows. We show that any MPC protocol \(\Phi\) between parties \(P_1,\cdots P_n\) can be transformed into one satisfying the following format. First, the parties execute a pre-processing step; namely, each party \(P_i\) computes some randomized function of its input \(x_i\) obtaining public value \(z_i\) which is shared with everyone else, and private value \(v_i\). \(z_i\) is roughly an encryption of \(x_i\) using randomness from \(v_i\) as a one-time pad. \(v_i\) also contains random bits that will be used as a one-time pad to encrypt bits sent later by \(P_i\). Second, each party sets its local state \(\mathsf {st}_i = (z_1\Vert \ldots \Vert z_n) \oplus v_i\). This places us at the beginning of the protocol execution phase. In our transformed protocol \(\Phi\) can be written as a sequence of Tactions. For each \(t \in [T]\), the \(t^{th}\) action \(\phi _t = (i,f, g,h)\) involves party \(P_i\) computing one\(\mathsf {NAND}\) gate; it sets \(\mathsf {st}_{i,h} = \mathsf {NAND}(\mathsf {st}_{i,f} , \mathsf {st}_{i,g})\) and sends \(v_{i,h}\oplus \mathsf {st}_{i,h}\) to all the other parties. Our transformed protocol is such that for any bit \(\mathsf {st}_{i,h}\), the bit \(v_{i,h}\) is unique and acts as the one-time pad to hide it from the other parties. (Some of the bits in \(v_{i}\) are set to 0. These bits do not need to be hidden from other parties.) To complete this action, each party \(P_j\) for \(j \ne i\) sets \(\mathsf {st}_{j,h}\) to be the received bit. After all the actions are completed, each party \(P_j\) outputs a function of its local state \(\mathsf {st}_j\). In this transformed MPC protocol, in any round, only one bit is sent based on just one gate (i.e., the gate obtained as \(v_{i,h}\oplus \mathsf {NAND}(\mathsf {st}_{i,f}, \mathsf {st}_{i,g})\) with inputs \(\mathsf {st}_{i,f}\) and \(\mathsf {st}_{i,g}\), where \(v_{i,h}\) is hardwired inside it) computation on two bits. Thus, we can use the above “toy” protocol to achieve this effect.
To squash the round complexity of this transformed protocol, in the first round, we will have each party follow the pre-processing step from above along with a bunch of carefully crafted first OT messages as in our “toy” protocol. In the second round, parties will send a garbled circuit that is expected to “speak” and “listen” to the garbled circuits of the other parties. So when \(\phi _1 = (i,f,g,h)\) is executed, we have that the garbled circuit sent by party \(P_i\) speaks and all the others listen. Each of these listening garbled circuits uses our “toy” protocol idea from above. After completion of the first action, all the garbled circuits will have read the transcript of communication (which is just the one bit communicated in the first action \(\phi _1\)). Next, the parties need to execute action \(\phi _2= (i,f,g,h)\) and this is done like the first action, and the process continues. This completes the main idea of our construction. Building on this idea, we obtain a compiler that assuming semi-honest two-round OT transforms any semi-honest MPC protocol into a two-round semi-honest MPC protocol. Furthermore, if the assumed semi-honest two-round OT protocol is in the plain model then so will be the resulting MPC protocol.
Compilation in the Malicious Case. The protocol ideas described above only achieve semi-honest security and additional use of non-interactive zero-knowledge (NIZK) proofs [19, 35] is required to upgrade security to malicious [9, 51]. This has been the case for all known two-round MPC protocol constructions. In a bit more detail, by using NIZKs parties can (without increasing the round complexity) prove in zero-knowledge that they are following protocol specifications. The use of NIZKs might seem essential to such protocols. However, we show that this can be avoided. Our main idea is as follows: instead of proving that the garbled circuits are honestly generated, we require that the garbled circuits prove to each other that the messages they send are honestly generated. Since our garbled circuits can “speak” and “listen” over several rounds without increasing the round complexity of the squished protocol, we can instead use an interactive zero-knowledge proof system and avoid NIZKs. Building on this idea, we obtain two-round MPC protocols secure against malicious adversaries by instantiating the compiler with a two-round oblivious transfer that is secure against malicious adversaries (which exists in the CRS model).3 Somewhat surprisingly, the security of the protocol is maintained even when the garbled circuits are generated incorrectly. This is because the first round receiver OT messages generated by the adversarial parties “commits” to the cheating strategy in the larger round protocol. The garbled circuits generated in the second round simply executes this cheating strategy and hence, we need not prove that the garbled circuits are generated correctly. We elaborate on this new idea and other issues involved in subsequent sections.
3 Preliminaries
We recall some standard cryptographic definitions in this section. Let \(\lambda\) denote the security parameter. A function \(\mu (\cdot) : \mathbb {N} \rightarrow \mathbb {R}^+\) is said to be negligible if for any polynomial \(\mathsf {poly}(\cdot)\) there exists \(\lambda _0\) such that for all \(\lambda \gt \lambda _0\), we have \(\mu (\lambda) \lt \frac{1}{\mathsf {poly}(\lambda)}\). We will use \(\mathsf {negl}(\cdot)\) to denote an unspecified negligible function and \(\mathsf {poly}(\cdot)\) to denote an unspecified polynomial function.
For a probabilistic algorithm A, we denote \(A(x;r)\) to be the output of A on input x with the content of the random tape being r. When r is omitted, \(A(x)\) denotes a distribution. For a finite set S, we denote \(x \leftarrow S\) as the process of sampling x uniformly from the set S. We will use PPT to denote the Probabilistic Polynomial Time algorithm.
3.1 Garbled Circuits
Below we recall the definition of garbling scheme for circuits [57] (see Applebaum et al. [7, 8], Lindell and Pinkas [50] and Bellare et al. [15] for a detailed proof and further discussion). A garbling scheme for circuits is a tuple of PPT algorithms \((\mathsf {Garble}, \mathsf {Eval})\). \(\mathsf {Garble}\) is the circuit garbling procedure and \(\mathsf {Eval}\) is the corresponding evaluation procedure. More formally:
—
\((\widetilde{\mathsf {C}},\lbrace \mathsf {lab}_{w,b}\rbrace _{w\in \mathsf {inp}(C), b\in \lbrace 0,1\rbrace }) \leftarrow \mathsf {Garble}(1^\lambda , C)\): \(\mathsf {Garble}\) takes as input a security parameter \(1^\lambda\), a circuit C, and outputs a garbled circuit\(\widetilde{\mathsf {C}}\) along with labels \(\mathsf {lab}_{w,b}\) where \(w\in \mathsf {inp}(C)\) (\(\mathsf {inp}(C)\) is the set of input wires of C) and \(b \in \lbrace 0,1\rbrace\). Each label \(\mathsf {lab}_{w,b}\) is assumed to be in \(\lbrace 0,1\rbrace ^\lambda\).
—
\(y\leftarrow \mathsf {Eval}(\widetilde{\mathsf {C}}, \lbrace \mathsf {lab}_{w,{x}_w}\rbrace _{w\in \mathsf {inp}(C)})\): Given a garbled circuit \(\widetilde{\mathsf {C}}\) and a sequence of input labels \(\lbrace \mathsf {lab}_{w,{x}_w}\rbrace _{w\in \mathsf {inp}(C)}\) (referred to as the garbled input), \(\mathsf {Eval}\) outputs a string y.
Correctness. For correctness, we require that for any circuit C and input \({x} \in \lbrace 0,1\rbrace ^{|\mathsf {inp}(C)|}\) we have that:
Security. For security, we require that there exists a PPT simulator \(\mathsf {Sim}\) such that for any circuit C and input \({x} \in \lbrace 0,1\rbrace ^{|\mathsf {inp}(C)|}\), we have that
where \((\widetilde{\mathsf {C}}, \lbrace \mathsf {lab}_{w,b}\rbrace _{w\in \mathsf {inp}(C), b\in \lbrace 0,1\rbrace }) \leftarrow \mathsf {Garble}(1^{\lambda },C)\) and \(\overset{c}{\approx }\) denotes that the two distributions are computationally indistinguishable.
Authenticity of Input labels. We require for any circuit C and input \(x \in \lbrace 0,1\rbrace ^{|\mathsf {inp}(C)|}\) and any PPT adversary \(\mathcal {A}\), the probability that the following game outputs 1 is negligible.
We can add authenticity of input labels property generically to any garbled circuit construction by digitally signing every input label and including the verification key as part of the garbled circuit \(\widetilde{C}\).
3.2 Universal Composability Framework
We work in the Universal Composition (UC) framework [26] to formalize and analyze the security of our protocols. (Our protocols can also be analyzed in the stand-alone setting, using the composability framework of [24], or in other UC-like frameworks, like that of [55].) We refer the reader to Appendix A for a brief overview of the model and to [25] for details.
3.3 Oblivious Transfer
In this article, we consider a 1-out-of-2 OT protocol, similar to [1, 23, 34, 46, 52] where one party, the sender, has input composed of two strings \((s_0, s_1)\) and the input of the second party, the receiver, is a bit \(\beta\). The receiver should learn \(s_{\beta }\) and nothing regarding \(s_{1-\beta }\) while the sender should gain no information about \(\beta\).
Security of the OT functionality can be described easily by an ideal functionality \(\mathsf {F}_\mathsf {OT}\) as is done in [31]. However, in our constructions, the receiver needs to reveal the randomness (or a part of the randomness) it uses in an instance of two-round OT to other parties. Therefore, defining security as an ideal functionality requires care and raises issues similar to one involved in defining ideal public-key encryption functionality [28, Page 96] arise. Thus, in our context, it is much easier to directly work with a two-round OT protocol. We define the syntax and the security guarantees of a two-round OT protocol below.
Semi-Honest Two-round Oblivious Transfer. A two-round semi-honest OT protocol \(\langle S,R\rangle\) is defined by three probabilistic algorithms \((\mathsf {OT}_1,\mathsf {OT}_2,\mathsf {OT}_3)\) as follows. The receiver runs the algorithm \(\mathsf {OT}_1\) which takes the security parameter \(1^\lambda\), and the receiver’s input \(\beta \in \lbrace 0,1\rbrace\) as input and outputs \(\mathsf {ots}_1\) and \(\omega\).4 The receiver then sends \(\mathsf {ots}_1\) to the sender, who obtains \(\mathsf {ots}_2\) by evaluating \(\mathsf {OT}_2(\mathsf {ots}_1, (s_0, s_1))\), where \(s_0, s_1 \in \lbrace 0,1\rbrace ^{\lambda }\) are the sender’s input messages. The sender then sends \(\mathsf {ots}_2\) to the receiver who obtains \(s_\beta\) by evaluating \(\mathsf {OT}_3(\mathsf {ots}_2, (\beta , \omega))\).
—
Correctness. For every choice bit \(\beta \in \lbrace 0,1\rbrace\) of the receiver and input messages \(s_0\) and \(s_1\) of the sender we require that, if \(({\mathsf {ots}}_1, \omega) \leftarrow \mathsf {OT}_1(1^\lambda ,\beta)\), \({\mathsf {ots}}_2 \leftarrow \mathsf {OT}_2({\mathsf {ots}}_1, (s_0, s_1))\), then \(\mathsf {OT}_3({\mathsf {ots}}_2,(\beta ,\omega)) = s_\beta\) with overwhelming probability.
Sender’s security. We require that for any choice of \(\beta \in \lbrace 0,1\rbrace\), overwhelming choices of \(\omega ^{\prime }\) and any strings \(K_0,K_1,L_0,L_1 \in \lbrace 0,1\rbrace ^\lambda\) with \(K_{\beta }=L_{\beta }\), we have that
where \(({\mathsf {ots}}_1,\omega) :=\mathsf {OT}_1(1^\lambda , \beta ;\omega ^{\prime }).\)
Constructions of semi-honest two-round OT are known in the plain model under assumptions such as DDH [1, 16, 52], quadratic residuosity [46] and LWE [54, 56].
Maliciously Secure Two-round Oblivious Transfer. We consider the stronger notion of oblivious transfer in the common random/reference string model. In terms of syntax, we supplement the syntax of semi-honest oblivious transfer with an algorithm \(K_\mathsf {OT}\) that takes the security parameter \(1^\lambda\) as input and outputs the common random/reference string \(\sigma\). Also, the three algorithms \(\mathsf {OT}_1,\mathsf {OT}_2\), and \(\mathsf {OT}_3\) additionally take \(\sigma\) as input. Correctness and receiver’s security properties in the malicious case are the same as the semi-honest case. However, we strengthen the sender’s security as described below.
—
Correctness. For every choice bit \(\beta \in \lbrace 0,1\rbrace\) of the receiver and input messages \(s_0\) and \(s_1\) of the sender we require that, if \(\sigma \leftarrow K_\mathsf {OT}(1^\lambda)\), \(({\mathsf {ots}}_1, \omega) \leftarrow \mathsf {OT}_1(\sigma ,\beta)\), \({\mathsf {ots}}_2 \leftarrow \mathsf {OT}_2(\sigma ,{\mathsf {ots}}_1, (s_0, s_1))\), then \(\mathsf {OT}_3(\sigma ,{\mathsf {ots}}_2,(\beta ,\omega)) = s_\beta\) with overwhelming probability.
Sender’s security. We require the existence of PPT algorithm \({\mathsf {Ext}} = ({\mathsf {Ext}}_1, {\mathsf {Ext}}_2)\) such that for any choice of \(K_0, K_1 \in \lbrace 0,1\rbrace ^\lambda\) and PPT adversary \(\mathcal {A}\) we have that
Constructions of maliciously secure two-round OT are known in the common random string model under assumptions such as DDH, quadratic residuosity, and LWE [54].
Equivocal Receiver’s Security. We also consider a strengthened notion of malicious receiver’s security where we require the existence of a PPT simulator \(\mathsf {Sim}_{Eq}\) such that the for any \(\beta \in \lbrace 0,1\rbrace\):
Using standard techniques in the literature (e.g., [31]) it is possible to add equivocal receiver’s security to any OT protocol. We sketch a construction in Appendix B for completeness. We note that if an OT protocol has equivocal receiver security then it satisfies standard simulation security against malicious senders. The transformation given in Appendix B gives a method to bootstrap indistinguishability based security to standard simulation security.
4 Conforming Protocols
Our protocol compilers work for protocols satisfying certain syntactic structures. We refer to protocols satisfying this syntax as conforming protocols. In this subsection, we describe this notion and prove that any MPC protocol can be transformed into a conforming protocol while preserving its correctness and security properties.
4.1 Specifications for a Conforming Protocol
Consider an n party deterministic5 MPC protocol \(\Phi\) between parties \(P_1, \ldots , P_n\) with inputs \(x_1, \ldots , x_n\), respectively. For each \(i \in [n]\), we let \(x_i \in \lbrace 0,1\rbrace ^m\) denote the input of party \(P_i\). A conforming protocol \(\Phi\) is defined by functions \(\mathsf {pre}\), \(\mathsf {post}\), and computations steps or what we call actions\(\phi _1,\cdots \phi _T\). The protocol \(\Phi\) proceeds in three stages: the pre-processing stage, the computation stage and the output stage.
—
Pre-processing phase: For each \(i \in [n]\), party \(P_i\) computes
where \(\mathsf {pre}\) is a randomized algorithm. The algorithm \(\mathsf {pre}\) takes as input the index i of the party, its input \(x_i\) and outputs \(z_i \in \lbrace 0,1\rbrace ^{\ell /n}\) and \(v_i \in \lbrace 0,1\rbrace ^\ell\) (where \(\ell\) is a parameter of the protocol). Finally, \(P_i\) retains \(v_i\) as the secret information and broadcasts \(z_i\) to every other party. We require that \(v_{i,k} = 0\) for all \(k \in [\ell ]\backslash \left\lbrace (i-1)\ell /n +1, \ldots , i\ell /n\right\rbrace\).
—
Computation phase: For each \(i \in [n]\), party \(P_i\) sets
and broadcasts \(\mathsf {st}_{i,h} \oplus v_{i,h}\) to every other party.
(3)
Every party \(P_j\) for \(j \ne i\) updates \(\mathsf {st}_{j,h}\) to the bit value received from \(P_i\).
We require that for all \(t, t^{\prime } \in [T]\) such that \(t \ne t^{\prime }\), we have that if \(\phi _t = (\cdot ,\cdot ,\cdot ,h)\) and \(\phi _{t^{\prime }} = (\cdot ,\cdot ,\cdot ,h^{\prime })\) then \(h \ne h^{\prime }\). Also, we denote \(A_i \subset [T]\) to be the set of rounds in with party \(P_i\) sends a bit. Namely, \(A_i = \left\lbrace t \in T\mid \phi _t = (i, \cdot , \cdot , \cdot)\right\rbrace .\)
—
Output phase: For each \(i \in [n]\), party \(P_i\) outputs \(\mathsf {post}(\mathsf {st}_i)\).
4.2 Transformation for Making a Protocol Conforming
We show that any MPC protocol can be made conforming by making only some syntactic changes. Our transformed protocols retain the correctness or security properties of the original protocol.
Lemma 4.1.
Any MPC protocol \(\Pi\) can be written as a conforming protocol \(\Phi\) while inheriting the correctness and the security of the original protocol.
Proof.
Let \(\Pi\) be any given MPC protocol. Without loss of generality we assume that in each round of \(\Pi\), one party broadcasts one bit that is obtained by computing a circuit on its initial state and the messages it has received so far from other parties. Note that this restriction can be easily enforced by increasing the round complexity of the protocol to the communication complexity of the protocol. Let the round complexity (and also communication complexity) of \(\Pi\) be p. In every round \(r \in [p]\) of \(\Pi\), a single bit is sent by one of the parties by computing a circuit. Let the circuit computed in round r be \(C_r\). Without loss of generality, we assume that (i) these exists q such that for each \(r \in [p]\), we have that \(q = |C_r|\), (ii) each \(C_r\) is composed of just NAND gates with fan-in two, and (iii) each party sends an equal number of bits in the execution of \(\Pi\). All three of these conditions can be met by adding dummy gates and a dummy round of interaction.
We are now ready to describe our transformed conforming protocol \(\Phi\). The protocol \(\Phi\) will have \(T = pq\) rounds. We let \(\ell = mn + pq\) and \(\ell ^{\prime } = pq/n\) and depending on \(\ell\) the compiled protocol \(\Phi\) is as follows:
—
\(\mathsf {pre}(i,x_i)\): Sample \(r_i \leftarrow \lbrace 0,1\rbrace ^{m}\) and \(s_i \leftarrow (\lbrace 0,1\rbrace ^{q-1}\Vert 0)^{p/n}\). (Observe that \(s_i\) is a \(pq/n\) bit random string such that its \(q^{th}, 2q^{th}\cdots\) locations are set to 0.) Output \(z_i := x_i \oplus r_i \Vert 0^{\ell ^{\prime }}\) and \(v_i := 0^{\ell /n} \Vert \ldots \Vert r_{i}\Vert s_i \Vert \ldots \Vert 0^{\ell /n}\).
—
We are now ready to describe the actions \(\phi _1,\cdots \phi _T\). For each \(r \in [p]\), round r in \(\Pi\) party is expanded into q actions in \(\Phi\) — namely, actions \(\lbrace \phi _j\rbrace _j\) where \(j \in \lbrace (r-1) q + 1 \cdots r q\rbrace\). Let \(P_{i}\) be the party that computes the circuit \(C_r\) and broadcasts the output bit broadcast in round r of \(\Pi\). We now describe the \(\phi _{j}\) for \(j \in \lbrace (r-1) q + 1 \cdots r q\rbrace\). For each j, we set \(\phi _j = (i, f,g,h)\) where f and g are the locations in \(\mathsf {st}_{i}\) that the \(j^{th}\) gate of \(C_r\) is computed on (recall that initially \(\mathsf {st}_i\) is set to \(z_i \oplus v_i\)). Moreover, we set h to be the first location in \(\mathsf {st}_i\) among the locations \((i-1)\ell /n + m+ 1\) to \(i\ell /n\) that has previously not been assigned to an action. (Note that this is \(\ell ^{\prime }\) locations which is exactly equal to the number of bits computed and broadcast by \(P_i\).)
Recall from before than on the execution of \(\phi _j\), party \(P_{i}\) sets \(\mathsf {st}_{i,h} := \mathsf {NAND}(\mathsf {st}_{i,{f}},\mathsf {st}_{i,{g}})\) and broadcasts \(\mathsf {st}_{i,h}\oplus v_{i,h}\) to all parties.
—
\(\mathsf {post}(i,\mathsf {st}_i)\): Gather the local state of \(P_i\) and the messages sent by the other parties in \(\Pi\) from \(\mathsf {st}_i\) and output the output of \(\Pi\).
Now we need to argue that \(\Phi\) preserves the correctness and security properties of \(\Pi\). Observe that \(\Phi\) is essentially the same as the protocol \(\Pi\) except that in \(\Phi\) some additional bits are sent. Specifically, in addition to the messages that were sent in \(\Pi\), in \(\Phi\) parties send \(z_i\) in the preprocessing step and \(q-1\) additional bit per every bit sent in \(\Pi\). Note that these additional bits sent are not used in the computation of \(\Phi\). Thus these bits do not affect the functionality of \(\Pi\) if dropped. This ensures that \(\Phi\) inherits the correctness properties of \(\Pi\). Next note that each of these bits is masked by a uniform independent bit. This ensures that \(\Phi\) achieves the same security properties as the underlying properties of \(\Pi\).
Finally, note that by construction for all \(t, t^{\prime } \in [T]\) such that \(t \ne t^{\prime }\), we have that if \(\phi _t = (\cdot ,\cdot ,\cdot ,h)\) and \(\phi _{t^{\prime }} = (\cdot ,\cdot ,\cdot ,h^{\prime })\) then \(h \ne h^{\prime }\) as required.□
5 Two-round MPC: Semi-Honest Case
In this section, we give our construction of two-round multiparty computation protocol in the semi-honest case with security against static corruptions based on any two-round semi-honest oblivious transfer protocol in the plain model. This is achieved by designing a compiler that takes any conforming arbitrary (polynomial) round MPC protocol \(\Phi\) and squashes it to two rounds.
5.1 Our Compiler
We give our construction of a two-round MPC in Figure 1 and the circuit that needs to be garbled (repeatedly) is shown in Figure 2. We start by providing intuition behind this construction.
Fig. 1.
Fig. 1. Two-round semi-honest MPC.
Fig. 2.
Fig. 2. The program \(\textsf {Prog}_{}\).
5.1.1 Overview.
In the first round of the compiled protocol, each party runs the pre-processing phase of the conforming protocol to obtain \(z_i\) and \(v_i\). The party sends \(z_i\) to every party and retains \(v_i\). In addition to this message, each party generates a bunch of receiver OT messages in the first round and broadcasts it to the other parties. For each round t where the party \(P_i\) is sending a message in the conforming protocol with \(\phi _t = (i,f,g,h)\) being the corresponding action, the party generates 4 OT messages. Specifically, for each \(\alpha ,\beta \in \lbrace 0,1\rbrace\), \(P_i\) computes a receiver OT message with \(v_{i,h} \oplus \mathsf {NAND}(v_{i,f}\oplus \alpha ,v_{i,g} \oplus \beta)\) as its choice bit. \(z_i\) together with these receiver OT messages correspond to the first round message of the compiled protocol.
In the second round of the compiled protocol, each party generates a bunch of garbled circuits and sends these to the other parties. Specifically, for each round of the conforming protocol, there is one garbled circuit that is generated by each party. The role of these garbled circuits is to emulate the computation done in the conforming protocol. Consider some round t of the conforming protocol with \(\phi _t = (i,f,g,h)\) being the action corresponding to this round. The garbled circuit generated by \(P_i\) for this round will perform the computation corresponding to the action and will output the result of this action. The other garbled circuits will need to “listen” to this output and update their states to include the message sent by \(P_i\). As mentioned in the introduction, the main challenge is to enable the other garbled circuits to listen to the message sent by \(P_i\) and this is where the first round OT messages will be helpful. Let us explain how the other garbled circuits listen to the message sent by \(P_i\).
Let us focus on round t of the protocol and let us assume that the input to the garbled circuits emulating round t is the correct updated state of the party at the end of round \(t-1\). We need to ensure that for each party, the inputs to its garbled circuit corresponding to round \(t + 1\) is the correct updated state at the end of round t. This task is easy to ensure for \(P_i\). This is because from its input, \(P_i\)’s garbled circuit can update the hth state bit as \(\mathsf {st}_{i,h} = \mathsf {NAND}(\mathsf {st}_{i,f},\mathsf {st}_{i,g})\) and output the labels for the round \(t+1\) garbled circuit corresponding to this updated state. Now, consider some party \(P_j\) for \(j \ne i\). The garbled circuit generated by this party must output the labels for the next garbled circuit that corresponds to the updated state at the end of round t. Since only the hth bit of the state is updated, let us focus on how this garbled circuit outputs the correct label corresponding to the hth bit of the state. Note that, if we set \(\alpha = \mathsf {st}_{j,f}\) and \(\beta = \mathsf {st}_{j,g}\) (where \(\mathsf {st}_j\) corresponds to the updated state at the end of round \(t-1\)), then the choice bit in the \((\alpha ,\beta)\)-th receiver OT message generated by \(P_i\) in the first round corresponds to the bit that is sent by \(P_i\) in the tth round. Thus, given the updated state at the end of round \(t-1\), the garbled circuit generated by \(P_j\) corresponding to round t computes a sender OT message w.r.t. the \((\alpha ,\beta)\)-th receiver OT message where the input strings correspond to the labels \(\mathsf {lab}_{h,0}\) and \(\mathsf {lab}_{h,1}\) for the next garbled circuit. To enable the decryption of this label, \(P_i\)’s garbled circuit additionally reveals the randomness used in generating the \((\alpha ,\beta)\)-th \(\mathsf {OT}\) message. Using the randomness and the sender OT message, each party can recover the label corresponding to the correct updated state of \(P_j\).
We stress that this process of revealing the randomness of the OT leads to a complete loss of security for the particular instance OT. Nevertheless, since the randomness of only one of the four OT messages of \(P_{i}\) is reveled, overall security is ensured. In particular, our construction ensures that the learned choice bit is in fact the message that is broadcasted in the underlying protocol \(\Phi\). Thus, it follows from the security of the protocol \(\Phi\) that learning this message does not cause any vulnerabilities.
Theorem 5.1.
Let \(\Phi\) be a polynomial round, n-party semi-honest MPC protocol computing a function \(f: (\lbrace 0,1\rbrace ^m)^n \rightarrow \lbrace 0,1\rbrace ^*\), \((\mathsf {Garble},\mathsf {Eval})\) be a garbling scheme for circuits, and \((\mathsf {OT}_1, \mathsf {OT}_2, \mathsf {OT}_3)\) be a semi-honest two-round OT protocol. The protocol described in Figure 1 is a two-round, n-party semi-honest MPC protocol computing f against static corruptions.
The rest of the section is devoted to proving this theorem.
5.2 Correctness
In order to prove correctness, it is sufficient to show that the label computed in Step 2. (d). (ii) of the evaluation procedure corresponds to the bit \(\mathsf {NAND}(\mathsf {st}_{i^*,f},\mathsf {st}_{i^*,g}) \oplus v_{i^*,h}\). Notice that by the assumption on the structure of \(v_{i^*}\) (recall that \(v_{i^*}\) is such that \(v_{i^*,k} = 0\) for all \(k \in [\ell ]\backslash \left\lbrace (i^*-1)\ell /n +1,\ldots , i^*\ell /n\right\rbrace\)) we deduce that for every \(i \ne i^*\), \(\mathsf {st}_{i,f} = \mathsf {st}_{i^*,f} \oplus v_{i^*,f}\) and \(\mathsf {st}_{i,g} = \mathsf {st}_{i^*,g} \oplus v_{i^*,g}\). Thus, the label obtained by \({\mathsf {OT}_2}\) corresponds to the bit \(\mathsf {NAND}(v_{i^*,f}\oplus \underbrace{\mathsf {st}_{i^*,f} \oplus v_{i^*,f}}_\alpha ,v_{i^*,g} \oplus \underbrace{\mathsf {st}_{i^*,g}\oplus v_{i^*,g}}_\beta) \oplus v_{i^*,h} = \mathsf {NAND}(\mathsf {st}_{i^*,f},\mathsf {st}_{i^*,g}) \oplus v_{i^*,h}\) and correctness as follows:
Via the same argument as above it is useful to keep in mind that for every \(i,j \in [n]\) and \(k \in [\ell ]\), we have that \(\mathsf {st}_{i,k} \oplus v_{i,k} = \mathsf {st}_{j,k} \oplus v_{j,k}\). Let us denote this shared value by \(\mathsf {st}^*\). Also, we denote the transcript of the interaction in the computation phase by \(\mathsf {Z}\in \lbrace 0,1\rbrace ^t\).
5.3 Simulator
Let \(\mathcal {A}\) be a semi-honest adversary corrupting a subset of parties and let \(H \subseteq [n]\) be the set of honest/uncorrupted parties. Since we assume that the adversary is static, this set is fixed before the execution of the protocol. Below we provide the simulator.
Description of the Simulator. We give the description of the ideal world adversary \(\mathcal {S}\) that simulates the view of the real-world adversary \(\mathcal {A}\). \(\mathcal {S}\) will internally use the semi-honest simulator \(\mathsf {Sim}_{\Phi }\) for \(\Phi\) and the simulator \(\mathsf {Sim}_\mathsf {G}\) for garbling scheme for circuits. Recall that \(\mathcal {A}\) is static and hence the set of honest parties H is known before the execution of the protocol.
Simulating the interaction with \(\mathcal {Z}\). For every input value for the set of corrupted parties that \(\mathcal {S}\) receives from \(\mathcal {Z}\), \(\mathcal {S}\) writes that value to \(\mathcal {A}\)’s input tape. Similarly, the output of \(\mathcal {A}\) is written as the output on \(\mathcal {S}\)’s output tape.
Simulating the interaction with \(\mathcal {A}\). For every concurrent interaction with the session identifier \(\mathsf {sid}\) that \(\mathcal {A}\) may start, the simulator does the following:
—
Initialization: \(\mathcal {S}\) uses the inputs of the corrupted parties \(\lbrace x_i\rbrace _{i \not\in H}\) and output y of the functionality f to generate a simulated view of the adversary.6 More formally, for each \(i \in [n]\setminus H\)\(\mathcal {S}\) sends \((\mathsf {input}, \mathsf {sid}, \lbrace P_1\cdots P_n\rbrace , P_i, x_i)\) to the ideal functionality implementing f and obtains the output y. Next, it executes \(\mathsf {Sim}_{\Phi }(1^{\lambda },\lbrace x_i\rbrace _{i \not\in H}, y)\) to obtain \(\lbrace z_i\rbrace _{i \in H},\) the random tapes for the corrupted parties, the transcript of the computation phase denoted by \(\mathsf {Z} \in \lbrace 0,1\rbrace ^t\) where \(\mathsf {Z}_t\) is the bit sent in the tth round of the computation phase of \(\Phi\), and the value \(\mathsf {st}^*\) (which for each \(i \in [n]\) and \(k \in [\ell ]\) is equal to \(\mathsf {st}_{i,k} \oplus v_{i,k}\)). \(\mathcal {S}\) starts the real-world adversary \(\mathcal {A}\) with the inputs \(\lbrace z_i\rbrace _{i \in H}\) and random tape generated by \(\mathsf {Sim}_\Phi\).
—
Round-1 messages from \(\mathcal {S}\) to \(\mathcal {A}\): Next \(\mathcal {S}\) generates the OT messages on behalf of honest parties as follows. For each \(i \in H, t \in A_i, \alpha , \beta \in \lbrace 0,1\rbrace\), generate \({\mathsf {ots}}_{1,t,\alpha ,\beta } \leftarrow \mathsf {OT}_1(1^\lambda ,\mathsf {Z}_t;\omega _{t,\alpha ,\beta })\). For each \(i \in H\), \(\mathcal {S}\) sends \((z_i, \lbrace {\mathsf {ots}}_{1,t, \alpha ,\beta }\rbrace _{t \in A_i, \alpha , \beta \in \lbrace 0,1\rbrace })\) to the adversary \(\mathcal {A}\) on behalf of the honest party \(P_i\).
—
Round-1 messages from \(\mathcal {A}\) to \(\mathcal {S}\): Corresponding to every \(i \in [n]\setminus H\), \(\mathcal {S}\) receives from the adversary \(\mathcal {A}\) the value \((z_i, \lbrace {\mathsf {ots}}_{1,t,\alpha ,\beta }\rbrace _{t \in A_i, \alpha , \beta \in \lbrace 0,1\rbrace })\) on behalf of the corrupted party \(P_i\).
—
Round-2 messages from \(\mathcal {S}\) to \(\mathcal {A}\): For each \(i \in H\), the simulator \(\mathcal {S}\) generates the second round message on behalf of party \(P_i\) as follows:
(1)
For each \(k \in [\ell ]\) set \({\mathsf {lab}}_{k}^{i,T+1} := 0^\lambda\).
(2)
\({\bf for}\) each t from T down to 1,
(a)
Parse \(\phi _t\) as \((i^*,f,g,h)\).
(b)
Set \(\alpha ^*:= \mathsf {st}^*_{f}\), \(\beta ^*:= \mathsf {st}^*_{g}\), and \(\gamma ^*:= \mathsf {st}^*_{h}\).
If \(i \ne i^*\) then set \({\mathsf {ots}}^i_{2,t,\alpha ^*,\beta ^*} \leftarrow \mathsf {OT}_2({\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*},{\mathsf {lab}}^{i,t+1}_{h},{\mathsf {lab}}^{i,t+1}_{h})\) and compute
Send \(\big (\lbrace \widetilde{\textsf {Prog}}^{i,t}\rbrace _{t \in [T]},\lbrace {\mathsf {lab}}^{i,1}_{k}\rbrace _{k \in [\ell ]} \big)\) to every other party.
—
Round-2 messages from \(\mathcal {A}\) to \(\mathcal {S}\): For every, \(i \in [n]\setminus H\), \(\mathcal {S}\) obtains the second round message from \(\mathcal {A}\) on behalf of the malicious parties. Subsequent to obtaining these messages, for each \(i \in H,\)\(\mathcal {S}\) sends \((\mathsf {generateOutput},\mathsf {sid},\lbrace P_1\cdots P_n\rbrace , P_i)\) to the ideal functionality.
5.4 Proof of Indistinguishability
We now show that no environment \(\mathcal {Z}\) can distinguish whether it is interacting with a real-world adversary \(\mathcal {A}\) or an ideal world adversary \(\mathcal {S}\). We prove this via a hybrid argument with \(T+1\) hybrids.
—
\(\mathcal {H}_{Real}\): This hybrid is the same as the real-world execution. Note that this hybrid is the same as hybrid \(\mathcal {H}_t\) below with \(t=0\).
—
\(\mathcal {H}_t\) (where \(t \in \lbrace 0,\ldots T\rbrace\)): Hybrid \(\mathcal {H}_t\) (for \(t \in \lbrace 1\cdots T\rbrace\)) is the same as hybrid \(\mathcal {H}_{t-1}\) except we change the distribution of the OT messages (both from the first and the second round of the protocol) and the garbled circuits (from the second round) that play a role in the execution of the tth round of the protocol \(\Phi\); namely, the action \(\phi _t = (i^*,f,g,h)\). We describe the changes more formally below.
We start by executing the protocol \(\Phi\) on the inputs and the random coins of the honest and the corrupted parties. This yields a transcript \(\mathsf {Z} \in \lbrace 0,1\rbrace ^T\) of the computation phase. Since the adversary is assumed to be semi-honest the execution of the protocol \(\Phi\) with \(\mathcal {A}\) will be consistent with \(\mathsf {Z}\). Let \(\mathsf {st}^*\) be the local state of the end of execution. Finally, let \(\alpha ^* := \mathsf {st}^*_{f}\), \(\beta ^* := \mathsf {st}^*_{g}\) and \(\gamma ^* := \mathsf {st}^*_{h}\). In hybrid \(\mathcal {H}_t\) we make the following changes with respect to hybrid \(\mathcal {H}_{t-1}\):
•
If \(i^* \not\in H\) then skip these changes. \(\mathcal {S}\) makes two changes in how it generates messages on behalf of \(P_{i^*}\). First, for all \(\alpha ,\beta \in \lbrace 0,1\rbrace\), \(\mathcal {S}\) generates \({\mathsf {ots}}_{1,t,\alpha ,\beta }\) as \(\mathsf {OT}_1(1^\lambda , \mathsf {Z}_t; \omega _{t,\alpha ,\beta })\) (note that only one of these four values is subsequently used) rather than \(\mathsf {OT}_1(1^\lambda , v_{i,h} \oplus \mathsf {NAND}(v_{i,f} \oplus \alpha , v_{i,g} \oplus \beta);\omega _{t,\alpha ,\beta })\). Second, it generates the garbled circuit
where \(\lbrace {\mathsf {lab}}_{k, \mathsf {st}_{i,k}}^{i^*,t+1}\rbrace _{k \in [\ell ]}\) are the honestly generates input labels for the garbled circuit \(\widetilde{\textsf {Prog}}^{i^*,t+1}\).
•
\(\mathcal {S}\) makes the following two changes in how it generates messages for other honest parties \(P_i\) (i.e., \(i \in H\setminus \lbrace i^*\rbrace\)). \(\mathcal {S}\) does not generate four \({\mathsf {ots}}_{2,t,\alpha ,\beta }^i\) values but just one of them; namely, \(\mathcal {S}\) generates the values \({\mathsf {ots}}_{2,t,\alpha ^*,\beta ^*}^i\) as \(\mathsf {OT}_2({\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*},{\mathsf {lab}}^{i,t+1}_{h,\mathsf {Z}_t}, {\mathsf {lab}}^{i,t+1}_{h,\mathsf {Z}_t})\) rather than \(\mathsf {OT}_2({\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*},{\mathsf {lab}}^{i,t+1}_{h,0}, {\mathsf {lab}}^{i,t+1}_{h,1})\). Second it generates the garbled circuit
where \(\lbrace {\mathsf {lab}}_{k,\mathsf {st}_{i,k}}^{i,t+1}\rbrace _{k \in [\ell ]}\) are the honestly generated input labels for the garbled circuit \(\widetilde{\textsf {Prog}}^{i,t+1}\).
Indistinguishability between \(\mathcal {H}_{t-1}\) and \(\mathcal {H}_{t}\) is proved in Lemma 5.2.
—
\(\mathcal {H}_{T+1}\): In this hybrid, we just change how the transcript \(\mathsf {Z}\), \(\lbrace z_{i}\rbrace _{i\in H}\), random coins of malicious parties, and value \(\mathsf {st}^*\) are generated. Instead of generating these using honest party inputs we generate these values by executing the simulator \(\mathsf {Sim}_\Phi\) on input \(\left\lbrace x_i \right\rbrace _{i \in [n]\setminus H}\) and the output y obtained from the ideal functionality.
The indistinguishability between hybrids \(\mathcal {H}^{\prime }_T\) and \(\mathcal {H}_{T+1}\) follows directly from the semi-honest security of the protocol \(\Phi\). Finally note that \(\mathcal {H}_{T+1}\) is same as the ideal execution (i.e., the simulator described in the previous subsection).
Lemma 5.2.
Assuming semi-honest security of the two-round OT protocol and the security of the garbling scheme, for all \(t \in \lbrace 1\ldots T\rbrace\) hybrids \(\mathcal {H}_{t-1}\) and \(\mathcal {H}_{t}\) are computationally indistinguishable.
Proof.
Using the same notation as before, let \(\phi _t = (i^*,f,g,h)\), \(\mathsf {st}_{i^*}\) be the state of \(P_{i^*}\) at the end of round t, and \(\alpha ^* := \mathsf {st}_{i^*,f}\oplus v_{i^*,f}\), \(\beta ^* := \mathsf {st}_{i^*,g}\oplus v_{i^*,g}\) and \(\gamma ^* := \mathsf {st}_{i^*,h} \oplus v_{i^*,h}\). The indistinguishability between hybrids \(\mathcal {H}_{t-1}\) and \(\mathcal {H}_{t}\) follows by a sequence of three sub-hybrids \(\mathcal {H}_{t,1}\), \(\mathcal {H}_{t,2}\), and \(\mathcal {H}_{t,3}\).
—
\(\mathcal {H}_{t,1}\): Hybrid \(\mathcal {H}_{t,1}\) is same as hybrid \(\mathcal {H}_{t-1}\) except that \(\mathcal {S}\) now generates the garbled circuits \(\widetilde{\textsf {Prog}}^{i,t}\) for each \(i \in H\) in a simulated manner (rather than generating them honestly). Specifically, instead of generating each garbled circuit and input labels \((\widetilde{\textsf {Prog}}^{i,t},\lbrace {{\mathsf {lab}}}^{i,t}_{k}\rbrace _{k\in [\ell ]})\) honestly, they are generated via the simulator by hard coding the output of the circuit itself. In a bit more details, parse \(\phi _t\) as \((i^*,f,g,h)\).
where \(\lbrace {\mathsf {lab}}_{k, \mathsf {st}_{i,k}}^{i,t+1}\rbrace _{k \in [\ell ]}\) are the honestly generates input labels for the garbled circuit \(\widetilde{\textsf {Prog}}^{i,t+1}\).
where \(\lbrace {\mathsf {lab}}_{k,\mathsf {st}_{i,k}}^{i,t+1}\rbrace _{k \in [\ell ]}\) are the honestly generated input labels for the garbled circuit \(\widetilde{\textsf {Prog}}^{i,t+1}\).
The indistinguishability between hybrids \(\mathcal {H}_{t,1}\) and \(\mathcal {H}_{t-1}\) follows by \(|H|\) invocations of security of the garbling scheme. For completeness, we give the proof of indistinguishability in Appendix C.
—
\(\mathcal {H}_{t,2}\): Skip this hybrid if there does not exist \(i \ne i^*\) such that \(i \in H\). In this hybrid, we change how \(\mathcal {S}\) generates the \({\mathsf {ots}}_{2,t,\alpha ,\beta }^i\) on behalf of every honest party \(P_i\) such that \(i \in H\setminus \lbrace i^*\rbrace\) for all choices of \(\alpha ,\beta \in \lbrace 0,1\rbrace\). More specifically, \(\mathcal {S}\) only generates one of these four values; namely, \({\mathsf {ots}}_{2,t,\alpha ^*,\beta ^*}^i\) which is now generated as \(\mathsf {OT}_2({\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*},{\mathsf {lab}}^{i,t+1}_{h,\mathsf {Z}_t}, {\mathsf {lab}}^{i,t+1}_{h,\mathsf {Z}_t})\) instead of \(\mathsf {OT}_2({\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*},{\mathsf {lab}}^{i,t+1}_{h,0}, {\mathsf {lab}}^{i,t+1}_{h,1})\).
Indistinguishability between hybrids \(\mathcal {H}_{t,2}\) and \(\mathcal {H}_{t,1}\) follows directly from the sender’s security of underlying semi-honest oblivious transfer protocol.
—
\(\mathcal {H}_{t,3}\): Skip this hybrid, if \(i^* \not\in H\). This hybrid is the same as \(\mathcal {H}_{t,2}\) except that we change how \(\mathcal {S}\) generates the Round-1 message on behalf of \(P_{i^*}\). Specifically, the simulator \(\mathcal {S}\) generates \({\mathsf {ots}}_{1,t,\alpha ,\beta }\) as is done in the \(\mathcal {H}_t\). In a bit more detail, for all \(\alpha ,\beta \in \lbrace 0,1\rbrace\), \(\mathcal {S}\) generates \({\mathsf {ots}}_{1,t,\alpha ,\beta }\) as \(\mathsf {OT}_1(1^\lambda ,\mathsf {Z}_t; \omega _{t,\alpha ,\beta })\) rather than \(\mathsf {OT}_1(1^\lambda ,v_{i,h} \oplus \mathsf {NAND}(v_{i,f} \oplus \alpha , v_{i,g} \oplus \beta);\omega _{t,\alpha ,\beta })\).
Indistinguishability between hybrids \(\mathcal {H}_{t,2}\) and \(\mathcal {H}_{t,3}\) follows directly by a sequence of 3 sub-hybrids each one relying on the receiver’s security of underlying semi-honest oblivious transfer protocol. Observe here that the security reduction crucially relies on the fact that \(\widetilde{\textsf {Prog}}^{i,t}\) only contains \(\omega _{t,\alpha ^*,\beta ^*}\) (i.e., does not have \(\omega _{t,\alpha ,\beta }\) for \(\alpha \ne \alpha ^*\) or \(\beta \ne \beta ^*\)). For completeness, we give the proof of indistinguishability in Appendix C.
Finally, observe that \(\mathcal {H}_{t,3}\) is the same as hybrid \(\mathcal {H}_{t}\).□
6 Two-round MPC: Malicious Case
In this section, we give our construction of a two-round multiparty computation protocol in the malicious case with security against static corruptions based on any two-round malicious oblivious transfer protocol (with equivocal receiver security which as argued earlier can be added with a need for any additional assumptions). This is achieved by designing a compiler that takes any conforming arbitrary (polynomial) round MPC protocol \(\Phi\) and squashes it to two rounds.
6.1 Our Compiler
We give our construction of two-round MPC in Figure 3 and the circuit that needs to be garbled (repeatedly) is shown in Figure 2 (same as the semi-honest case). We start by providing intuition behind this construction. Our compiler is essentially the same as the semi-honest case. In addition to the minor syntactic changes, the main difference is that we compile malicious secure conforming protocols instead of semi-honest ones.
Fig. 3.
Fig. 3. Two-round malicious MPC.
Another technical issue arises because the adversary may wait to receive the first round messages that \(\mathcal {S}\) sends on the behalf of honest parties before sending the first round messages on behalf of the corrupted parties. Recall that by sending the receiver OT messages in the first round, every party “commits” to all its future messages that it will send in the computation phase of the protocol. Thus, the ideal world simulator \(\mathcal {S}\) must somehow commit to the messages generated on behalf of the honest party before extracting the adversary’s effective input. To get around this issue, we use the equivocability property of the OT using which the simulator can equivocate its first round messages after learning the malicious adversary’s effective input.
Theorem 6.1.
Let \(\Phi\) be a polynomial round, n-party malicious MPC protocol computing a function \(f: (\lbrace 0,1\rbrace ^m)^n \rightarrow \lbrace 0,1\rbrace ^*\), \((\mathsf {Garble},\mathsf {Eval})\) be a garbling scheme for circuits, and \((K_\mathsf {OT},\mathsf {OT}_1, \mathsf {OT}_2, \mathsf {OT}_3)\) be a maliciously secure (with equivocal receiver security) two-round OT protocol. The protocol described in Figure 3 is a two-round, n-party malicious MPC protocol computing f against static corruptions.
We prove the security of our compiler in the rest of the section. The proof of correctness is the same as for the case of semi-honest security (see Section 5.2).
As in the semi-honest case, it is useful to keep in mind that for every \(i,j \in [n]\) and \(k \in [\ell ]\), we have that \(\mathsf {st}_{i,k} \oplus v_{i,k} = \mathsf {st}_{j,k} \oplus v_{j,k}\). Let us denote this shared value by \(\mathsf {st}^*\). Also, we denote the transcript of the interaction in the computation phase by \(\mathsf {Z}\in \lbrace 0,1\rbrace ^t\).
6.2 Simulator
Let \(\mathcal {A}\) be a malicious adversary corrupting a subset of parties and let \(H \subseteq [n]\) be the set of honest/uncorrupted parties. Since we assume that the adversary is static, this set is fixed before the execution of the protocol. Below we provide the notion of faithful execution and then describe our simulator.
Faithful Execution. In the first round of our compiled protocol, \(\mathcal {A}\) provides \(z_i\) for every \(i \in [n]\setminus H\) and \({\mathsf {ots}}_{1,t,\alpha ,\beta }\) for every \(t \in \cup _{i \in [n]\setminus h}\) and \(\alpha ,\beta \in \lbrace 0,1\rbrace\). These values act as “binding” commitments to all of the adversary’s future choices. All these committed choices can be extracted using the extractor \({\mathsf {Ext}}_2\). Let \(b_{t,\alpha ,\beta }\) be the value extracted from \({\mathsf {ots}}_{1,t,\alpha ,\beta }\). Intuitively speaking, a faithful execution is an execution that is consistent with these extracted values.
More formally, we define an interactive procedure \(\mathsf {Faithful}(i, \lbrace z_i\rbrace _{i \in [n]}, \lbrace b_{t,\alpha ,\beta }\rbrace _{t \in A_i,\alpha ,\beta })\) that on input \(i \in [n]\), \(\lbrace z_i\rbrace _{i \in [n]}\), \(\lbrace b_{t,\alpha ,\beta }\rbrace _{t\in A_i,\alpha ,\beta \in \lbrace 0,1\rbrace }\) produces protocol \(\Phi\) message on behalf of party \(P_i\) (acting consistently/faithfully with the extracted values) as follows:
(1)
Set \(\mathsf {st}^* := z_1 \Vert \ldots \Vert z_n\).
(2)
For \(t \in \left\lbrace 1\cdots T \right\rbrace\)
(a)
Parse \(\phi _t = (i^*,f,g,h)\).
(b)
If \(i \ne i^*\) then it waits for a bit from \(P_{i^*}\) and sets \(\mathsf {st}_{h}^*\) to be the received bit once it is received.
(c)
Set \({\mathsf {st}}^*_h := b_{t,\mathsf {st}_{f}^*,{\mathsf {st}}_{g}^*}\) and output it to all the other parties.
We will later argue that any deviation from the faithful execution by the adversary \(\mathcal {A}\) on behalf of the corrupted parties (during the second round of our compiled protocol) will be detected. Additionally, we prove that such deviations do not hurt the security of the honest parties.
Description of the Simulator. We give the description of the ideal world adversary \(\mathcal {S}\) that simulates the view of the real-world adversary \(\mathcal {A}\). \(\mathcal {S}\) will internally use the malicious simulator \(\mathsf {Sim}_{\Phi }\) for \(\Phi\), the extractor \({\mathsf {Ext}} = ({\mathsf {Ext}}_1,{\mathsf {Ext}}_2)\) implied by the sender security of two-round OT, the simulator \(\mathsf {Sim}_{Eq}\) implied by the equivocal receiver’s security and the simulator \(\mathsf {Sim}_\mathsf {G}\) for garbling scheme for circuits. Recall that \(\mathcal {A}\) is static and hence the set of honest parties H is known before the execution of the protocol.
Simulating the interaction with \(\mathcal {Z}\). For every input value for the set of corrupted parties that \(\mathcal {S}\) receives from \(\mathcal {Z}\), \(\mathcal {S}\) writes that value to \(\mathcal {A}\)’s input tape. Similarly, the output of \(\mathcal {A}\) is written as the output on \(\mathcal {S}\)’s output tape.
Simulating the interaction with \(\mathcal {A}\). For every concurrent interaction with the session identifier \(\mathsf {sid}\) that \(\mathcal {A}\) may start, the simulator does the following:
—
Generation of the common random/reference string: \(\mathcal {S}\) generates the common random/reference string as follows:
(1)
For each \(i \in H, t \in A_i\), \(\alpha ,\beta \in \lbrace 0,1\rbrace\) set \((\sigma _{t,\alpha ,\beta }\), \(({\mathsf {ots}}_{1,t,\alpha ,\beta }\), \(\omega _{t,\alpha ,\beta }^0\), \(\omega _{t,\alpha ,\beta }^1)) \leftarrow \mathsf {Sim}_{Eq}(1^\lambda)\) (using equivocal simulator).
(2)
For each \(i \in [n]\setminus H,\alpha ,\beta \in \lbrace 0,1\rbrace\) and \(t \in A_i\) generate \((\sigma _{t,\alpha ,\beta }, \tau _{t,\alpha ,\beta }) \leftarrow {\mathsf {Ext}}_1(1^\lambda)\) (using the extractor of the OT protocol).
(3)
Output the common random/reference string as \(\lbrace \sigma _{t,\alpha ,\beta } \rbrace _{t,\alpha ,\beta }\).
—
Initialization: \(\mathcal {S}\) executes the simulator (against malicious adversary’s) \(\mathsf {Sim}_{\Phi }(1^{\lambda })\) to obtain \(\lbrace z_i\rbrace _{i \in H}\). Moreover, \(\mathcal {S}\) starts the real-world adversary \(\mathcal {A}\). We next describe how \(\mathcal {S}\) provides its messages to \(\mathsf {Sim}_\Phi\) and \(\mathcal {A}\).
—
Round-1 messages from \(\mathcal {S}\) to \(\mathcal {A}\): For each \(i \in H\), \(\mathcal {S}\) sends \((z_i, \lbrace {\mathsf {ots}}_{1,t, \alpha ,\beta }\rbrace _{t \in A_i, \alpha , \beta \in \lbrace 0,1\rbrace })\) to the adversary \(\mathcal {A}\) on behalf of the honest party \(P_i\).
—
Round-1 messages from \(\mathcal {A}\) to \(\mathcal {S}\): Corresponding to every \(i \in [n]\setminus H\), \(\mathcal {S}\) receives from the adversary \(\mathcal {A}\) the value \((z_i, \lbrace {\mathsf {ots}}_{1,t,\alpha ,\beta }\rbrace _{t \in A_i, \alpha , \beta \in \lbrace 0,1\rbrace })\) on behalf of the corrupted party \(P_i\). Next, for each \(i \in [n]\setminus H, t \in A_i, \alpha , \beta \in \lbrace 0,1\rbrace\) extract \(b_{t,\alpha ,\beta } := {\mathsf {Ext}}_2(\tau _{t,\alpha ,\beta }, {\mathsf {ots}}_{1,t,\alpha ,\beta })\).
—
Completing the execution with \(\mathsf {Sim}_\Phi\): For each \(i \in [n]\setminus H\), \(\mathcal {S}\) sends \(z_i\) to \(\mathsf {Sim}_\Phi\) on behalf of the corrupted party \(P_i\). This starts the computation phase of \(\Phi\) with the simulator \(\mathsf {Sim}_\Phi\). \(\mathcal {S}\) provides computation phase messages to \(\mathsf {Sim}_\Phi\) by following a faithful execution. More formally, for every corrupted party \(P_i\) where \(i \in [n]\setminus H\), \(\mathcal {S}\) generates messages on behalf of \(P_i\) for \(\mathsf {Sim}_\Phi\) using the procedure \(\mathsf {Faithful}(i,\lbrace z_i\rbrace _{i \in [n]}, \lbrace b_{t,\alpha ,\beta }\rbrace _{t \in A_i,\alpha ,\beta })\). At some point during the execution, \(\mathsf {Sim}_\Phi\) will return the extracted inputs \(\lbrace x_i\rbrace _{i \in [n]\setminus H}\) of the corrupted parties. For each \(i \in [n]\setminus H\), \(\mathcal {S}\) sends \((\mathsf {input}, \mathsf {sid}, \lbrace P_1\cdots P_n\rbrace , P_i, x_i)\) to the ideal functionality implementing f and obtains the output y which is provided to \(\mathsf {Sim}_\Phi\). Finally, at some point the faithful execution completes.
Let \(\mathsf {Z} \in \lbrace 0,1\rbrace ^t\) where \(\mathsf {Z}_t\) is the bit sent in the tth round of the computation phase of \(\Phi\) be the output of this execution. And let \(\mathsf {st}^*\) be the state value at the end of execution of one of the corrupted parties (this value is the same for all the parties). Also, set for each \(t \in \cup _{i \in H} A_i\) and \(\alpha ,\beta \in \lbrace 0,1\rbrace\) set \(\omega _{t,\alpha ,\beta } := \omega _{t,\alpha ,\beta }^{\mathsf {Z}_t}\).
—
Round-2 messages from \(\mathcal {S}\) to \(\mathcal {A}\): For each \(i \in H\), the simulator \(\mathcal {S}\) generates the second round message on behalf of party \(P_i\) as follows:
(1)
For each \(k \in [\ell ]\) set \({\mathsf {lab}}_{k}^{i,T+1} := 0^\lambda\).
(2)
\({\bf for}\) each t from T down to 1,
(a)
Parse \(\phi _t\) as \((i^*,f,g,h)\).
(b)
Set \(\alpha ^*:= \mathsf {st}^*_{f}\), \(\beta ^*:= \mathsf {st}^*_{g}\), and \(\gamma ^*:= \mathsf {st}^*_{h}\).
Send \((\lbrace \widetilde{\textsf {Prog}}^{i,t}\rbrace _{t \in [T]},\lbrace {\mathsf {lab}}^{i,1}_{k}\rbrace _{k \in [\ell ]})\) to every other party.
—
Round-2 messages from \(\mathcal {A}\) to \(\mathcal {S}\): For every \(i \in [n]\setminus H\), \(\mathcal {S}\) obtains the second-round message from \(\mathcal {A}\) on behalf of the malicious parties. Subsequent to obtaining these messages, \(\mathcal {S}\) executes the garbled circuits provided by \(\mathcal {A}\) on behalf of the corrupted parties to see the execution of garbled circuits proceeds consistently with the expected faithful execution. If the computation succeeds then for each \(i \in H,\)\(\mathcal {S}\) sends \((\mathsf {generateOutput},\mathsf {sid},\lbrace P_1\cdots P_n\rbrace , P_i)\) to the ideal functionality.
6.3 Proof of Indistinguishability
We now show that no environment \(\mathcal {Z}\) can distinguish whether it is interacting with a real-world adversary \(\mathcal {A}\) or an ideal world adversary \(\mathcal {S}\). We prove this via a hybrid argument with T + 3 hybrids.
—
\(\mathcal {H}_{Real}\): This hybrid is the same as the real-world execution.
—
\(\mathcal {H}_{0}\): In this hybrid, we start by changing the distribution of the CRS and the distribution of the sender OT messages of the honest parties generated w.r.t. a receiver OT message generated by a corrupt party. More formally, \(\mathcal {S}\) generates the common random/reference string as follows:
(1)
For each \(i \in [n]\setminus H,\alpha ,\beta \in \lbrace 0,1\rbrace\) and \(t \in A_i\) generate \((\sigma _{t,\alpha ,\beta }, \tau _{t,\alpha ,\beta }) \leftarrow {\mathsf {Ext}}_1(1^\lambda)\) (using the extractor of the OT protocol).
Corresponding to every \(i \in [n]\setminus H\), \(\mathcal {A}\) sends \((z_i, \lbrace {\mathsf {ots}}_{1,t,\alpha ,\beta }\rbrace _{t \in A_i, \alpha , \beta \in \lbrace 0,1\rbrace })\) on behalf of the corrupted party \(P_i\) as its first round message. For each \(i \in [n]\setminus H, t \in A_i, \alpha , \beta \in \lbrace 0,1\rbrace\) in this hybrid we extract \(b_{t,\alpha ,\beta } := {\mathsf {Ext}}_2(\tau _{t,\alpha ,\beta }, {\mathsf {ots}}_{1,t,\alpha ,\beta })\).
(2)
For each \(t \in [T]\) such that \(\phi _t = (i,f,g,h)\) where \(i \not\in H\), we change how \(\mathcal {S}\) generates the \({\mathsf {ots}}_{2,t,\alpha ,\beta }^i\) on behalf of every honest party \(P_i\) for all choices of \(\alpha ,\beta \in \lbrace 0,1\rbrace\). More specifically, \(\mathcal {S}\) generates this message as \(\mathsf {OT}_2(\sigma _{t,\alpha ,\beta }, {\mathsf {ots}}_{1,t,\alpha ,\beta },{\mathsf {lab}}^{i,t+1}_{h,b_{t,\alpha ,\beta }}, {\mathsf {lab}}^{i,t+1}_{h,b_{t,\alpha ,\beta }})\) instead of \(\mathsf {OT}_2(\sigma _{t,\alpha ,\beta }, {\mathsf {ots}}_{1,t,\alpha ,\beta },{\mathsf {lab}}^{i,t+1}_{h,0}, {\mathsf {lab}}^{i,t+1}_{h,1})\).
Note that, this hybrid is the same as hybrid \(\mathcal {H}_t\) below with \(t=0\).
The indistinguishability between hybrids \(\mathcal {H}_{Real}\) and \(\mathcal {H}_0\) follows from a reduction to the sender’s security of the two-round OT protocol.
—
\(\mathcal {H}_t\) (where \(t \in \lbrace 0,\ldots T\rbrace\)): Hybrid \(\mathcal {H}_t\) (for \(t \in \lbrace 1\cdots T\rbrace\)) is the same as hybrid \(\mathcal {H}_{t-1}\) except we change the distribution of the OT messages (both from the first and the second round of the protocol) and the garbled circuits (from the second round) that play a role in the execution of the tth round of the protocol \(\Phi\); namely, the action \(\phi _t = (i^*,f,g,h)\). We describe the changes more formally below.
For each \(i \in [n]\setminus H\), in this hybrid \(\mathcal {S}\) (in his head) completes execution of \(\Phi\) using honest party inputs and randomness. In this execution, the messages on behalf of corrupted parties are generated via faithful execution. Specifically, \(\mathcal {S}\) sends \(\lbrace z_i\rbrace _{i \in [n]\setminus H}\) to the honest parties on behalf of the corrupted party \(P_i\) in this mental execution of \(\Phi\). This starts the computation phase of \(\Phi\). In this computation phase, \(\mathcal {S}\) generates honest party messages using the inputs and random coins of the honest parties and generates the messages of the each malicious party \(P_i\) by executing \(\mathsf {Faithful} (i, \lbrace z_i\rbrace _{i \in [n]\setminus H}, \lbrace b_{t,\alpha ,\beta }\rbrace _{t \in A_i,\alpha ,\beta })\). Let \(\mathsf {st}^*\) be the local state of the end of execution. Finally, let \(\alpha ^* := \mathsf {st}^*_{f}\), \(\beta ^* := \mathsf {st}^*_{g}\) and \(\gamma ^* := \mathsf {st}^*_{h}\). In hybrid \(\mathcal {H}_t\) we make the following changes with respect to hybrid \(\mathcal {H}_{t-1}\):
•
If \(i^* \not\in H\) then skip these changes. \(\mathcal {S}\) makes two changes in how it generates messages on behalf of \(P_{i^*}\). First, for all \(\alpha ,\beta \in \lbrace 0,1\rbrace\), \(\mathcal {S}\) computes \((\sigma _{t,\alpha ,\beta }\), \(({\mathsf {ots}}_{1,t,\alpha ,\beta }, \omega _{t,\alpha ,\beta }^0, \omega _{t,\alpha ,\beta }^1)) \leftarrow \mathsf {Sim}_{Eq}(1^\lambda)\) (using equivocal simulator) and sets \(\omega _{t,\alpha ^*,\beta ^*}\) as \(\omega _{t,\alpha ^*,\beta ^*}^{\mathsf {Z}_t}\) rather than
\(\omega _{t,\alpha ^*,\beta ^*}^{v_{i,h} \oplus \mathsf {NAND}(v_{i,f} \oplus \alpha ^*, v_{i,g} \oplus \beta ^*)}\) (note that these two values are the same when using the honest party’s input and randomness). Second, it generates the garbled circuit
where \(\lbrace {\mathsf {lab}}_{k, \mathsf {st}_{i,k}}^{i^*,t+1}\rbrace _{k \in [\ell ]}\) are the honestly generates input labels for the garbled circuit \(\widetilde{\textsf {Prog}}^{i^*,t+1}\).
•
\(\mathcal {S}\) makes the following two changes in how it generates messages for other honest parties \(P_i\) (i.e., \(i \in H\setminus \lbrace i^*\rbrace\)). \(\mathcal {S}\) does not generate four \({\mathsf {ots}}_{2,t,\alpha ,\beta }^i\) values but just one of them; namely, \(\mathcal {S}\) generates the values \({\mathsf {ots}}_{2,t,\alpha ^*,\beta ^*}^i\) as \(\mathsf {OT}_2(\sigma _{t,\alpha ^*,\beta ^*}, {\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*},{\mathsf {lab}}^{i,t+1}_{h,\mathsf {Z}_t}, {\mathsf {lab}}^{i,t+1}_{h,\mathsf {Z}_t})\) rather than \(\mathsf {OT}_2(\sigma _{t,\alpha ^*,\beta ^*},{\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*},{\mathsf {lab}}^{i,t+1}_{h,0}, {\mathsf {lab}}^{i,t+1}_{h,1})\). Second it generates the garbled circuit
where \(\lbrace {\mathsf {lab}}_{k,\mathsf {st}_{i,k}}^{i,t+1}\rbrace _{k \in [\ell ]}\) are the honestly generated input labels for the garbled circuit \(\widetilde{\textsf {Prog}}^{i,t+1}\).
Indistinguishability between \(\mathcal {H}_{t-1}\) and \(\mathcal {H}_{t}\) is proved in Lemma 6.2
—
\(\mathcal {H}^{\prime }_T\!:\) In this hybrid, we modify the output phase of the computation to execute the garbled circuits provided by \(\mathcal {A}\) on behalf of the corrupted parties and see if the execution of garbled circuits proceeds consistently with the transcript \(\mathsf {Z}\). If the computation succeeds then for each \(i \in H,\) we instruct the parties in H to output y (which is the output obtained by all parties in the execution of \(\Phi\)); else, we instruct them to output \(\bot\). This hybrid is computationally close to \(\mathcal {H}_{T}\) from the authenticity property of the input labels.
—
\(\mathcal {H}_{T+1}\): In this hybrid, we just change how the transcript \(\mathsf {Z}\), \(\lbrace z_{i}\rbrace _{i\in H}\), random coins of malicious parties, and value \(\mathsf {st}^*\) are generated. Instead of generating these using honest party inputs in execution with a faithful execution of \(\Phi\), we generate it via the simulator \(\mathsf {Sim}_\Phi\) (of the maliciously secure protocol \(\Phi\)). In other words, we execute the simulator \(\mathsf {Sim}_\Phi\) where messages on behalf of each corrupted party \(P_i\) are generated using \(\mathsf {Faithful}(i,\lbrace z_i\rbrace _{i \in [n]\setminus H}, \lbrace b_{t,\alpha ,\beta }\rbrace _{t\in A_i,\alpha ,\beta })\). (Note that \(\mathsf {Sim}_\Phi\) might rewind \(\mathsf {Faithful}\). This can be achieved since \(\mathsf {Faithful}\) is just a polynomial time interactive procedure that can also be rewound.)
The indistinguishability between hybrids \(\mathcal {H}^{\prime }_T\) and \(\mathcal {H}_{T+1}\) follows directly from the malicious security of the protocol \(\Phi\). Finally, note that \(\mathcal {H}_{T+1}\) is same as the ideal execution (i.e., the simulator described in the previous subsection).
Lemma 6.2.
Assuming malicious security of the two-round OT protocol and the security of the garbling scheme, for all \(t \in \lbrace 1\ldots T\rbrace\) hybrids \(\mathcal {H}_{t-1}\) and \(\mathcal {H}_{t}\) are computationally indistinguishable.
Proof.
Using the same notation as before, let \(\phi _t = (i^*,f,g,h)\), \(\mathsf {st}_{i^*}\) be the state of \(P_{i^*}\) at the end of round t, and \(\alpha ^* := \mathsf {st}_{i^*,f}\oplus v_{i^*,f}\), \(\beta ^* := \mathsf {st}_{i^*,g}\oplus v_{i^*,g}\) and \(\gamma ^* := \mathsf {st}_{i^*,h} \oplus v_{i^*,h}\). The indistinguishability between hybrids \(\mathcal {H}_{t-1}\) and \(\mathcal {H}_{t}\) follows by a sequence of three sub-hybrids \(\mathcal {H}_{t,1}\), \(\mathcal {H}_{t,2}\), and \(\mathcal {H}_{t,3}\).
—
\(\mathcal {H}_{t,1}\): Hybrid \(\mathcal {H}_{t,1}\) is same as hybrid \(\mathcal {H}_{t-1}\) except that \(\mathcal {S}\) now generates the garbled circuits \(\widetilde{\textsf {Prog}}^{i,t}\) for each \(i \in H\) in a simulated manner (rather than generating them honestly). Specifically, instead of generating each garbled circuit and input labels \((\widetilde{\textsf {Prog}}^{i,t},\lbrace {{\mathsf {lab}}}^{i,t}_{k}\rbrace _{k\in [\ell ]})\) honestly, they are generated via the simulator by hard coding the output of the circuit itself. In a bit more details, parse \(\phi _t\) as \((i^*,f,g,h)\).
where \(\lbrace {\mathsf {lab}}_{k, \mathsf {st}_{i,k}}^{i,t+1}\rbrace _{k \in [\ell ]}\) are the honestly generates input labels for the garbled circuit \(\widetilde{\textsf {Prog}}^{i,t+1}\).
where \(\lbrace {\mathsf {lab}}_{k,\mathsf {st}_{i,k}}^{i,t+1}\rbrace _{k \in [\ell ]}\) are the honestly generated input labels for the garbled circuit \(\widetilde{\textsf {Prog}}^{i,t+1}\).
The indistinguishability between hybrids \(\mathcal {H}_{t,1}\) and \(\mathcal {H}_{t-1}\) follows by \(|H|\) invocations of security of the garbling scheme.
—
\(\mathcal {H}_{t,2}\): Skip this hybrid if there does not exist \(i \ne i^*\) such that \(i \in H\). In this hybrid, we change how \(\mathcal {S}\) generates the \({\mathsf {ots}}_{2,t,\alpha ,\beta }^i\) on behalf of every honest party \(P_i\) such that \(i \in H\setminus \lbrace i^*\rbrace\) for all choices of \(\alpha ,\beta \in \lbrace 0,1\rbrace\). More specifically, \(\mathcal {S}\) only generates one of these four values; namely, \({\mathsf {ots}}_{2,t,\alpha ^*,\beta ^*}^i\) which is now generated as \(\mathsf {OT}_2(\sigma _{t,\alpha ^*,\beta ^*}, {\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*},{\mathsf {lab}}^{i,t+1}_{h,\mathsf {Z}_t}, {\mathsf {lab}}^{i,t+1}_{h,\mathsf {Z}_t})\) instead of \(\mathsf {OT}_2(\sigma _{t,\alpha ^*,\beta ^*}, {\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*},{\mathsf {lab}}^{i,t+1}_{h,0}, {\mathsf {lab}}^{i,t+1}_{h,1})\).
In the case where \(i^* \not\in H\), this change is syntactic since we have already changed the distribution of \({\mathsf {ots}}^i_{2,t,\alpha ^*,\beta ^*}\) in \(\mathcal {H}_0\). In the case where \(i^* \in H\), indistinguishability between hybrids \(\mathcal {H}_{t,2}\) and \(\mathcal {H}_{t,1}\) follow directly from the sender’s security of underlying malicious oblivious transfer protocol. In fact, we only rely on the semi-honest security of the oblivious transfer to make this change.
—
\(\mathcal {H}_{t,3}\): Skip this hybrid, if \(i^* \not\in H\). This hybrid is same as \(\mathcal {H}_{t,2}\) except that we change how \(\mathcal {S}\) generates the Round-1 message on behalf of \(P_{i^*}\). Specifically, the simulator \(\mathcal {S}\) generates \({\mathsf {ots}}_{1,t,\alpha ,\beta }\) as is done in the \(\mathcal {H}_t\). In a bit more detail, computes \((\sigma _{t,\alpha ,\beta }\), \(({\mathsf {ots}}_{1,t,\alpha ,\beta }, \omega _{t,\alpha ,\beta }^0, \omega _{t,\alpha ,\beta }^1)) \leftarrow \mathsf {Sim}_{Eq}(1^\lambda)\) (using equivocal simulator) and sets \(\omega _{t,\alpha ^*,\beta ^*}\) as \(\omega _{t,\alpha ^*,\beta ^*}^{\mathsf {Z}_t}\) rather than \(\omega _{t,\alpha ^*,\beta ^*}^{v_{i,h} \oplus \mathsf {NAND}(v_{i,f} \oplus \alpha ^*, v_{i,g} \oplus \beta ^*)}\) (note that these two values are the same when using the honest party’s input and randomness).
We now argue indistinguishability between \(\mathcal {H}_{t,2}\) and \(\mathcal {H}_{t,3}\) using the equivocal receiver security. We interact with the equivocal security challenger four times. For each \(\alpha ,\beta\), we obtain \(\sigma _{t,\alpha ,\beta }, {\mathsf {ots}}_{1,t,\alpha ,\beta }\) and \(\omega ^{v_{i,h} \oplus \mathsf {NAND}(v_{i,f} \oplus \alpha , v_{i,g} \oplus \beta)}_{t,\alpha ,\beta }\). We use this to generate the first round message of the protocol and the second round messages of the protocol. Note that if these values were generated honestly then the distribution produced is identical to \(\mathcal {H}_{t,2}\). Else, it is distributed identically to \(\mathcal {H}_{t,3}\).
Finally, observe that \(\mathcal {H}_{t,3}\) is the same as hybrid \(\mathcal {H}_{t}\).□
Footnotes
1
The work of Boyle, Gilbova, and Ishai [20] provides a construction of two-round MPC for a constant number of parties from DDH.
2
Semi-malicious security is a strengthening of the semi-honest security wherein the adversary is allowed to choose its random tape arbitrarily. Ashrov et al. [9] showed that any protocol satisfying semi-malicious security could be upgraded to one with malicious security additionally using Non-Interactive Zero-Knowledge proofs (NIZKs).
3
For technical reasons detailed later, we need the two-round OT protocol to satisfy a stronger property called as equivocal receiver security. We give a transformation (in the CRS model) from any malicious secure OT to one that additionally satisfies equivocal receiver security.
4
We note that \(\omega\) in the output of \(\mathsf {OT}_1\) need not contain all the random coins used by \(\mathsf {OT}_1\). This fact will be useful in the stronger equivocal security notion of oblivious transfer.
5
Randomized protocols can be handled by including the randomness used by a party as part of its input.
6
For simplicity of exposition, we only consider the case where every party gets the same output. The proof in the more general case where parties get different outputs follows analogously.
A Our Model
Below we briefly review UC security. For full details see [26]. Most parts of this section are taken verbatim from [30]. A reader familiar with the notion of UC security can safely skip this section.
A.1 The Basic Model of Execution
Following [42, 44], a protocol is represented as an interactive Turing machine (ITM), which represents the program to be run within each participant. Specifically, an ITM has three tapes that can be written to by other ITMs: the input and subroutine output tapes model the inputs from and the outputs to other programs running within the same “entity” (say, the same physical computer), and the incoming communication tapes and outgoing communication tapes model messages received from and to be sent to the network. It also has an identity tape that cannot be written to by the ITM itself. The identity tape contains the program of the ITM (in some standard encoding) plus additional identifying information specified below. Adversarial entities are also modeled as ITMs.
We distinguish between ITMs (which represent static objects, or programs) and instances of ITMs, or ITIs, that represent interacting processes in a running system. Specifically, an ITI is an ITM along with an identifier that distinguishes it from other ITIs in the same system. The identifier consists of two parts: A session-identifier (SID) which identifies which protocol instance the ITM belongs to, and a party identifier (PID) that distinguishes among the parties in a protocol instance. Typically the PID is also used to associate ITIs with “parties”, or clusters, that represent some administrative domains or physical computers.
The model of computation consists of a number of ITIs that can write on each other’s tapes in certain ways (specified in the model). The pair (SID, PID) is a unique identifier of the ITI in the system.
With one exception (discussed within) we assume that all ITMs are probabilistic polynomial time (PPT). An ITM is PPT if there exists a constant \(c \gt 0\) such that, at any point during its run, the overall number of steps taken by M is at most \(n^c\), where n is the overall number of bits written on the input tape of M in this run. (In fact, in order to guarantee that the overall protocol execution process is bounded by a polynomial, we define n as the total number of bits written to the input tape of M, minus the overall number of bits written by M to input tapes of other ITMs.; see [26].)
A.2 Security of Protocols
Protocols that securely carry out a given task (or, protocol problem) are defined in three steps, as follows. First, the process of executing a protocol in an adversarial environment is formalized. Next, an “ideal process” for carrying out the task at hand is formalized. In the ideal process the parties, do not communicate with each other. Instead, they have access to an “ideal functionality,” which is essentially an incorruptible “trusted party” that is programmed to capture the desired functionality of the task at hand. A protocol is said to securely realize an ideal functionality if the process of running the protocol amounts to “emulating” the ideal process for that ideal functionality. Below we overview the model of protocol execution (called the real-life model), the ideal process, and the notion of protocol emulation.
The model for protocol execution. The model of computation consists of the parties running an instance of a protocol \(\Pi\), an adversary\(\mathcal {A}\) that controls the communication among the parties, and an environment\(\mathcal {Z}\) that controls the inputs to the parties and sees their outputs. We assume that all parties have a security parameter \(n \in \mathbb {N}\). (We remark that this is done merely for convenience and is not essential for the model to make sense). The execution consists of a sequence of activations, where in each activation a single participant (either \(\mathcal {Z}\), \(\mathcal {A}\), or some other ITM) is activated, and may write on a tape of at most one other participant, subject to the rules below. Once the activation of a participant is complete (i.e., once it enters a special waiting state), the participant whose tape was written on is activated next. (If no such party exists then the environment is activated next.)
The environment is given an external input z and is the first to be activated. In its first activation, the environment invokes the adversary \(\mathcal {A}\), providing it with some arbitrary input. In the context of UC security, the environment can from now on invoke (namely, provide input to) only ITMs that consist of a single instance of protocol \(\Pi\). That is, all the ITMs invoked by the environment must have the same SID and the code of \(\Pi\).
Once the adversary is activated, it may read its own tapes and the outgoing communication tapes of all parties. It may either deliver a message to some party by writing this message on the party’s incoming communication tape or report information to \(\mathcal {Z}\) by writing this information on the subroutine output tape of \(\mathcal {Z}\). For simplicity of exposition, in the rest of this article we assume authenticated communication; that is, the adversary may deliver only messages that were actually sent. (This is however not essential as shown in [11, 27].)
Once a protocol party (i.e., an ITI running \(\Pi\)) is activated, either due to an input given by the environment or due to a message delivered by the adversary, it follows its code and possibly writes a local output on the subroutine output tape of the environment, or an outgoing message on the adversary’s incoming communication tape.
In this work, we consider the setting of static corruptions. In the static corruption setting, the set of corrupted parties is determined at the start of the protocol execution and does not change during the execution.
The protocol execution ends when the environment halts. The output of the protocol execution is the output of the environment. Without loss of generality, we assume that this output consists of only a single bit.
Let \({\rm\small EXEC}_{\pi ,\mathcal {A},\mathcal {Z}}(n,z,r)\) denote the output of the environment \(\mathcal {Z}\) when interacting with parties running protocol \(\Pi\) on security parameter n, input z and random input \(r = r_\mathcal {Z}, r_\mathcal {A}, r_1, r_2, \ldots\) as described above (z and \(r_\mathcal {Z}\) for \(\mathcal {Z}\); \(r_\mathcal {A}\) for \(\mathcal {A}\), \(r_i\) for party \(P_i\)). Let \({\rm\small EXEC}_{\pi ,\mathcal {A},\mathcal {Z}}(n,z)\) random variable describing \({\rm\small EXEC}_{\pi ,\mathcal {A},\mathcal {Z}}(n,z,r)\) where r is uniformly chosen. Let \({\rm\small EXEC}_{\pi ,\mathcal {A},\mathcal {Z}}\) denote the ensemble \(\lbrace {\rm\small EXEC}_{\pi ,\mathcal {A},\mathcal {Z}}(n,z)\rbrace _{n \in \mathbb {N}, z \in \lbrace 0,1\rbrace ^*}\).
Ideal functionalities and ideal protocols. Security of protocols is defined via comparing the protocol execution to an ideal protocol for carrying out the task at hand. A key ingredient in the ideal protocol is the ideal functionality that captures the desired functionality, or the specification, of that task. The ideal functionality is modeled as another ITM (representing a “trusted party”) that interacts with the parties and the adversary. More specifically, in the ideal protocol for functionality \(\mathcal {F}\) all parties simply hand their inputs to an ITI running \(\mathcal {F}\). (We will simply call this ITI \(\mathcal {F}\). The SID of \(\mathcal {F}\) is the same as the SID of the ITIs running the ideal protocol. (the PID of \(\mathcal {F}\) is null.)) In addition, \(\mathcal {F}\) can interact with the adversary according to its code. Whenever \(\mathcal {F}\) outputs a value to a party, the party immediately copies this value to its own output tape. We call the parties in the ideal protocol dummy parties. Let \(\Pi (\mathcal {F})\) denote the ideal protocol for functionality \(\mathcal {F}\).
Securely realizing an ideal functionality. We say that a protocol \(\Pi\)emulates protocol \(\phi\) if for any adversary \(\mathcal {A}\) there exists an adversary \(\mathcal {S}\) such that no environment \(\mathcal {Z}\), on any input, can tell with non-negligible probability whether it is interacting with \(\mathcal {A}\) and parties running \(\Pi\), or it is interacting with S and parties running \(\phi\). This means that, from the point of view of the environment, running protocol \(\Pi\) is ‘just as good’ as interacting with \(\phi\). We say that \(\Pi\)securely realizes an ideal functionality \(\mathcal {F}\) if it emulates the ideal protocol \(\Pi (\mathcal {F})\). More precise definitions follow. A distribution ensemble is called binary if it consists of distributions over \(\lbrace 0,1\rbrace\).
Definition A.1.
Let \(\Pi\) and \(\phi\) be protocols. We say that \(\Pi\)UC-emulates\(\phi\) if for any adversary \(\mathcal {A}\) there exists an adversary \(\mathcal {S}\) such that for any environment \(\mathcal {Z}\) that obeys the rules of interaction for UC security we have \({\rm\small EXEC}_{\mathsf {F},\mathcal {S},\mathcal {Z}}\approx {\rm\small EXEC}_{\pi ,\mathcal {A},\mathcal {Z}}\).
Definition A.2.
Let \(\mathcal {F}\) be an ideal functionality and let \(\Pi\) be a protocol. We say that \(\Pi\)UC-realizes\(\mathcal {F}\) if \(\Pi\) UC-emulates the ideal process \(\Pi (\mathcal {F})\).
A.3 The Common Reference/Random String Functionality
In the common reference string (CRS) model [29, 31], all parties in the system obtained from a trusted party a reference string, which is sampled according to a pre-specified distribution D. The reference string is referred to as the CRS. In the UC framework, this is modeled by an ideal functionality \(\mathcal {F}_{CRS}^D\) that samples a string \(\rho\) from a pre-specified distribution D and sets \(\rho\) as the CRS. \(\mathcal {F}_{CRS}^D\) is described in Figure 4.
Fig. 4.
Fig. 4. The common reference string functionality.
When the distribution D in \(\mathcal {F}_{CRS}^D\) is sent to be the uniform distribution (on a string of appropriate length) then we obtain the common random string functionality denoted as \(\mathcal {F}_{CRS}\).
A.4 General Functionality
We consider the general-UC functionality \(\mathcal {F}\), which securely evaluates any polynomial-time (possibly randomize) function \(f: (\lbrace 0,1\rbrace ^{\ell _{in}})^n \rightarrow (\lbrace 0,1\rbrace ^{\ell _{out}})^n\). The functionality \(\mathcal {F}_f\) is parameterized with a function f and is described in Figure 5. In this article, we will only be concerned with the static corruption model.
Fig. 5.
Fig. 5. General functionality.
B Equivocal Receiver’s Security in Oblivious Transfer
Using standard techniques for the literature (e.g., [31]) it is possible to add equivocal receiver’s security to any OT protocol. We sketch a construction in below for the sake of completeness.
Lemma B.1.
Assuming two-round maliciously secure OT protocol, there exists a two-round maliciously secure OT protocol with equivocal receiver’s security.
Proof.
Given a two-round maliciously secure OT protocol \((K_\mathsf {OT}^{\prime },\mathsf {OT}_1^{\prime },\mathsf {OT}_2^{\prime },\mathsf {OT}_3^{\prime })\) we give a two-round maliciously secure OT protocol \((K_\mathsf {OT},\mathsf {OT}_1,\mathsf {OT}_2,\mathsf {OT}_3)\) that additionally achieves the equivocal receiver’s security. We also use a pseudorandom generator \(g: \lbrace 0,1\rbrace ^\lambda \rightarrow \lbrace 0,1\rbrace ^{3\lambda }\). Our construction is as follows:
\(\mathsf {OT}_2(\sigma = (\sigma ^{\prime }, r), {\mathsf {ots}}_1= (y, \lbrace {\mathsf {ots}}_{1,i}^0, {\mathsf {ots}}_{1,i}^1\rbrace _{i\in [\lambda ]}), (s_0,s_1))\): Let \(C_{y, s}\) be a circuit with \(y \in \lbrace 0,1\rbrace ^{3\lambda }\) and s hardwired in it which on input \(x\in \lbrace 0,1\rbrace ^\lambda\) outputs s if \(y = g(x)\) and \(\bot\) otherwise. \(\mathsf {OT}_2\) proceeds as follows:
The correctness of the above described OT protocol follows directly from the correctness of the underlying cryptographic primitives. We now prove sender security and equivocal receiver’s security.
Sender’s Security. The sender’s security of \((K_\mathsf {OT},\mathsf {OT}_1,\mathsf {OT}_2,\mathsf {OT}_3)\) follows from the sender’s security of \((K_\mathsf {OT}^{\prime },\mathsf {OT}_1^{\prime },\mathsf {OT}_2^{\prime },\mathsf {OT}_3^{\prime })\) and the simulation security of the garbling scheme. We start by describing the construction of \({\mathsf {Ext}} = ({\mathsf {Ext}}_1, {\mathsf {Ext}}_2)\) using the extractor \({\mathsf {Ext}}^{\prime } = ({\mathsf {Ext}}_1^{\prime }, {\mathsf {Ext}},_2^{\prime })\) for \((K_\mathsf {OT}^{\prime },\mathsf {OT}_1^{\prime },\mathsf {OT}_2^{\prime },\mathsf {OT}_3^{\prime })\).
—
\({\mathsf {Ext}}_1(1^\lambda)\) executes \((\sigma ^{\prime },\tau) \leftarrow {\mathsf {Ext}}_1^{\prime }(1^\lambda)\) and \(r \leftarrow \lbrace 0,1\rbrace ^{3\lambda }\) and outputs \(\sigma := (\sigma ^{\prime },r)\) and \(\tau\).
—
\({\mathsf {Ext}}_2(\tau , {\mathsf {ots}}_1 = (y, \lbrace {\mathsf {ots}}_{1,i}^0, {\mathsf {ots}}_{1,i}^1 \rbrace _{i \in [\lambda ]}))\) proceeds as follows: For each \(i \in [n]\), obtain \(x_{0,i} := {\mathsf {Ext}}_2^{\prime }(\tau ,{\mathsf {ots}}_{1,i})\). If \(g(x_0) = y\) then output 0 and 1 otherwise.
Now we argue that using this extractor \({\mathsf {Ext}} = ({\mathsf {Ext}}_1,{\mathsf {Ext}}_2)\), for any PPT adversary \(\mathcal {A}\), the distributions \(\text{IND}_\mathcal {A}^{\text{REAL}}(1^\lambda , K_0, K_1)\) and \(\text{IND}_\mathcal {A}^{\text{IDEAL}}(1^\lambda , K_0, K_1)\) are computationally indistinguishable. We argue this via the following sequence of hybrids.
—
\(\mathcal {H}_0\): This hybrid is the same as \(\text{IND}_\mathcal {A}^{\text{REAL}}(1^\lambda , K_0, K_1)\).
—
\(\mathcal {H}_1\): In this hybrid we change how the \(\sigma ^{\prime }\) in \(\sigma = (\sigma ^{\prime }, r)\) is generated. Specifically, we use the extractor \({\mathsf {Ext}}_1^{\prime }\) above to generate it. Additionally, we use \({\mathsf {Ext}}_2^{\prime }\) to recover a value of \(x_0\) and \(x_1\) that the receiver provides in \(\lbrace {\mathsf {ots}}_{1,i}^0\rbrace _{i\in [\lambda ]}\) and \(\lbrace {\mathsf {ots}}_{1,i}^1\rbrace _{i\in [\lambda ]}\), respectively.
Indistinguishability between \(\mathcal {H}_0\) and \(\mathcal {H}_1\) can be reduced directly to the sender’s security of the underlying OT protocol. Additionally, by a counting argument, we make the claim that for any \(x_0, x_1\) over the random choices of y we have that \(\Pr [g(x_0) = y \wedge g(x_1) = r\oplus y]\) is negligible. Thus, we set \(\beta = 0\) if \(g(x_0) = y\) and 1 otherwise. This is the same as the value extracted by \({\mathsf {Ext}}_2\) above.
—
\(\mathcal {H}_2\): In this hybrid, we change how the values \({\mathsf {ots}}_{2,i}^{1-\beta }\) are generated for each \(i \in [\lambda ]\). More specifically, for each \(i \in [\lambda ]\), we generate \({\mathsf {ots}}_{2,i}^{1-\beta }\leftarrow \mathsf {OT}_2(\sigma ^{\prime },{\mathsf {ots}}_{1,i}^{1-\beta }, (\mathsf {lab}_{i,x_{1-\beta ,i}}^{1-\beta },\mathsf {lab}_{i,x_{1-\beta ,i}}^{1-\beta }))\).
Indistinguishability between \(\mathcal {H}_1\) and \(\mathcal {H}_2\) can be reduced to the receiver’s security of the underlying OT protocol.
—
\(\mathcal {H}_3\): In this hybrid we change the garbled \(\widetilde{C}^{1-\beta }\) to the simulate circuit generated via \(\mathsf {Sim}_\mathsf {G}\) with the output \(\bot\) hardwired (i.e., it is generated as \(\mathsf {Sim}_\mathsf {G}(1^\lambda , \bot)\)).
Indistinguishability between \(\mathcal {H}_2\) and \(\mathcal {H}_3\) reduces to the security of the garbling scheme.
Equivocal Receiver’s Security. We start by providing the PPT simulator \(\mathsf {Sim}_{Eq}(1^\lambda)\) which proceeds as follows:
(1)
Generate \(\sigma ^{\prime } \leftarrow K^{\prime }_\mathsf {OT}(1^\lambda)\) and \(r := g(x_0)\oplus g(x_1)\) where \(x_0,x_1 \leftarrow \lbrace 0,1\rbrace ^\lambda\). Set \(\sigma := (\sigma ^{\prime }, r)\).
(2)
Sample \(x \leftarrow \lbrace 0,1\rbrace ^\lambda\). Set \(y := g(x_0)\).
(3)
For each \(i \in [\lambda ]\), prepare \(({\mathsf {ots}}_{1,i}^0,\omega _{i}^0) \leftarrow \mathsf {OT}_1^{\prime }(\sigma ^{\prime }, x_{0,i})\).
(4)
For each \(i \in [\lambda ]\), prepare \(({\mathsf {ots}}_{1,i}^1,\omega _{i}^1) \leftarrow \mathsf {OT}_1^{\prime }(\sigma ^{\prime }, x_{1,i})\).
We are left to argue that for each \(\beta\), the distribution \((\sigma , {\mathsf {ots}}_1, \omega _\beta)\) is indistinguishable from the distribution of the honestly generated values. We sketch the argument for the case where \(\beta =0\). The argument for the case where \(\beta = 1\) is analogous.
—
\(\mathcal {H}_0\): This hybrid corresponds to the real distribution. Namely, we set \(\sigma = (\sigma ^{\prime }, r) \leftarrow K_\mathsf {OT}(1^\lambda)\) and \(({\mathsf {ots}}_1 = (y, \lbrace {\mathsf {ots}}_{1,i}^0, {\mathsf {ots}}_{1,i}^1\rbrace _{i\in [\lambda ]}), \omega _\beta)\leftarrow \mathsf {OT}_1(\sigma , \beta)\).
—
\(\mathcal {H}_1\): In this hybrid, we change how r in generated. More specifically, we set r as \(g(x) \oplus g(x^{\prime })\) where \(x,x^{\prime } \leftarrow \lbrace 0,1\rbrace ^\lambda\) and use the same x in the generation of \({\mathsf {ots}}_1\).
Indistinguishability between hybrids \(\mathcal {H}_0\) and \(\mathcal {H}_1\) follows directly from the security of the pseudorandom generator.
—
\(\mathcal {H}_2\): In this hybrid, we change how \({\mathsf {ots}}_{1,i}^1\) values are generated. Specifically, for each \(i \in [\lambda ]\), we set \(({\mathsf {ots}}_{1,i}^1,\omega _{i}^1) \leftarrow \mathsf {OT}_1^{\prime }(\sigma ^{\prime }, x^{\prime }_i)\) instead of \(({\mathsf {ots}}_{1,i}^1,\omega _{i}^1) \leftarrow \mathsf {OT}_1^{\prime }(\sigma ^{\prime }, x_i)\). Note that \(\mathcal {H}_2\) is the same as the distribution generated by \(\mathsf {Sim}_{Eq}\) for \(\beta =0\) case.
Indistinguishability between hybrids \(\mathcal {H}_1\) and \(\mathcal {H}_2\) follows from the receiver’s security of the underlying OT protocol.
Claim.Assuming the security of garbling scheme for circuits, \(\mathsf {Hybrid}_{t-1} \approx _c\mathsf {Hybrid}_{t,1}\).
Proof.
Let \(\mathcal {A}\) be an adversary corrupting the set of parties \([n] \setminus H\) that can distinguish between \(\mathsf {Hybrid}_t\) and \(\mathsf {Hybrid}_{t,1}\) with non-negligible probability. We construct an adversary \(\mathcal {B}\) breaking the security of garbling scheme.
\(\mathcal {B}\) chooses an uniform random tape for every \(j \not\in H\) and interacts with the adversary \(\mathcal {A}\). \(\mathcal {B}\) computes the first round message \({z}_i,\lbrace {\mathsf {ots}}_{1,t,\alpha ,\beta }\rbrace _{t \in A_i,\alpha ,\beta \in \lbrace 0,1\rbrace }\) for every \(i \in H\) as in \(\mathsf {Hybrid}_{t-1}\). \(\mathcal {B}\) runs in its “head” a faithful execution of the protocol \(\Phi\) using both honest and corrupted parties inputs. This yields the protocol transcript \(\mathsf {Z}\) and the shared local state \(\mathbb {Z}^*\). For every \(i \in H\), it generates the second round message as follows:
(1)
Set \(\ell ^{i,T+1} := \lbrace \mathsf {label}_{k,0}^{i,T+1}, \mathsf {label}_{k,1}^{i,T+1}\rbrace _{k\in [\ell ]}\) where for each \(k \in [\ell ]\) and \(b \in \lbrace 0,1\rbrace\)\(\mathsf {label}_{k,b}^{i,T+1} := 0^\lambda\).
(2)
\({\bf for}\) each w from T down to \(t+1\),
(1)
Parse \(\phi _w\) as \((i^*,f,g,h)\).
(2)
If \(i = i^*\) then compute (where \(\textsf {Prog}\) is described in Figure 2)
If \(i \ne i^*\) then for every \(\alpha ,\beta \in \lbrace 0,1\rbrace\), set \({\mathsf {ots}}^i_{2,w,\alpha ,\beta } \leftarrow \mathsf {OT}_2({\mathsf {ots}}_{1,w,\alpha ,\beta },\mathsf {label}^{i,w+1}_{h,0},\mathsf {label}^{i,w+1}_{h,1})\) and compute
For every \(i \in H\), let \(\mathsf {st}^t_{i}\) be the secret local state of party \(P_i\) before the beginning of the tth round of the computation phase. Interact with the garbled circuits challenger and give \(\mathsf {st}^t_i\) as the challenge input and \(\textsf {Prog}[{i,\phi _t},v_i,\lbrace \omega _{t,\alpha ,\beta }\rbrace _{\alpha ,\beta },\bot ,\ell ^{i,t+1}]\) as the challenge circuit if \(i = i^*\) and \(\textsf {Prog}[{i,\phi _t},v_i,\bot ,\lbrace {\mathsf {ots}}^i_{2,t,\alpha ,\beta }\rbrace _{\alpha ,\beta },\ell ^{i,t+1}]\) as the challenge circuit if \(i \ne i^*\) where \({\mathsf {ots}}^i_{2,t,\alpha ,\beta } \leftarrow \mathsf {OT}_2({\mathsf {ots}}_{1,t,\alpha ,\beta },\mathsf {label}^{i,t+1}_{h,0}, \mathsf {label}^{i,t+1}_{h,1})\). Obtain \(\widetilde{\textsf {Prog}}^{i,t}\) and \(\lbrace \mathsf {label}^{i,t}_{k}\rbrace _{k \in [\ell ]}\).
(4)
\({\bf for}\) each w from \(t-1\) down to 1:
(1)
Parse \(\phi _w\) as \((i^*,f,g,h)\).
(2)
Set \(\alpha ^* := \mathbb {Z}^*_f\), \(\beta ^* = \mathbb {Z}^*_g\) and \(\gamma ^* := \mathbb {Z}^*_h\).
Send \((\lbrace \widetilde{\textsf {Prog}}^{i,w}\rbrace _{w \in [T]},\lbrace \mathsf {label}^{i,1}_{k}\rbrace _{k \in [\ell ]})\) to every other party.
Notice that if the garbling \(\widetilde{\textsf {Prog}}^{i,t}\) is generated using the honest procedure then the messages sent to \(\mathcal {A}\) are distributed identically to \(\mathsf {Hybrid}_{t-1}\). Else, they are distributed identically to \(\mathsf {Hybrid}_{t,1}\). Thus, \(\mathcal {B}\) breaks the security of the garbling scheme for circuits which is a contradiction.□
Claim.Assuming the receiver security of oblivious transfer, we have \(\mathsf {Hybrid}_{t,2} \approx _c\mathsf {Hybrid}_{t,3}\).
Proof.
Let \(\mathcal {A}\) be an adversary corrupting the set of parties \([n] \setminus H\) that can distinguish between \(\mathsf {Hybrid}_{t,2}\) and \(\mathsf {Hybrid}_{t,3}\) with non-negligible probability. We construct an adversary \(\mathcal {B}\) breaking the receiver security of the oblivious transfer.
\(\mathcal {B}\) chooses a uniform random tape for every \(j \not\in H\) and interacts with the adversary \(\mathcal {A}\). For every \(i \in H\), \(\mathcal {B}\) generates \(z_i\) and \({\mathsf {ots}}_{1,w,\alpha ,\beta }\) for every \(w \in \cup _{i \in H} A_i \setminus \lbrace t\rbrace\) as in \(\mathsf {Hybrid}_{t,1}\). \(\mathcal {B}\) runs in its “head” a faithful execution of the protocol \(\Phi\) using both honest and corrupted parties inputs. This yields the protocol transcript \(\mathsf {Z}\) and the shared local state \(\mathbb {Z}^*\). Set \(\alpha ^* := \mathbb {Z}^*_f\), \(\beta ^* = \mathbb {Z}^*_g\) and \(\gamma ^* := \mathbb {Z}^*_h\). Let \(\phi _t = (i^*,f,g,h)\). For \((\alpha ,\beta) \ne (\alpha ^*,\beta ^*)\), we interact with the OT challenger and send \(\mathsf {Z}_t\), \(v_{i,h} \oplus \mathsf {NAND}(v_{i,f} \oplus \alpha , v_{i,g} \oplus \beta)\) as the challenge bits. Obtain \({\mathsf {ots}}_{1,t,\alpha ,\beta }\) as the challenge first OT message. Sample \(\omega _{t,\alpha ^*,\beta ^*}\) uniformly at random and compute \({\mathsf {ots}}_{1,t,\alpha ^*,\beta ^*}\) as \(\mathsf {OT}_1(1^\lambda ,\mathsf {Z}_t;\omega _{t,\alpha ^*,\beta ^*})\). For each \(i \in H\), send \(z_i, \lbrace {\mathsf {ots}}{1,w,\alpha ,\beta }\rbrace _{w\in A_i,\alpha ,\beta \in \lbrace 0,1\rbrace }\) on behalf of the honest party. Generate the second round message as in \(\mathsf {Hybrid}_{t,1}\).
Notice that if the challenge bit is \(\mathsf {Z}_t\) then the distribution of messages to \(\mathcal {A}\) is identical to \(\mathsf {Hybrid}_{t,3}\). Else, it is identical to \(\mathsf {Hybrid}_{t,2}\). Thus, \(\mathcal {B}\) breaks the receiver security of the oblivious transfer.□
References
[1]
William Aiello, Yuval Ishai, and Omer Reingold. 2001. Priced oblivious transfer: How to sell digital goods. In Proceedings of the EUROCRYPT 2001. Birgit Pfitzmann (Ed.), Vol. 2045, Springer, Germany, Innsbruck, Austria, 119–135.
Prabhanjan Ananth, Arka Rai Choudhuri, Aarushi Goel, and Abhishek Jain. 2018. Round-optimal secure multiparty computation with honest majority. In Proceedings of the 38th Annual International Cryptology Conference.Hovav Shacham and Alexandra Boldyreva (Eds.), Lecture Notes in Computer Science, Vol. 10992, Springer, 395–424. DOI:
Prabhanjan Ananth, Arka Rai Choudhuri, Aarushi Goel, and Abhishek Jain. 2019. Two round information-theoretic MPC with malicious security. In Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Yuval Ishai and Vincent Rijmen (Eds.), Lecture Notes in Computer Science, Vol. 11477. Springer, 532–561. DOI:
Benny Applebaum, Zvika Brakerski, and Rotem Tsabary. 2018. Perfect secure computation in two rounds. In Proceedings of the Theory of Cryptography - 16th International Conference.Amos Beimel and Stefan Dziembowski (Eds.), Lecture Notes in Computer Science, Vol. 11239, Springer, 152–174. DOI:
Benny Applebaum, Zvika Brakerski, and Rotem Tsabary. 2019. Degree 2 is complete for the round-complexity of malicious MPC. In Proceedings of the Advances in Cryptology - EUROCRYPT 2019-38th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Yuval Ishai and Vincent Rijmen (Eds.), Lecture Notes in Computer Science, Vol. 11477, Springer, 504–531. DOI:
Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. 2004. Cryptography in NC\(^0\). In Proceedings of the 45th FOCS. IEEE Computer Society Press, Rome, Italy, 166–175.
Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. 2005. Computationally private randomizing polynomials and their applications. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity. 260–274. DOI:
Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. 2012. Multiparty computation with low communication, computation and interaction via threshold FHE. In Proceedings of the EUROCRYPT 2012.David Pointcheval and Thomas Johansson (Eds.), Vol. 7237, Springer, Germany, Cambridge, UK, 483–501.
Saikrishna Badrinarayanan, Vipul Goyal, Abhishek Jain, Yael Tauman Kalai, Dakshita Khurana, and Amit Sahai. 2018. Promise zero knowledge and its applications to round optimal MPC. In Proceedings of the 38th Annual International Cryptology ConferenceHovav Shacham and Alexandra Boldyreva (Eds.), Lecture Notes in Computer Science, Vol. 10992, Springer, 459–487. DOI:
Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, and Tal Rabin. 2005. Secure computation without authentication. In Proceedings of the CRYPTO 2005.Victor Shoup (Ed.), Vol. 3621, Springer, Germany, Santa Barbara, CA, 361–377.
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. 2001. On the (Im)possibility of obfuscating programs. In Proceedings of the CRYPTO 2001.Joe Kilian (Ed.), Vol. 2139, Springer, Germany, Santa Barbara, CA, 1–18.
James Bartusek, Sanjam Garg, Daniel Masny, and Pratyay Mukherjee. 2020. Reusable two-round MPC from DDH. In Proceedings of the Theory of Cryptography - 18th International Conference.Rafael Pass and Krzysztof Pietrzak (Eds.), Lecture Notes in Computer Science, Vol. 12551, Springer, 320–348. DOI:
Donald Beaver, Silvio Micali, and Phillip Rogaway. 1990. The round complexity of secure protocols (Extended Abstract). In Proceedings of the 22nd ACM STOC. ACM Press, Baltimore, MD, 503–513.
Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. 2012. Foundations of garbled circuits. In Proceedings of the ACM CCS 12.Ting Yu, George Danezis, and Virgil D. Gligor (Eds.), ACM, Raleigh, NC, 784–796.
Mihir Bellare and Silvio Micali. 1990. How to sign given any trapdoor function. In Proceedings of the CRYPTO’88.Shafi Goldwasser (Ed.), Vol. 403, Springer, Germany, Santa Barbara, CA, 200–215.
Fabrice Benhamouda and Huijia Lin. 2018. k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits. In Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Jesper Buus Nielsen and Vincent Rijmen (Eds.), Lecture Notes in Computer Science, Vol. 10821, Springer, 500–532. DOI:
Fabrice Benhamouda and Huijia Lin. 2020. Mr NISC: Multiparty reusable non-interactive secure computation. In Proceedings of the Theory of Cryptography - 18th International Conference Rafael Pass and Krzysztof Pietrzak (Eds.), Lecture Notes in Computer Science, Vol. 12551, Springer, 349–378. DOI:
Manuel Blum, Paul Feldman, and Silvio Micali. 1988. Non-interactive zero-knowledge and its applications (Extended Abstract). In Proceedings of the 20th ACM STOC. ACM, Chicago, IL, 103–112.
Elette Boyle, Niv Gilboa, and Yuval Ishai. 2017. Group-based secure computation: Optimizing rounds, communication, and computation. In Proceedings of the EUROCRYPT 2017.Jean-Sébastien Coron and Jesper Buus Nielsen (Eds.), Vol. 10211. Springer, Germany, Paris, France, 163–193.
Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, and Stefano Tessaro. 2018. Foundations of homomorphic secret sharing. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference. 21:1–21:21. DOI:
Zvika Brakerski and Renen Perlman. 2016. Lattice-based fully dynamic multi-key FHE with short ciphertexts. In Proceedings of the CRYPTO 2016.Matthew Robshaw and Jonathan Katz (Eds.), Vol. 9814, Springer, Germany, Santa Barbara, CA, 190–213. DOI:
Christian Cachin, Claude Crépeau, and Julien Marcil. 1998. Oblivious transfer with a memory-bounded receiver. In Proceedings of the 39th FOCS. IEEE Computer Society Press, Palo Alto, CA, 493–502.
Ran Canetti. 2000b. Universally Composable Security: A New Paradigm for Cryptographic Protocols. Cryptology ePrint Archive, Report 2000/067. (2000). Retrieved September 1, 2017 from http://eprint.iacr.org/2000/067.
Ran Canetti. 2001. Universally composable security: A new paradigm for cryptographic protocols. In Proceedings of the 42nd FOCS. IEEE Computer Society Press, Las Vegas, NV, 136–145.
Ran Canetti. 2004. Universally composable signature, certification, and authentication. In Proceedings of the 17th IEEE Computer Security Foundations Workshop. 219. DOI:
Ran Canetti. 2005. Universally composable security: A new paradigm for cryptographic protocols. (2005). Version of December 2005. Retrieved September 1, 2017 from http://eccc.uni-trier.de/eccc-reports/2001/TR01-016.
Ran Canetti and Marc Fischlin. 2001. Universally composable commitments. In Proceedings of the CRYPTO 2001.Joe Kilian (Ed.), Vol. 2139, Springer, Germany, Santa Barbara, CA, 19–40.
Ran Canetti, Huijia Lin, and Rafael Pass. 2010. Adaptive hardness and composable security in the plain model from standard assumptions. In Proceedings of the 51st FOCS. IEEE Computer Society Press, Las Vegas, NV, 541–550.
Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai. 2002. Universally composable two-party and multi-party secure computation. In Proceedings of the 34th ACM STOC. ACM, Montréal, Québec, Canada, 494–503.
Arka Rai Choudhuri, Michele Ciampi, Vipul Goyal, Abhishek Jain, and Rafail Ostrovsky. 2020. Round optimal secure multiparty computation from minimal assumptions. In Proceedings of the Theory of Cryptography - 18th International Conference.Rafael Pass and Krzysztof Pietrzak (Eds.), Lecture Notes in Computer Science, Vol. 12551, Springer, 291–319. DOI:
Michael Clear and Ciaran McGoldrick. 2015. Multi-identity and multi-key leveled FHE from learning with errors. In Proceedings of the CRYPTO 2015.Rosario Gennaro and Matthew J. B. Robshaw (Eds.), Vol. 9216, Springer, Germany, Santa Barbara, CA, 630–656. DOI:
Yan Zong Ding, Danny Harnik, Alon Rosen, and Ronen Shaltiel. 2004. Constant-round oblivious transfer in the bounded storage model. In Proceedings of the TCC 2004.Moni Naor (Ed.), Vol. 2951, Springer, Germany, Cambridge, MA, 446–472.
Uriel Feige, Dror Lapidot, and Adi Shamir. 1990. Multiple non-interactive zero knowledge proofs based on a single random string (Extended Abstract). In Proceedings of the 31st FOCS. IEEE Computer Society Press, St. Louis, Missouri, 308–317.
Sanjam Garg, Craig Gentry, Shai Halevi, and Mariana Raykova. 2014. Two-round secure MPC from indistinguishability obfuscation. In Proceedings of the TCC 2014.Yehuda Lindell (Ed.), Vol. 8349, Springer, Germany, San Diego, CA, 74–94. DOI:
Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. 2013. Candidate indistinguishability obfuscation and functional encryption for all circuits. In Proceedings of the 54th FOCS. IEEE Computer Society Press, Berkeley, CA, 40–49.
Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. 2013. Witness encryption and its applications. In Proceedings of the 45th ACM STOC.Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (Eds.), ACM, Palo Alto, CA, 467–476.
Sanjam Garg, Yuval Ishai, and Akshayaram Srinivasan. 2018. Two-round MPC: Information-theoretic and black-box. In Proceedings of the Theory of Cryptography - 16th International Conference. Amos Beimel and Stefan Dziembowski (Eds.), Lecture Notes in Computer Science, Vol. 11239, Springer, 123–151. DOI:
Sanjam Garg and Akshayaram Srinivasan. 2017. Garbled protocols and two-round MPC from bilinear maps. In Proceedings of the 58th FOCS. IEEE Computer Society Press, 588–599.
Sanjam Garg and Akshayaram Srinivasan. 2018. Two-round multiparty secure computation from minimal assumptions. In Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Jesper Buus Nielsen and Vincent Rijmen (Eds.), Lecture Notes in Computer Science, Vol. 10821, Springer, 468–499. DOI:
Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to play any mental game or A completeness theorem for protocols with honest majority. In Proceedings of the 19th ACM STOC.Alfred Aho (Ed.), ACM, New York City, NY, 218–229.
Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. 1988. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing 17, 2 (1988), 281–308. DOI:
S. Dov Gordon, Feng-Hao Liu, and Elaine Shi. 2015. Constant-round MPC with fairness and guarantee of output delivery. In Proceedings of the CRYPTO 2015.Rosario Gennaro and Matthew J. B. Robshaw (Eds.), Vol. 9216, Springer, Germany, Santa Barbara, CA, 63–82. DOI:
Yuval Ishai and Eyal Kushilevitz. 2000. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In Proceedings of the 41st FOCS. IEEE Computer Society Press, Redondo Beach, CA, 294–304.
Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. 2008. Founding cryptography on oblivious transfer - efficiently. In Proceedings of the CRYPTO 2008.David Wagner (Ed.), Vol. 5157, Springer, Germany, Santa Barbara, CA, 572–591.
Pratyay Mukherjee and Daniel Wichs. 2016. Two round multiparty computation via multi-key FHE. In Proceedings of the EUROCRYPT 2016.Marc Fischlin and Jean-Sébastien Coron (Eds.), Vol. 9666, Springer, Germany, Vienna, Austria, 735–763. DOI:
Moni Naor and Benny Pinkas. 2001. Efficient oblivious transfer protocols. In Proceedings of the 12th SODA. S. Rao Kosaraju (Ed.), ACM-SIAM, Washington, DC, 448–457.
Chris Peikert and Sina Shiehian. 2016. Multi-key FHE from LWE, revisited. In Proceedings of the TCC 2016-B.Martin Hirt and Adam D. Smith (Eds.), Vol. 9986, Springer, Germany, Beijing, China, 217–238. DOI:
Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. 2008. A framework for efficient and composable oblivious transfer. In Proceedings of the CRYPTO 2008.David Wagner (Ed.), Vol. 5157, Springer, Germany, Santa Barbara, CA, 554–571.
Birgit Pfitzmann and Michael Waidner. 2000. Composition and integrity preservation of secure reactive systems. In Proceedings of the ACM CCS 00.S. Jajodia and P. Samarati (Eds.), ACM, Athens, Greece, 245–254.
Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th ACM STOC.Harold N. Gabow and Ronald Fagin (Eds.), ACM, Baltimore, MA, 84–93.
Andrew Chi-Chih Yao. 1986. How to generate and exchange secrets (Extended Abstract). In Proceedings of the 27th FOCS. IEEE Computer Society Press, Toronto, Ontario, Canada, 162–167.
Luo YChen YLi TTan CDou H(2024)Cloud-SMPC: two-round multilinear maps secure multiparty computation based on LWE assumptionJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00586-513:1Online publication date: 22-Jan-2024
Ananth PGulati ALin Y(2024)Cryptography in the Common Haar State Model: Feasibility Results and SeparationsTheory of Cryptography10.1007/978-3-031-78017-2_4(94-125)Online publication date: 28-Nov-2024
We present the first two-round multiparty computation (MPC) protocols secure against malicious adaptive corruption in the common reference string (CRS) model, based on DDH, LWE, or QR. Prior two-round adaptively secure protocols were known only in ...
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
In the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure two-party computation has ...
CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security
While the feasibility of constant-round and actively secure MPC has been known for over two decades, the last few years have witnessed a flurry of designs and implementations that make its deployment a palpable reality. To our knowledge, however, ...
Luo YChen YLi TTan CDou H(2024)Cloud-SMPC: two-round multilinear maps secure multiparty computation based on LWE assumptionJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00586-513:1Online publication date: 22-Jan-2024
Ananth PGulati ALin Y(2024)Cryptography in the Common Haar State Model: Feasibility Results and SeparationsTheory of Cryptography10.1007/978-3-031-78017-2_4(94-125)Online publication date: 28-Nov-2024
