k-Round Multiparty Computation from k-Round Oblivious Transfer via Garbled Interactive Circuits | Springer Nature Link

Garg et al. [24] introduced a generic approach for collapsing any MPC protocol down to 2 rounds, using indistinguishability obfuscation [4, 25]. Later et al. [35] showed how to perform round collapsing using garbled circuits, witness encryption, and NIZK. Very recently, Garg and Srinivasan [29] further showed how to do collapse rounds using garbled protocols, which can be implemented from bilinear pairing groups. In this work, we perform round collapsing using our new notion of garbled interactive circuits; this notion is general and enables us to weaken the assumption to 2-round OT. (See the full version [7] for a more detailed comparison with prior works.) Below, we give an overview of our construction in the 2-round setting; construction in the multi-round setting is similar.

2.1 Round-Collapsing via Obfuscation

The basic idea is natural and simple: To construct 2-round MPC protocols for a function f, take any multi-round MPC protocols for f, referred to as the inner MPC protocols, such as, the Goldreich-Micali-Wigderson protocol [32], and try to eliminate interaction. Garg, Gentry, Halevi, and Raykova (GGHR) [24] showed how to do this using indistinguishability obfuscation. The idea is to let each player \(P_i\) obfuscate their next-step circuit \({\mathsf {Next}}_i(x_i, r_i, \star )\) in an execution of the inner MPC protocol \(\varPi \) for computing f, where \({\mathsf {Next}}_i(x_i,r_i,\star )\) has \(P_i\)’s private input \(x_i\) and random tape \(r_i\) hardcoded, and produces \(P_i\)’s next message \(m_i^\ell \) in round \(\ell \), on input the messages \({\bar{m}}^{<\ell } = {\{m_j^{\ell '}\}}_{j, \ell '<\ell }\) broadcast by all parties in the previous rounds,

Given all obfuscated circuits \({\{{\mathrm {i}O}({{\mathsf {Next}}(x_i,r_i,\star )}_j)\}}\), each party \(P_i\) can emulate the execution of \(\varPi \) in its head, eliminating interaction completely.

The above idea achieves functionality, but not security. In fact, attackers, given the obfuscated next-step circuits of honest parties, can evaluate the residual function with the inputs of honest parties hardcoded, or even evaluate honest parties’ next-step circuits on arbitrary “invalid” messages. To avoid this, the protocol requires each party to commit to its input and random tape in the first round, \(c_i {\mathop {\leftarrow }\limits ^{{}_R}}{\mathsf {Com}}(x_i, r_i)\). Then, in the second round, each party obfuscates an augmented next-step circuit \({{\mathsf {AugNext}}}_i\) that takes additionally a NIZK proof \(\pi _j^{\ell '}\) for each message \(m_j^{\ell '}\) it receives, and verifies the proof \(\pi _j^{\ell '}\) that \(m_j^{\ell '}\) is generated honestly from inputs and random tapes committed in \(c_j\) (it aborts otherwise). This way, only the unique sequence of honestly generated messages is accepted by honest parties’ obfuscated circuits. In the security proof, by the security of indistinguishability obfuscation and NIZK, this unique sequence can even be hardcoded into honest parties’ obfuscated circuits, enabling simulation using the simulator of the inner MPC protocol.

2.2 Garbled Interactive Circuits

The fact that it suffices and is necessary that the honest parties’ obfuscated circuits only allow for a single meaningful “execution path” (determined by the unique sequence of honest messages), suggests that we should rather use garbling instead of obfuscation for hiding honest parties’ next-step circuits. However, the challenge is that the next-step circuits \({\mathsf {Next}}_i\) are not plain circuits: They are interactive in the sense that they takes inputs (i.e., MPC messages) generated by other parties that cannot be fixed at time of garbling. To overcome the challenge, we formalize the MPC players as interactive circuits, and propose a new notion called Garbled Interactive Circuits (GIC).

The interaction with an interactive circuit is captured via a non-deterministic (\(\text {poly}\)-size) oracle \({\mathcal {O}}\) that on inputs a query q and some witness w returns an answer \(a = {\mathcal {O}}(q, w)\) (or \(\bot \) if w is not accepting). (Note that \({\mathcal {O}}\) is non-deterministic in the sense that without a valid witness, one cannot evaluate \({\mathcal {O}}\).) An interactive circuit \({\mathrm {i}C}\) consists of a list of L next-step circuits \({\{{\mathrm {i}C}^\ell \}}_{\ell \in [L]}\). Its execution with oracle \({\mathcal {O}}\) on input a list of witnesses \({\bar{w}} = {\{{\bar{w}}^\ell \}}\) proceeds in L iterations as depicted in Fig. 1: In round \(\ell \), \({\mathrm {i}C}^\ell \) on input the state \({{{st}}}^{\ell -1}\) output in the previous round, as well as the answers \({\bar{a}}^{\ell -1} = {\{a^{\ell -1}_k\}}\) from \({\mathcal {O}}\) to queries \({\bar{q}}^{\ell -1} = {\{q^{\ell -1}_k\}}\) produced in the previous round, outputs the new state \({{{st}}}^{\ell }\) and queries \({\bar{q}}^\ell = {\{q^{\ell }_k\}}\), and a (round) output \(o^\ell \).

The output of the execution is the list of round outputs \({\bar{o}}={\{o^\ell \}}_\ell \), and the transcript of the execution is the list of all queries, answers, and outputs \(\mathsf {trans}({\mathrm {i}C}, {\bar{w}}) = {\{({\bar{q}}^\ell , {\bar{a}}^\ell , o^\ell )\}}_\ell \). In the case that any oracle answer is \(a^\ell _k =\bot \), the execution is considered invalid. For simplicity of this high-level overview, we consider only valid executions and valid transcript; see Sect. 4 for more details.

A Garbled Interactive Circuit (GIC) scheme \(\mathsf {GiC}\) allows us to garble an interactive circuit \(\widehat{{\mathrm {i}C}}{\mathop {\leftarrow }\limits ^{{}_R}}\mathsf {GiC.Garble}({\mathrm {i}C})\), s.t. 

• Correctness: We can evaluate \(\widehat{{\mathrm {i}C}}\) with the oracle \({\mathcal {O}}\) and a list \({\bar{w}}\) of witnesses (in the clear) to obtain each round output \(o^\ell = \mathsf {GiC.Eval}(\widehat{{\mathrm {i}C}},{\bar{w}}^{<\ell })\). This significantly differs from classical garbling techniques where inputs of the computation must be encoded using secrets (such as, mapping them to corresponding input keys or labels).

• Simulation Security for Unique Transcripts Distribution: Security guarantees that \(\widehat{{\mathrm {i}C}}\) reveals only the transcript of execution, including all outputs, queries, and answers, and nothing else, that is, it can be simulated by \(\widetilde{\mathrm {i}C}{\mathop {\leftarrow }\limits ^{{}_R}}\mathsf {GiC.Sim}(\mathsf {trans})\), provided that there is a unique transcript of execution.

The requirement on unique transcript is necessary, otherwise, security is ill-defined as there may exist different transcripts produced by using different witnesses, and the simulator cannot hardcode them all. Furthermore, garbled interactive circuit schemes are meant to be different from obfuscation and hides only a single execution path. To formalize this, there are two options:

• Statistically Unique Transcript. The easier option is requiring simulation security only for interactive circuits \({\mathrm {i}C}\) that have unique transcript no matter what witnesses are used, that is, for all \({\bar{w}}, {\bar{w}}'\), \(\mathsf {trans}({\mathrm {i}C},{\mathcal {O}}, {\bar{w}}) = \mathsf {trans}({\mathrm {i}C},{\mathcal {O}}, {\bar{w}}')\). This is, however, a strong requirement.

• (Default:) Computationally Unique Transcript. The more general option is considering a distribution \(\mathrm {i}\mathcal {D}\) over \(({\mathrm {i}C}, {\bar{w}})\) that has computationally unique transcripts, in the sense that given \(({\mathrm {i}C}, {\bar{w}})\), it is hard to find \({\bar{w}}'\) that leads to a different valid transcript, \(\mathsf {trans}({\mathrm {i}C},{\mathcal {O}}, {\bar{w}}) \ne \mathsf {trans}({\mathrm {i}C},{\mathcal {O}}, {\bar{w}}')\).^{Footnote 7}

GIC for a computational or statistical unique-transcript distribution ensures:

Looking ahead, our 2-round MPC protocols from 2-round semi-honest oblivious transfer crucially rely on the stronger notion of GIC for computationally unique transcripts. If using GIC for statistically unique transcripts, we would need a 2-round OT protocol where the receiver’s message statistically binds its input bit, which is not a necessary assumption for constructing 2-round semi-honest MPC protocols.

2.3 Constructing GIC from Witness Selector

We start with the warm-up case of building GIC for statistically unique transcripts by combining plain garbled circuits and witness encryption. Witness Encryption (WE) proposed by Garg et al. [26], enables one to encrypt a message under an instance \(\mathsf {x}\) of an NP language \(\mathcal {L}\) to obtain a ciphertext \(\mathsf {ct}{\mathop {\leftarrow }\limits ^{{}_R}}\mathsf {WE.Enc}(\mathsf {x}, \mathsf {M})\); later this ciphertext can be decrypted using any witness \(\mathsf {w}\) of \(\mathsf {x}\), \(\mathsf {M}= \mathsf {WE.Dec}(\mathsf {ct},\mathsf {w})\). The idea of combining garbled circuits and witness encryption has already appeared in three recent works by Gordon et al. [35], Cho et al. [19], and Döttling and Garg [23]. Our garbled interactive circuit scheme can be viewed as a generalization of their ideas for capturing the full power of this combination. As we explain shortly, to handle computationally unique transcripts, we need to rely on a new primitive called Witness Selector, which strengthens WE.^{Footnote 8}

To garble an interactive circuit \({\mathrm {i}C} = {\{{\mathrm {i}C}^\ell \}}_\ell \), a natural first attempt is garbling each next-step circuit \({\mathrm {i}C}^\ell \) as a plain circuit, yielding L garbled circuits \({\{\widehat{{\mathrm {i}C}}{}^\ell , \mathsf {key}^\ell \}}_{\ell }\), where each input wire of \(\widehat{{\mathrm {i}C}}{}^\ell \) has two keys, \((\mathsf {key}^\ell [k,0],\mathsf {key}^\ell [k,1])\), one for this input bit being 0 and one for 1. The difficulty is that, to evaluate \(\widehat{{\mathrm {i}C}}{}^\ell \), the evaluator must obtain keys corresponding to the honestly generated state \({{{st}}}^{\ell -1}\) and answers \({\bar{a}}^{\ell -1}\) produced in the previous round; denote these keys as \(\mathsf {key}^\ell [{{{st}}}^{\ell -1}]\) and \(\mathsf {key}^\ell [{\bar{a}}^{\ell -1}]\).^{Footnote 9} We show how to enable this by modifying the garbled circuits \({\{\widehat{{\mathrm {i}C}}{}^\ell \}}\) as follows.

• The first idea is embedding all keys \(\mathsf {key}^\ell \) for one garbled circuit \(\widehat{{\mathrm {i}C}}{}^\ell \) in the previous one \(\widehat{{\mathrm {i}C}}{}^{\ell -1}\), so that, \(\widehat{{\mathrm {i}C}}{}^{\ell -1}\) can output directly the keys \(\mathsf {key}^\ell [{{{st}}}^{\ell -1}]\) for the state \({{{st}}}^{\ell -1}\) it produces. This idea, however, does not apply for selecting keys for answers \({\bar{a}}^{\ell -1}\), as \(\widehat{{\mathrm {i}C}}{}^{\ell -1}\) only computes queries \({\bar{q}}^{\ell -1}\) but not answers as it does not necessarily know the corresponding witnesses \({\bar{w}}^{\ell -1}\).

• The second idea is using WE as a “translator.” To illustrate the idea, assume that there is a single query \(q^{\ell -1}\) and it has a Boolean answer \(a^{\ell -1}\). In this case, let \(\widehat{{\mathrm {i}C}}{}^{\ell -1}\) output a pair of WE ciphertexts \((\mathsf {ct}_0, \mathsf {ct}_1)\), where \(\mathsf {ct}_b\) encrypts the key \(\mathsf {key}^\ell [k,b]\) for the answer \(a^{\ell -1}\) being b, under the statement \(\mathsf {x}_b\) that the oracle outputs b, \({\mathcal {O}}(q^{\ell -1}, w'_b) = b\), for some witness \(w'_b\). Now, the evaluator after evaluating \(\widehat{{\mathrm {i}C}}{}^{\ell -1}\) obtains \(\mathsf {ct}_0, \mathsf {ct}_1\). Using the witness \(w^\ell \) it receives as input, it can decrypt the WE ciphertext \(\mathsf {ct}^{\ell -1}_{a^{\ell -1}}\) for \(a^{\ell -1} = {\mathcal {O}}(q^{\ell -1}, w^{\ell -1})\), obtaining the right key \(\mathsf {key}^\ell [a^{\ell -1}]\) for evaluating the next garbled circuit.

To show security, it boils down to argue that for each garbled circuit \(\widehat{{\mathrm {i}C}}{}^{\ell }\), only one key for each input wire is revealed. The security of \(\widehat{{\mathrm {i}C}}{}^{\ell -1}\) ensures that only keys \(\mathsf {key}^\ell [{{{st}}}^{\ell -1}]\) for the right state is revealed. On the other hand, to argue that only keys \(\mathsf {key}^\ell [k,a^{\ell -1}]\) for the right answers are revealed, it crucially relies on the fact that the transcript including the answer is statistically unique. Thus, the ciphertext \(\mathsf {ct}_{1-a^{\ell -1}}\) is encrypted under a false statement, and by security of WE, the label \(\mathsf {key}^\ell [k,1-a^{\ell -1}]\) is hidden. We emphasize that if the transcript were only computationally unique, both WE ciphertexts \(\mathsf {ct}_0, \mathsf {ct}_1\) would potentially be encrypted under true statements, as there may exist two witnesses \(w_0, w_1\) that make the oracle output 0 and 1, \({\mathcal {O}}(q^{\ell -1}, w_0) = 0\), \({\mathcal {O}}(q^{\ell -1}, w_1) = 1\), even though it is computationally hard to find them; and the security of WE would be vacuous.

To handle computationally unique transcripts, WE is not the right tool. We propose a new primitive called Witness Selective (WS), which strengthens WE in two ways:

• Correctness: WS is defined for a non-deterministic oracle \({\mathcal {O}}\). One can encrypt a set of keys \(\mathsf {key}= {\{\mathsf {key}[k,b]\}}_{k \in [l], b \in {\{0,1\}}}\) under a query q, \(\mathsf {ct}\leftarrow \mathsf {WS.Enc}(q,\mathsf {key})\), which can later be decrypted using a witness w revealing the keys selected according to the output \(a = {\mathcal {O}}(q, w)\), that is, \({\{\mathsf {key}[k,a_k]\}}_k = \mathsf {WS.Dec}(\mathsf {ct}, w)\).

• Semantic Security for Unique Answers: The security guarantee is that the WS ciphertext \(\mathsf {ct}\) hides all the keys \(\mathsf {key}[k, 1-a_{k}]\), provided that a is the computationally unique answer. Clearly, if it were easy to find two witnesses \(w, w'\) such that, \((a = {\mathcal {O}}(q, w)) \ne (a' = {\mathcal {O}}(q,w'))\), the aforementioned semantic security cannot hold. Therefore, similarly to GIC, security is only required to hold for a distribution \(\mathrm {w}\mathcal {D}\) over (q, w) that has computationally unique answers in the sense that given (q, w), it is hard to find \(w'\) that makes \({\mathcal {O}}\) output a different valid answer. Then,

  $$\begin{aligned}&{\left\{ \mathsf {WS.Enc}(q,\mathsf {key}) : (q, w) {\mathop {\leftarrow }\limits ^{{}_R}}\mathrm {w}\mathcal {D}\right\} } \approx \\&{\left\{ \mathsf {WS.Enc}(q,\mathsf {key}) : (q, w) {\mathop {\leftarrow }\limits ^{{}_R}}\mathrm {w}\mathcal {D}; \ a = {\mathcal {O}}(q, w); \ \forall k, \ \mathsf {key}[k, 1-a_k] = 0 \right\} } . \end{aligned}$$

We can construct general GIC scheme for computationally unique transcript by replacing WE in the warm-up construction with WS. Slightly more precisely, each garbled circuit \(\widehat{{\mathrm {i}C}}{}^{\ell -1}\) outputs a WS ciphertext \(\mathsf {ct}\) encrypting keys \({\{\mathsf {key}[k, b]\}}\) for all wires corresponding to the oracle answer \(a^{\ell -1}\), under the query \(q^{\ell -1}\) (if there are multiple queries, simply generate one WS ciphertext for each query); then, the evaluator can use the witness \(w^{\ell -1}\) to decrypt and obtain keys \({\{\mathsf {key}[k, a^{\ell -1}_k]\}}\) selected according to the oracle answer \(a^{\ell -1} = {\mathcal {O}}(q^{\ell -1}, w^{\ell -1})\). Since the oracle answer (as a part of the transcript) is computationally unique, semantic security of WS ensures that the other keys \({\{\mathsf {key}[k, 1-a^{\ell -1}_k]\}}\) remain hidden, and hence we can invoke the security of the garbled circuits to argue the security of GIC.

As discussed above, WS is stronger than WE. For instance, one can use WS to encrypt a set of keys \(\mathsf {key}\) under a query \(q = (h,y=h(v))\) for a randomly sampled collision-resistant hash function h. With respect to the de-hashing oracle \({\mathcal {O}}(q, v')\) that outputs \(v'\) if \(y = h(v')\), a WS ciphertext reveals only keys \({\{\mathsf {key}[k,v_k]\}}\) selected by v, and hides others. In contrast, WE provides no security in this case. On the other hand, WS is weaker than the notion of extractable WE [33]. Roughly speaking, extractable WE guarantees that for every attacker A, there is an extractor E, such that, if A can decrypt a ciphertext encrypted under statement \(\mathsf {x}\), then E can output a witness of \(\mathsf {x}\). Extractable WE implies WS, and is strictly stronger as it requires knowledge extraction.

We note that so far there is no construction of general-purpose WE, let alone WS or extractable WE, from standard assumptions. This is also not the goal of this work. Instead, we show below how to construct special-purpose WS that suffices to construct 2-round MPC protocols.

2.4 Round-Collapsing via Garbled Interactive Circuits

We now revisit the round-collapsing approach, by replacing obfuscation with garbled interactive circuits. First, we observe that each player \(P_i\) in the inner MPC protocol can be viewed as an interactive circuit \({\{P_i^\ell \}}\), interacting with an oracle \({\mathcal {O}}\) representing the other parties \({\{P_j\}}\), as described in Fig. 2.

The important details are: In each round \(\ell \), \(P_i^{\ell }\) obtains through the oracle \({\mathcal {O}}\) all messages \({\bar{m}}^{\ell -1} = {\{m_j^{\ell -1}\}}_j\) output in the previous round, and additionally, it outputs a proof \(\pi ^{\ell }_i\) that the message \(m_i^{\ell }\) it outputs is generated honestly from its input \(x_i\) and random tape \(r_i\) committed in \(c_i\). The message and proof are exactly the witness \(w_i^\ell = (m_i^\ell , \pi ^\ell _i)\) for the query \(q^\ell _i\) that players \(P_j^\ell \) make in round \(\ell \) to the oracle \({\mathcal {O}}\) for obtaining \(P_i\)’s message \(a_i^\ell =m_i^\ell \) for the next round.

Therefore, we can use a GIC scheme to garble the interactive circuit representing each player \(P_i\) to collapse round:

1. 1.

   In the first round of MPC, each \(P_i\) broadcasts a commitment \(c_i\) to its input \(x_i\) and random tape \(r_i\), and

2. 2.

   in the second round, each \(P_i\) sends the garbled interactive circuit \(\widehat{P}{}_i {\mathop {\leftarrow }\limits ^{{}_R}}\mathsf {GiC.Garble}({\{P^\ell _i\}})\), and

3. 3.

   each \(P_i\) emulates the execution of inner MPC in its head, by evaluating all \({\{\widehat{P}{}_j\}}\) round by round: In round \(\ell \), it evaluates \(o_j^\ell = (m_j^\ell , \pi _j^\ell ) = \mathsf {GiC.Eval}(\widehat{P}{}_j, {\bar{w}}^{<\ell })\), using the outputs obtained in previous rounds as witnesses, \(w^{<\ell } = o^{< \ell } = {\{ (m_k^{\ell '},\pi _k^{\ell '})\}}_{k, \ell '<\ell }\). \(P_i\) obtains its output when the inner MPC execution completes.

We observe that the transcript of execution of each \({\{P^\ell _i\}}\) is indeed computationally unique, as the commitments \({\{c_j\}}\) have unique committed values \({\{x_j, r_j\}}\) by the computational binding property, and lead to unique next messages \({\{m_j^\ell \}}\), by the soundness of proofs \({\{\pi _j^\ell \}}\). Therefore, the GIC scheme guarantees that the garbled interactive circuits reveals only their outputs, queries, and answers, summing up to all commitments \({\{c_j\}}\), inner MPC messages \({\{m^\ell _j\}}\), and proofs \({\{\pi _j^\ell \}}\), all of which can be made simulatable.

The MPC messages can be simulated by the simulator of the inner MPC protocol. To make commitments and proofs simulatable, the easiest way is using a standard non-interactive commitment scheme and a NIZK system, which however (1) requires a common reference string, and (2) makes the task of instantiating the associated WS scheme difficult. Recall that to instantiate the GIC scheme, we need a WS scheme for the oracle \({\mathcal {O}}\) described above, which internally verifies proofs. To solve this, we resort to a zero-knowledge Functional Commitment (FC) scheme that has a built-in special-purpose proof system. By minimizing the security requirements on this commitment, we manage to construct it, together with an associated WS scheme, from 2-message semi-honest OT (which is a necessary assumption). This gives 2-round MPC protocols in the plain model from 2-message semi-honest OT.

2.5 Functional Commitment with Witness Selector from OT

A zero-knowledge functional commitment scheme \({\mathsf {FC}}\) is computationally binding and computationally hiding, and additionally supports functional opening that is both binding and zero-knowledge. The notion of functional commitment was previously proposed by Libert et al. [37] for inner product functions, and later generalized to general functions in [3]. Here, we consider a stronger property, namely a zero-knowledge property. On the other hand, we do not require commitments nor functional decommitments to be of size constant in the length of the committed value, and our binding property only holds against semi-honest adversaries. Functional commitments were also implicitly and informally suggested by Gorbunov et al. in [34], as a way to interpret their new primitive: Homomorphic Trapdoor Functions (HTDFs). HTDFs could be used to construct our functional commitments (but the converse is not true). However, we do not know how to construct WS associated to an FC built from the HTDF proposed in [34].

• Functional Opening: For a commitment \(c = {\mathsf {FC.Com}}(v; \rho )\) and a circuit G, one can generate a functional decommitment \(d\) to the output of G evaluated on the committed value v, namely \(m= G(v)\), using the randomness \(\rho \) of the commitment \(c\),

  $$ d= {\mathsf {FC.FOpen}}(c, G, m, \rho ), \quad {\mathsf {FC.FVer}}(c, G, m, d) = 1.$$

  We say that \((m,d)\) is a decommitment to (c, G); here, \(d\) serves as a proof \(\pi = d\) that the value committed in c evaluates to m through G in our 2-round MPC protocols.

  (Semi-Honest) Functional Binding: For an honestly generated commitment \(c= {\mathsf {FC.Com}}(v;\rho )\) with random tape \(\rho \), it is hard to find a decommitment \((m',d')\) to (c, G) for a different output \(m'\ne m\), even given \(\rho \). Note this is weaker than standard computational binding, as binding is only required for honestly generated commitments. This corresponds to distributional soundness of the proofs.

  Simulation (i.e., Zero-Knowledge): An honestly generated commitment \(c {\mathop {\leftarrow }\limits ^{{}_R}}{\mathsf {FC.Com}}(v;\rho )\) (with random tape \(\rho \)) and decommitment \(d\) can be simulated together, using only the output m, \((\tilde{c}, \tilde{d}) {\mathop {\leftarrow }\limits ^{{}_R}}{\mathsf {FC.Sim}}(c, G, m)\). This property is weaker than standard zero-knowledge, as the statement is from a distribution and is also simulated; only a single decommitment \(d\) can be given for each commitment, or else simulation does not work.

A WS scheme associated with \({\mathsf {FC}}\) is for the oracle \({\mathcal {O}}^{\mathsf {FC}}\) that on input a query (c, G) and a witness \(w = (m,d)\), outputs m if \((m,d)\) is a valid decommitment to (c, G), and \(\bot \) otherwise. The functional binding property ensures that for any v, G, the distribution \(\mathrm {w}\mathcal {D}_{v,G}\) of query \(q = (c, G)\) and decommitment \(w = (m, d)\) for honestly generated \(c= {\mathsf {FC.Com}}(v;\rho )\), produces computationally unique oracle answer m (even given the randomness \(\rho \) as auxiliary information). Despite the fact that functional commitments are only semi-honestly binding and one-time simulatable, we show that, together with an associated WS scheme, they suffice to instantiate our 2-round MPC protocols.

We show how to construct a functional commitment, and its associated WS scheme, from garbled circuits and a 2-round string 2-to-1 semi-honest OT.

OT as semi-honest binding commitment: We start with observing that any string 2-to-1 semi-honest OT gives a commitment scheme that is semi-honest binding; that is, given an honestly generated commitment \(c = {\mathsf {Com}}(v;\rho )\) using a uniformly random tape \(\rho \), it is hard to find a decommitment \((v',\rho ')\) that opens c to a different value \(v' \ne v\) even given \(\rho \). To see this, consider the parallelized version of 2-to-1 string OT, where \(\mathrm {ot}_1 = \mathrm {p}\mathsf {OT}_1(x; \rho )\) generates the first flows from OT receiver for every bit \(x_k\), and \(\mathrm {ot}_2 = \mathrm {p}\mathsf {OT}_2(\mathrm {ot}_1, {\{\mathsf {key}[k, b]\}})\) generates the second flows from OT sender for every pair of inputs \((\mathsf {key}[k,0], \mathsf {key}[k,1])\). Combining \(\mathrm {ot}_2\) with the randomness \(\rho \) used for generating the first flows, one can act as the OT receiver to recover exactly one input \(\mathsf {key}[k, x_k]\) at each coordinate k. We argue that the first flow \(\mathrm {ot}_1 = \mathrm {p}\mathsf {OT}_1(x; \rho )\) is a semi-honest commitment to x. Suppose that it is not the case and that it is easy to find a decommitment \(\rho '\) to a different value \(x' \ne x\). Then a semi-honest attacker acting as OT receiver can violate the privacy of OT sender. (However, observe that \(\mathrm {p}\mathsf {OT}_1(x)\) is not necessarily computationally binding, as there is no security for maliciously generated first flows of OT.)

Functional Opening: We use garbled circuits and OT (as a semi-honest binding commitment scheme) to enable functional opening. To commit to a value v, garble a universal circuit \(U_v(\star ) = U(v,\star )\) with v hardcoded, and commit to all its input keys \({\{\mathsf {key}[k,b]\}}\) using \(\mathrm {p}\mathsf {OT}_1\):

To generate a decommitment (m, d) of (c, G), simply send the keys and randomness used for generating the OT first flows \({\{\mathrm {ot}_1[k,G[k]]\}}\) selected by G. More formally, if G[k] is the k-th bit of the description of G which is used as input to \(U_v\):

Verifying a decommitment \(d= {\{\mathsf {key}', \rho '\}}\) w.r.t. (c, G, m) involves checking that the keys and randomness contained in \(d'\) generate the OT first flows selected by G, and the garbled universal circuit \(\widehat{U}{}_v\) evaluates to m on input these keys.

The alternative text for this image may have been generated using AI.

It is easy to see that the semi-honest binding property of \(\mathrm {p}\mathsf {OT}_1\) implies the semi-honest functional binding of \({\mathsf {FC}}\), and that a pair (c, d) can be simulated relying on the security of garbled circuits and the computational hiding property (i.e., receiver privacy) of \(\mathrm {p}\mathsf {OT}_1\).

WS for \({\mathsf {FC}}\): Next, to construct a WS scheme for the oracle \({\mathcal {O}}^{\mathsf {FC}}\) that verifies the functional decommitment of \({\mathsf {FC}}\), we again use garbled circuits to “enforce and hide” this verification. To encrypt a set of messages \(\mathsf {M}[i,b']\) under a query (c, G), our idea is to garble the following circuit V that acts as \({\mathsf {FC.FVer}}\) (without checking (1)), and selects messages according to the output m if verification passes,

Let \(\widehat{V}{}\) be the garbled circuit, and \({\{{\mathsf {okey}}_k[j,\beta ]\}}_{j}\) the set of keys for the input wires corresponding to \(\mathsf {key}'[k]\). (For clarity, we denote keys for \(\widehat{V}{}\) as \({\mathsf {okey}}\).)

Given a decommitment \(d= (\mathsf {key}', \rho ')\), correct WS decryption should recover messages \({\{\mathsf {M}[i,G(v)_i]\}}\) selected according to the correct output G(v) if the decommitment is valid, and \(\bot \) if invalid. To enable this, what is missing is a “translation mechanism” that can achieve the following: For every k,

• Correctness: if \((\mathsf {key}'[k], \rho '[k])\) is a valid decommitment to \(\mathrm {ot}_1[k, G[k]]\), it translates this pair into input keys of \(\widehat{V}{}\) corresponding to \(\mathsf {key}[k, G[k]]\), namely \({\{{\mathsf {okey}}_k[j,\mathsf {key}[k,G[k]]_j]\}}_j\).

• Security: the other keys \({\{{\mathsf {okey}}_k[j,1-\mathsf {key}[k,G[k]]_j]\}}_j\) are always hidden.

With such a translation mechanism, given a valid decommitment \(d = \{\mathsf {key}[k, G[k]],\rho [k, G[k]]\}\), one can obtain all input keys corresponding to \({\{\mathsf {key}[k, G[k]]\}}\), and can evaluate \(\widehat{V}{}\) with these keys to obtain the correct output,

The security of the translation mechanism and garbled circuit \(\widehat{V}{}\) guarantees that only the right messages \({\{\mathsf {M}[i, G(v)_i]\}}\) are revealed.

Our key observation is that the second flows of OT is exactly such a translation mechanism. For every OT first flows \(\mathrm {ot}_1[k,G[k]]\) selected by G, generate the OT second flows using appropriate input keys of \(\widehat{V}{}\) as sender’s inputs,

Indeed, for every k, given a valid decommitment \((\mathsf {key}[k, G[k]],\rho ')\) to \(\mathrm {ot}_1[k,G[k]]\), one can act as an OT receiver to recover input keys \({\{{\mathsf {okey}}_k\left[ j,\mathsf {key}[k,G[k]]_j\right] \}}_j\), achieving correct translation. On the other hand, the OT sender’s security guarantees that the other keys \({\{{\mathsf {okey}}_k\left[ j,1-\mathsf {key}[k,G[k]]_j\right] \}}_j\) remain hidden.

Summarizing the above ideas gives the following construction of WS for \({\mathsf {FC}}\):

• \(\mathsf {WS.Enc}((c,G), \mathsf {M})\): To encrypt \(\mathsf {M}\) under (c, G), encryptor garbles the circuit V as in Eq. (2), and generates the second OT flows as in Eq. (4). The WS ciphertext is \(\mathsf {ct}= (c, G, \widehat{V}{}, {\{\mathrm {ot}_2[k]\}})\).

• \(\mathsf {WS.Dec}(\mathsf {ct},d)\): To decrypt \(\mathsf {ct}\) with a decommitment \(d = {\{\mathsf {key}', \rho '\}}\), the decryptor first verifies that for every k \((\mathsf {key}'[k], \rho '[k])\) is a valid decommitment of \(\mathrm {ot}_1[k, G[k]]\) in c; otherwise, abort. Then, for every k, it acts as an OT receiver with input \(\mathsf {key}'[k]\), randomness \(\rho '[k]\), and OT sender’s message \(\mathrm {ot}_2[k]\) to recover input keys of \(\widehat{V}{}\) corresponding to \(\mathsf {key}'[k]\). Finally, it evaluates \(\widehat{V}{}\) with the obtained keys and output the messages output by \(\widehat{V}{}\), as in Eq. (3).

The correctness and security of the WS scheme follows directly from the correctness and security of the translation mechanism, which are in turn implied by those of OT. See the full version [7] for more details.

Combining Sects. 2.1 to 2.5, we get a construction of a 2-round semi-honest MPC protocol from any 2-round semi-honest OT protocol using round collapsing for an inner MPC protocol.

2.6 Semi-Malicious and Malicious Security in the CRS Model

Toward achieving malicious security, we first achieve semi-malicious security. Roughly speaking, a semi-malicious party \(P_j\) generates its messages according to the protocol using arbitrarily and adaptively chosen inputs and random tapes. This is formalized by letting \(P_j\) “explain” each message \(m^{\ell }_j\) it sends with a pair of input and random tape consistent with it, on a special witness tape. In the two-round setting, the challenge in simulating the view of \(P_j\) lies in simulating honest parties’ first messages without knowing any secret information of \(P_j\). This is because \(P_j\) may rush to see honest parties’ first messages before outputting its own message, input, and random tape. (Observe that this is not an issue for semi-honest security, as the simulator learns the inputs and random tapes of corrupted parties first.)

Recall that in our 2-round protocols, each party \(P_i\) sends functional commitments \(c_i\) to its input and random tape \((x_i,r_i)\) in the first round, which are later partially decommitted to reveal \(P_i\)’s messages m in the inner MPC protocol. The simulation property of the functional commitment scheme \({\mathsf {FC}}\) ensures that the commitment and decommitment can be simulated together using just the message. However, this is insufficient for achieving semi-malicious security, as the simulator must simulate commitments in the first round with no information. To overcome this problem, we strengthen the simulatability of \({\mathsf {FC}}\) to equivocability, that is, simulation takes the following two steps: First, a commitment \(\tilde{c}\) is simulated with no information, and later it is equivocated to open to any output m w.r.t. any circuit G. Instantiating our 2-round MPC protocols with such an equivocal functional commitment scheme, and other primitives that are semi-maliciously secure (e.g., using a semi-maliciously secure multi-round MPC protocol, and 2-round OT protocol), naturally “lift” semi-honest security to semi-malicious security.

With a simple idea, we can transform any simulatable functional commitment scheme \({\mathsf {FC}}\) into an equivocal one \(\mathsf {eFC}\): Let \((\mathsf {OT}_1, \mathsf {OT}_2)\) be the sender and receiver’s algorithms of a 2-out-of-1 OT scheme.

• To commit to v, generate a \({\mathsf {FC}}\) commitment c to v, and then commit to each bit \(c_i\) twice using the algorithm \(\mathsf {OT}_1\), yielding the \(\mathsf {eFC}\) commitment:

  $$\begin{aligned} ec = {\left\{ \mathrm {ot}_1[i,0] = \mathsf {OT}_1(c_i;\ r[i,0]),\ \mathrm {ot}_1[i,1] = \mathsf {OT}_1(c_i;\ r[i,1]) \right\} }_i \,. \end{aligned}$$

• An \(\mathsf {eFC}\) decommitment (ed, G(v)) to (ec, G) contains the \({\mathsf {FC}}\) decommitment (d, G(v)) to (c, G), and the OT randomness \({\{r[i,c_i]\}}\) for generating the set of first flows \({\{\mathrm {ot}_1[i,c_i]\}}\) selected by c. Note that for any ec generated according to the above commitment algorithm, the revealed OT randomness determines the commitment c, and then the \({\mathsf {FC}}\) decommitment d determines G(v).

• Now, a commitment can be simulated by committing to both 0 and 1 in ec,

  $$\widetilde{ec} = {\{\mathrm {ot}_1[i,0] = \mathsf {OT}_1(0;\ r[i,0]),\ \mathrm {ot}_1[i,1] = \mathsf {OT}_1(1;\ r[i,1]) \}}_i \,.$$

  To decommit \(\widetilde{ec}\) to output G(v), first simulate the \({\mathsf {FC}}\) commitment and decommitment \((\tilde{c}, \tilde{d})\) together using G(v), and then reveal the set of randomness \({\{r[i, \tilde{c}_i]\}}\) selected according to the simulated commitment \(\tilde{c}\).

The WS scheme associated with \(\mathsf {eFC}\) can be constructed similarly as that for \({\mathsf {FC}}\). The above idea is conceptually simple, but leads to nested calls of \(\mathrm {p}\mathsf {OT}_1\)/\(\mathsf {OT}_1\), as a \({\mathsf {FC}}\) commitment c already contains OT first flows. This is not a problem when using 2-round OT, but does not extend to multi-round OT. In the full version [7], we present a more involved construction that avoids nested calls.

Malicious Security in the CRS Model. Given 2-round semi-maliciously secure protocols, in the CRS model, we can let each party prove using NIZK that each message is generated in a semi-malicious way (i.e., according to the protocol w.r.t. some input and random tape) as done in [2], which immediately gives Corollary 1.3 in the introduction. We refer the reader to [2] for more details.

Extension to k Rounds. Our 2-round semi-honest or semi-malicious constructions so far can be extended to k-round constructions, when replacing the underlying 2-round OT protocols with semi-honest or semi-malicious k-round OT protocols. See the full version [7] for more details.

2.7 Malicious Security in the Plain Model

We first show a new compilation that turns any \((k-1)\)-round MPC protocol for computing f satisfying a stronger variant of semi-malicious security, called delayed-semi-malicious security, into a k-round malicious MPC protocol for f, assuming only one-way functions, for any \(k \ge 5\). Roughly speaking, a delayed-semi-malicious party \(P_j\) acts like a semi-malicious party, except that, it only “explains” all its messages once, before the last round (instead of explaining each of its messages after each round). This is formalized by letting \(P_j\) output a pair of input and random tape before the last round (on its special witness tape) which is required to be consistent with all \(P_j\)’s messages. We say that a protocol is delayed-semi-malicious secure if it is secure against such adversaries. (For technical reasons, we require the protocols to have a universal simulator.) We observe that our k-round semi-malicious MPC protocols, when instantiated with a k-round delayed-semi-malicious OT become secure against delayed semi-malicious attackers (and admit a universal simulator).

To “lift” delayed-semi-malicious security to malicious security generically, our compilation builds on techniques of [1]. To illustrate the idea, consider compiling our 2-round delayed-semi-malicious MPC protocol \(\varPhi \) for f into a 5-round malicious MPC protocol \(\varPi \) for f. The basic idea is running \(\varPhi \) for computing f, and restricting a malicious adversary A to act as a delayed-semi-malicious one \(A'\) by requiring A to prove using zero-knowledge proof of knowledge (ZKPOK) that its messages in each round of \(\varPhi \) are generated correctly according to some input and random tape. Unlike the CRS model, ZKPOK in the plain model requires at least 4 rounds. Sequentializing the two ZKPOK leads to a 8-round protocol. But if the ZKPOK allows for delayed-input, that is, only the last prover’s message depends on the statement and witness, then the two ZKPOK can be partially parallelized, leading to a 5-round protocol. In addition, in order to prevent mauling attacks, the ZKPOK must be non-malleable. Fortunately, Ciampi, Ostrovsky, Siniscalchi, and Visconti [20] (COSV) recently constructed a 4-round delayed-input non-malleable ZKPOK protocol from one-way functions, which suffice for our purpose. When starting from a 4-round (instead of 2-round) protocol \(\varPhi \), to obtain a 5-round malicious protocol \(\varPi \), we cannot afford to prove correctness of each round. But, if \(\varPhi \) is delayed-semi-malicious secure, then it suffices to prove correctness only at the last two rounds, keeping the round complexity at 5.

Though the high-level ideas are simple, there are subtleties in the construction and proof. We cannot use the non-malleable ZKPOK in a black-box. This is because simulation of non-malleable ZKPOK uses rewindings and may render the \(\varPhi \) instance running in parallel insecure. In addition, the COSV non-malleable ZKPOK is only many-many non-malleable in the synchronous setting, but in \(\varPi \), the non-malleable ZKPOKs are not completely synchronized (ending either at the second last or the last round). Therefore, we use the COSV construction in a non-black-box way in \(\varPi \) (with some simplification) as done in [1]. The specific property of COSV non-malleable ZKPOK that we rely on is that simulation requires only rewinding the second and third rounds, while (witness) extraction requires only rewinding the third and forth rounds. This means \(\varPhi \) would be rewound at second/third and third/fourth rounds. The security of a generic delayed-semi-malicious protocol may not hold amid such rewinding. However, if we start with a 4-round protocol, rewindings can be circumvented if \(\varPi \) contains no messages of \(\varPhi \) in its third round. This means, in the rewindings of second/third and third/fourth rounds, the simulator can simply replay messages of \(\varPhi \) in the main thread, keeping the instance of \(\varPhi \) secure. See the full version [7] for details.

The above transformation is modular and general, but comes at a price—it only gives k-round malicious MPC from \((k-1)\)-round delayed-semi-malicious OT, which is not necessary. To eliminate the gap, we leverage specific structures of our k-round delayed-semi-malicious protocols, to address the rewinding issue above. To illustrate the ideas, lets again examine the \(k=5\) case.

To handle rewindings at third/fourth rounds, we observe that at the end of fourth round, each party \(P_i\) proves using COSV non-malleable ZK that it has acted honestly in \(\varPhi \) according to some input and random tape \((x_i, r_i)\). If in the malicious protocol \(\varPi \), each party additionally commits to \((x_i, r_i)\) in the first two rounds using a statistically binding commitment scheme (and prove that its messages are generated honestly using the committed value). Then, as long as the adversary cannot cheat in the non-malleable ZK proofs, its messages in the third/fourth rounds of \(\varPhi \) are determined by the commitments in the first two rounds. Therefore, the simulator can afford to continuously rewinding the adversary, until it repeats its messages in \(\varPhi \) in the main execution thread. In this case, the simulator can simply replay the honest parties’ messages in \(\varPhi \) in the main thread.

To handle rewindings at second/third rounds, the specific property of our protocol that we rely on is that the first 2 rounds of \(\varPhi \) contains only instances of OT, whose messages do not depend on parties’ inputs. The latter holds because of the random self-reducibility of OT (hence, the sender and receiver can only use their inputs for generating their last messages). To avoid rewinding these OT instances in \(\varPhi \), our idea is modifying the malicious protocol \(\varPi \) as follows: In the first 2 rounds, for every OT instance \(\mathsf {OT}_j\) in \(\varPhi \), \(\varPi \) runs two independent OT instances \(\mathsf {OT}_j^0\) and \(\mathsf {OT}_j^1\). In the third round, an random instance \(\mathsf {OT}_j^{b_j}\) for \({b_j} \leftarrow {\{0,1\}}\) is chosen to be continued, and the other \(\mathsf {OT}_j^{1-{b_j}}\) aborted—they are referred to as the real and shadow instances. Now in a rewinding of the second/third round, to avoid rewinding the real OT instances, the simulator replays the OT messages in the second round, and in the third round, continues the shadow instances \(\mathsf {OT}_j^{1-{b_j}}\) and aborts the real instances \(\mathsf {OT}_j^{b_j}\). Importantly, since for every pair \((\mathsf {OT}_j^0, \mathsf {OT}_j^1)\), the choice \({b_j}\) of which is real and which is shadow is random and independent, the view of the adversary in a rewinding is identical to that in the main execution thread. This guarantees that rewindings would succeed.

We remark that this idea does not apply in general. This is because to continue a random instance of a general protocol \(\varPhi \) in the third round, parties may need to agree on that instance, which requires coin-tossing. In contrast, our protocol \(\varPhi \) consists of many OT instances \(\mathsf {OT}_j\), the decision of which of \((\mathsf {OT}_j^0,\mathsf {OT}_j^1)\) to continue can be made locally by the party who is supposed to send the third message of \(\mathsf {OT}_j\) in \(\varPhi \). In the full version [7], we put the above two ideas together, which gives k-round malicious OT from k-round delayed-semi-malicious OT.

A figure summarizing the results is provided in the full version [7].