Multiparty Reusable Non-interactive Secure Computation from LWE | Springer Nature Link

We now give an overview of our construction of mrNISC protocols in the plain model from LWE with polynomial modulus and PRF in \(\mathrm {NC}^1 \).

2.1 Review of Definition of mrNISC Protocols

Towards constructing mrNISC protocols, the work of [22] defined the notion of mrNISC schemes, with a game-based security definition. Furthermore, they showed that a mrNISC scheme immediately yields a mrNISC protocol that UC-implements an ideal mrNISC functionality that allows for any number of computations over any subsets of inputs registered by parties. Thus, in this work, we focus on implementing mrNISC schemes for polynomial-size circuits.

mrNISC Scheme. An n-party functionality \(\mathcal {U}\) is a represented by a Boolean circuit that takes a public input z and n private inputs. If \(\mathcal {U}\) is a universal circuit and z specifies the actual function to be computed, then this formalism allows the parties of the mrNISC to compute any function on their private inputs. An mrNISC scheme for \(\mathcal {U}\), consists the following three algorithms:

• Input Encoding: A party \(P_i\) encodes its private input \(x_i\) by invoking \((\hat{x}_i, s_i)\leftarrow \mathsf {Com}(1^\lambda , x_i)\). It then publishes the encoding \(\hat{x}_i\) and keeps the secret state \(s_i\).

• Computation: In order for a subset of parties \({\{P_i\}}_{i \in I}\) to compute the functionality \(\mathcal {U}\) on their private inputs \({\boldsymbol{x}}_I\) and a public input z, each party in I generates a computation encoding \(\alpha _{i} \leftarrow \mathsf {Encode}( z, {\{\hat{x}_j\}}_{j \in I}, s_i)\) and sends it to the evaluator.

• Output: The evaluator reconstructs the output \(y = \mathsf {Eval}(z, {\{\hat{x}_i\}}_{i \in I}, {\{\alpha _{i}\}}_{i \in I})\). (Note that reconstruction is public as the evaluator has no secret state.) Correctness requires that \(y=\mathcal {U}(z,{\{x_i\}}_{i\in I})\) when everything is honestly computed.

Simulation-security requires that the view of an adversary corrupting the evaluator and a subset of parties, can be simulated using just the outputs of the computations.^{Footnote 5} Following [22], we consider static corruptions and semi-malicious security. Static corruptions restrict the adversary to corrupt a fixed subset C of parties chosen at the very beginning, and semi-malicious security [10] restricts the corrupted parties \({\{P_i\}}_{i \in C}\) to follow the protocol specification, but allows the adversary to choose their inputs and randomness \({\{x_i, r_i\}}_{i \in C}\) arbitrarily. During an execution of the mrNISC scheme for \(\mathcal {U}\), honest and corrupted parties \(P_i\) can register their inputs by posting input encodings \(\hat{x}_i\). Multiple computations, each specified by \((z^k, I^k)\), can be carried out as follows: each \(P_i\) for \(i \in I^k\) sends the corresponding computation encoding \(\alpha ^k_i\), which together reveal \(y^k = \mathcal {U}(z^k,{\{x_i\}}_{i \in I^k})\). All the messages from the honest parties, including \({\{\hat{x}_i\}}_{i \not \in C}\) and \({\{\alpha ^k_i\}}_{k, i \in I^k \setminus C}\), must be simulatable from the outputs \({\{y^k\}}_k\), the public information of the computations \({\{z^k, I^k\}}_k\), and the input and randomness of the corrupted parties \({\{x_i, r_i\}}_{i \in C}\). Furthermore, simulation must hold in the adaptive setting, where the input and computation encodings are interleaved and all \(x_i\) and \((z^k, I^k)\) are chosen adaptively by the adversary.

2.2 Step 1: Reusable Functional OT from LWE

We identify a complete 2-party function, called functional OT \(\mathcal {U}_{\mathrm {fOT}}\), and show 1) how to construct a 2-party reusable NISC scheme for computing \(\mathcal {U}_{\mathrm {fOT}}\) in the plain model, and 2) how to bootstrap from \(\mathcal {U}_{\mathrm {fOT}}\) to general mrNISC scheme for any circuit \(\mathcal {U}\in \mathrm {P} \).

Functional OT. \(\mathcal {U}_{\mathrm {fOT}}\) takes three inputs: A public input consisting of two functions \(g_1:\{0,1\}^{n_1}\rightarrow \{0,1\}^{\lambda }\times \{0,1\}^{\lambda }\) and \(g_{2}:\{0,1\}^{n_2}\rightarrow \{0,1\}\) represented as Boolean circuits, a private input \(x_1 \in \{0,1\}^{n_1}\) from a party \(P_1\) acting as the \(\mathcal {U}_{\mathrm {fOT}}\) sender \(x_2\in \{0,1\}^{n_2}\) from a party \(P_2\) acting as the \(\mathcal {U}_{\mathrm {fOT}}\) receiver, and computes:

The name functional OT comes from the fact that both the OT sender’s strings \(\ell _0, \ell _1\) and receiver’s choice bit \(c\) are functions on sender’s and receiver’s private inputs \(x_1\) and \(x_2\).

A 2rNISC scheme for computing \(\mathcal {U}_{\mathrm {fOT}}\) provides a way to encode the private input \(x_i\) of any party \(P_i\), so that later any two parties \(P_{i}\) and \(P_{j}\) can securely compute \(\mathcal {U}_{\mathrm {fOT}}\) (acting as sender and receiver respectively) to reveal only \((c,\ell _{c})\) computed according to arbitrarily chosen functions \((g_1, g_2)\) and their private inputs \(x_{i}\) and \(x_{j}\), by each sending a single message. Importantly, the encoding \(\hat{x}_{i}\) of \(P_i\) is reusable in any number of \(\mathcal {U}_{\mathrm {fOT}}\) computations with different parties and different functions. Note that different from classical OT where \((c, \ell _c)\) is private to the receiver, a 2rNISC scheme allows to reconstruct \((c, \ell _c)\) publicly given all messages sent. Jumping ahead, this feature serves exactly the purpose of achieving the public reconstruction property of mrNISC.

Constructing 2rNISC for \(\mathcal {U}_{\mathrm {fOT}}\). We construct 2rNISC for \(\mathcal {U}_{\mathrm {fOT}}\) in the plain model from LWE with just polynomial modulus and PRF in \(\mathrm {NC}^1 \) in two steps: We start with designing a scheme \(\varPi _{\mathrm {fOT}}= (\mathsf {Com},\mathsf {Encode}, \mathsf {Eval})\) that handles only circuits \(g_2\) with bounded logarithmic depth \(O(\log \lambda )\) (whereas the depth of \(g_1\) is unrestricted), and then bootstrap \(\varPi \) to 2rNISC that handles \(g_2\) with unbounded polynomial depth.

  Our 2rNISC makes use of the GSW homomorphic encryption scheme [46], which can be turned into a homomorphic commitment scheme (or homomorphic trapdoor functions) as done in [49]. It enables us to commit to a string \(\boldsymbol{x} \in \{0,1\}^{n}\) in a commitment \(\mathbf {C}\), and then homomorphically evaluate any circuit f on \(\mathbf {C}\) to obtain a commitment \(\mathbf {C}_{f}\) to \(f(\boldsymbol{x})\). More concretely, the scheme publishes a CRS \(\mathsf {crs}= \mathbf {A}\) containing a matrix of dimension \(N\times M\) for \(M = \varOmega (N\cdot \log q)\); the matrix \(\mathbf {A} = {[\mathbf {B}^{\top } \vert \boldsymbol{b}^\top _{1}\vert \ldots \vert \boldsymbol{b}^\top _{k}]}^{\top }\) consists of a random submatrix \(\mathbf {B} \leftarrow \mathbb {Z}_q^{(N-k)\times M}\), together with k LWE samples \({\{b_l = \boldsymbol{t}_l\mathbf {B} + \boldsymbol{e}_l\}}_{l \in [k]}\) w.r.t. independently sampled secret \(\boldsymbol{t}_l\) and noise \(\boldsymbol{e}_l\), where \(\boldsymbol{e}_1\) is sampled from a truncated discrete Gaussian distribution and always bounded by \(|\boldsymbol{e}_l|_\infty \le B\). Committing to a binary string \(\boldsymbol{x}\) simply involves encrypting each bit \(x_i\) using GSW encryption and public key \(\mathbf {A}\), and the encryption randomness is the decommitment.

We note two important details: First, the matrix \(\mathbf {A}\) corresponds to the public key in GSW encryption; here, we insist on it containing \(k>1\) LWE samples, where k is a parameter that scales with the input length of the parties. Second, when \(\mathbf {A}\) is sampled honestly at random, it satisfies the following well-formedness with overwhelming probability: 1) it is generated as above using some \(\mathbf {B}\), \(\boldsymbol{t}_l\), and B-bounded \(\boldsymbol{e}_l\)’s, and 2) vectors \(\boldsymbol{e}_l\)’s are linearly independent over the integers. Observe that the well-formedness can be verified efficiently given the random coins used to sample \(\mathbf {A}\). For any \(\mathbf {A}\) satisfying property 1), commitments w.r.t. \(\mathbf {A}\) are statistical binding, and in fact even extractable using the secrets \(\boldsymbol{t}_l\)’s. We shall see how property 2) is helpful later.

The homomorphism of GSW enables homomorphic evaluation over the commitments to obtain a commitment to \(f(\boldsymbol{x})\) as follows

The new decommitment \(\mathbf {R}_f\) can be evaluated directly from \({\{\mathbf {R}_i\}}, {\{\mathbf {C}_i\}},\boldsymbol{x}\) and in particular is linear in the original decommitments \(\mathbf {R}_i\)’s.

  To construct 2rNISC for functional OT, our idea is letting each player \(P_i\) commit to its input \(\boldsymbol{x}\) as the input encoding, and keep the decommitment as its private state. Note that the homomorphic commitments require a CRS, but we wish to construct 2rNISC in the plain model. Thus, we let each player choose its own CRS.

Later two parties, \(P_1\) acting as the sender and \(P_2\) acting as the receiver, wish to compute functional OT w.r.t. \((g_1, g_2)\) on their private inputs denoted as \(\boldsymbol{x}_1\) and \(\boldsymbol{x}_2\), and have encodings and secret states denoted as \((\hat{{\boldsymbol{x}}}_b = (\mathbf {A}_b,{\{\mathbf {C}_{b,i}\}}), s_b = {\{\mathbf {R}_{b,i}\}})\) with \(b = 1\) for \(P_1\) and \(b = 2\) for \(P_2\). \(P_1\) can privately compute sender’s strings \((\ell _0, \ell _1) = g_1(\boldsymbol{x}_1)\), and \(P_2\) the receiver’s choice \(c= g_2(\boldsymbol{x}_2)\). In addition, given \(\hat{\boldsymbol{x}}_2\), both parties can homomorphically evaluate \(g_2\) to obtain a commitment \(\mathbf {C}_{g_2} = \mathbf {A}_2 \mathbf {R}_{g_2} + c\mathbf {G}\) to \(c\), while \(P_2\) additionally knows the decommitment \(\mathbf {R}_{g_2}\).

At this point, we wish to have the following two components to enable computing \(\ell _c\) non-interactively.

• Witness Encryption of Sender’s Strings \((\ell _0, \ell _1)\): \(P_1\) would like to witness encrypt \(\ell _b\) w.r.t. the statement that, under CRS \(\mathbf {A}\), \(\mathbf {C}_{g_2}\) is a commitment to bit b, so that, \(\ell _b\) is revealed given a witness that is a decommtiment to b, and is hidden if \(\mathbf {C}_{g_2}\) is a commitment to \(1-b\). Then the sender’s computation encoding is

  $$\begin{aligned} \mathsf {Encode}((g_1, g_2), (\hat{x}_1, \hat{x}_2), s_1) \ : \ \alpha _1 = {\{\boldsymbol{w}_b \leftarrow \mathsf {WEnc}((\mathbf {A}_2, \mathbf {C}_{g_2}, b), \ell _b)\}}_{b \in {\{0,1\}}} \end{aligned}$$

• Zero-Knowledge Decommitment to Receiver’s Choice \(c\): \(P_2\) would like to open \(\mathbf {C}_{g_2}\) to \(c\) by sending a decommitment, in a zero-knowledge way that reveals only \(c\) and nothing more about \(\boldsymbol{x}_2\). Note that the basic decommitment \(\mathbf {R}_{g_2}\) is not zero-knowledge and may reveal information of \(\boldsymbol{x}_2\).

  $$\begin{aligned} \mathsf {Encode}((g_1, g_2), (\hat{x}_1, \hat{x}_2), s_2 = {\{\mathbf {R}_i\}}_i) \ : \ \alpha _2 = (\mathbf {X}_{g_2} \leftarrow \mathsf {ZKDecom}(g_2, \mathbf {C}_{g_2}, \mathbf {R}_{g_2}))~, \end{aligned}$$

  where \(\mathsf {ZKDecom}\) produces a zero-knowledge decommitment \(\mathbf {X}_{g_2}\).

An evaluator given \((\alpha _1, \alpha _2)\) can witness decrypt to obtain \(\ell _c\) as desired.

  The main technical challenge is co-designing WE and ZK decommitments so that the latter can decrypt the former. For this we will draw techniques from previous works for constructing context-hiding homomorphic signatures [49] and 2-message statistically sender private OT [24]. At the same time, we crucially rely on the fact that our 2rNISC only need to be secure against semi-malicious adversaries to simplify the requirements on WE and ZK decommitments. The key observation is that a semi-malicious corrupted party \(P_2\) must generate its input encoding \((\mathbf {A}_2, {\{\mathbf {C}_{2,i}\}}_i)\) using the honest algorithm, albeit using arbitrary randomness. This means that i) \(\mathbf {A}_2\) must be well-formed and ii) \({\{\mathbf {C}_{2,i}\}}_i\) must be a valid commitment \({\{\mathbf {A}_2 \mathbf {R}_i + x_{2,i}\mathbf {G}\}}_i\) to some input \(\boldsymbol{x}_2\) with a decommitement \(\mathbf {R}_i\) of 1/−1 values. As a result, \(\mathbf {C}_{g_2} = \mathbf {A}_2 \mathbf {R}_{g_2} + g_2(\boldsymbol{x}_{2})\mathbf {G}\) must be a valid commitment to \(g_2(\boldsymbol{x}_2) = 0/1\) with a decommitment \(\mathbf {R}_{g_2}\) of small magnitude^{Footnote 6}.

Therefore, the correctness and security of WE and ZK decommitments only need to hold w.r.t. well-formed \(\mathbf {A}\) (i.e., \(\mathbf {A}_2\)) and valid commitment \(\mathbf {C}\) (i.e., \(\mathbf {C}_{g_2}\)) to 0/1 with small decommitment, and does not need to hold w.r.t. ill-formed \(\mathbf {A}\) or invalid commitment \(\mathbf {C}\)—we refer to this as the promise version of WE and ZK decommitments:

• Yes instances \((\mathbf {A}, \mathbf {C}, b)\) contain a well-formed \(\mathbf {A}\) and a valid commitment \(\mathbf {C}\) to bit b, and we require the ZK property of the decommitments and correctness of WE for them.

• No instances \((\mathbf {A}, \mathbf {C}, b)\) contain a well-formed \(\mathbf {A}\) and a valid commitment \(\mathbf {C}\) to bit \(1-b\), and we require the hiding property of WE for them.

Thanks to the fact that it suffices to focus on the promise version, we manage to give a relatively simple construction of WE and ZK decommitment. Next we proceed to their description; by default, all matrices \(\mathbf {A}\)’s are well-formed and commitments \(\mathbf {C}\)’s are valid 0/1 commitments.

  The context-hiding homomorphic signature schemes of [49] provides a way to generate zero-knowledge decommtiments. If the committer wishes to open \(\mathbf {C}_f = \mathbf {A} \mathbf {R}_f + f(\boldsymbol{x})\mathbf {G}\) to \(f(\boldsymbol{x}) = b\) w.r.t. CRS \(\mathbf {A}\), it constructs the matrix

and uses \(\mathbf {R}_f\) as a right-trapdoor [2, 31] of \({\mathbf {D}^{(b)}}\) to sample a short \(B'\)-bounded vector \(\boldsymbol{v}\), for appropriately set \(B'\) such that, \({\mathbf {D}^{(b)}}\boldsymbol{v} = \boldsymbol{u}\), where \(\boldsymbol{u}\) is a random vector published additionally in the CRS. The vector \(\boldsymbol{v}\) is the new decommitment.^{Footnote 7} \(\boldsymbol{v}\) together with \(\mathbf {A}\) and the original commitment \({\{\mathbf {C}_i\}}\) to \(\boldsymbol{x}\) reveals no more information beyond that \(f(\boldsymbol{x}) =b\), since they can be jointly simulated using only (f, b), by sampling \(\mathbf {A}\) at random with a trapdoor \(\mathbf {T}_{\mathbf {A}}\) [2, 54], \(\mathbf {C}_i\)’s at random, and \(\boldsymbol{v}\) using \(\mathbf {T}_{\mathbf {A}}\) as a left-trapdoor of \({\mathbf {D}^{(b)}}\). A random \(\mathbf {A}\) is computationally indistinguishable from a well-formed \(\mathbf {A}\) by LWE, and \(\boldsymbol{v}\) sampled using the left or the right trapdoor is statistically close.

However, we do not know how to construct a matching WE for verifying the above ZK decommitment and need to modify the decommitment as follows. The new decommitment of \(\mathbf {A}, \mathbf {C}_f\) to \(f(\boldsymbol{x}) = b\) contains a short \(B'\)-bounded basis \(\mathbf {X}_f \in \mathbb {Z}^{M'\times M'}\) of the lattice \(\varLambda ^\bot _q(\mathbf {{\mathbf {D}^{(b)}}}) = {\{ \boldsymbol{z} \in \mathbb {Z}^{M'} \ : \mathbf {{\mathbf {D}^{(b)}}}\boldsymbol{z} = \boldsymbol{0} \pmod q \}}\) over the integers, that is, \(\mathbf {{\mathbf {D}^{(b)}}}\mathbf {X}_f = \boldsymbol{0}^{N \times M'}\) and is \(\mathbf {X}_f\) has full rank over the integers. Such a basis can be sampled again using \(\mathbf {R}_f\) as a right-trapdoor of \({\mathbf {D}^{(b)}}\), and can be simulated together with \(\mathbf {A}, {\{\mathbf {C}_i\}}\) by sampling \(\mathbf {A}\) without a trapdoor \(\mathbf {T}_{\mathbf {A}}\) and using it as a left-trapdoor of \({\mathbf {D}^{(b)}}\) to sample the basis. In summary, our ZK decommitment is generated as:

where \(\mathbf {T}_{\mathbf {G}}\) is a trapdoor of the gadget matrix \(\mathbf {G}\) and \(\alpha \) controls the norm of the trapdoor.

  To design a compatible WE that can be decrypted using the above ZK decommitments. we crucially rely on the following fundamental properties of lattices defined by a matrix \(\mathbf {D} \in \mathbb {Z}_q^{N \times M'}\).

• If the lattice \(\varLambda ^\bot _q(\mathbf {D}) = {\{ \boldsymbol{z} \in \mathbb {Z}^{M'} \ : \mathbf {D}\boldsymbol{z} = \boldsymbol{0} \pmod q \}}\) has a \(B'\)-bounded basis \(\mathbf {X}\) over the integers, then vectors of form \(\boldsymbol{s} \mathbf {D} + \boldsymbol{e}\) can be efficiently decoded using \(\mathbf {X}\), and \(\boldsymbol{s}\) can be recovered, provided that the norm of \(\boldsymbol{e}\) is sufficiently smaller than \(q/{B'}\).

• On the other hand if the lattice \(\varLambda _q(\mathbf {D}) = {\{ \boldsymbol{y} \in \mathbb {Z}^{M'} \ : \boldsymbol{y} = \boldsymbol{s} \mathbf {D} \pmod q \}}\) contains k linearly independent vectors of norm \(\ll q/{B'}\), then vectors of form \(\boldsymbol{s} \mathbf {D} + \boldsymbol{e}\) is lossy and \(\boldsymbol{s}\) has n bits of entropy, if k is sufficiently larger than n. This is essentially because the components of \(\boldsymbol{s} \mathbf {A}\) in the direction the short vectors are masked by \(\boldsymbol{e}\).

The work of [24] relied on the above properties in their construction of two message statistically sender-private OT from LWE. We here rely on them to achieve respectively the correctness and hiding property of our promise WE. To encrypt a string \(\ell _b\), under a statement \((\mathbf {A}, \mathbf {C} = \mathbf {C}_f, b)\), our WE does:

where \(\mathsf {Ext}\) is a strong seeded extractor and \(\mathsf {sd}\) is a randomly sampled seed, \(\boldsymbol{s}_b\) is a random secret from \(\mathbb {Z}_q^{N}\), and \(\boldsymbol{e}_b\) is from a truncated discrete Gaussian distribution with appropriate parameter.

• Correctness for Yes Instances: For a well-formed \(\mathbf {A}\) and a valid commitment \(\mathbf {C} = \mathbf {A} \mathbf {R} + b\mathbf {G}\) to b, the ZK decommitment \(\mathbf {X}\) is exactly a short-basis of \(\varLambda ^{\bot }_q(\mathbf {D}^{(b)})\). Therefore, by the first lattice property, given \(\mathbf {X}\), the decryptor can efficiently decode \(\boldsymbol{w}_b\) to obtain \(\boldsymbol{s}_b\) and then recover \(\ell _b\).

• Hiding for No Instances: For a well-formed \(\mathbf {A}\) and a valid commitment \(\mathbf {C} = \mathbf {A} \mathbf {R} + (1-b) \mathbf {G}\) to \(1-b\), \(\mathbf {D}^{(b)} = [\mathbf {A} \mid \mathbf {A}\mathbf {R}]\) and hence the lattice \(\varLambda _q(\mathbf {D}^{(b)})\) contains at least k short vectors. This is because, by the structure of a well-formed \(\mathbf {A}\), for every \(l \in [k]\), \((-\boldsymbol{t}_l||1)\mathbf {D}^{(b)} = (\boldsymbol{e}_l || \boldsymbol{e}_l \mathbf {R})\) is short as \(\boldsymbol{e}_l\) and \(\mathbf {R}\) are. Moreover, these vectors are independent as long as \(\boldsymbol{e}_l\)’s are (and \(k < \dim (\boldsymbol{e}_l) = M\)), where the latter is guaranteed by the (second requirement of) well-formedness of \(\mathbf {A}\). Therefore, by the second lattice property, \(\boldsymbol{s}_b\) has n bits of entropy conditioned on \(\boldsymbol{w}_b\) and the output of the extractor information theoretically hides \(\ell _b\).

  Combining the homomorphic commitment scheme with ZK decommitments and the witness encryption, we obtain 2rNISC for computing functional OT with semi-malicious security. Let’s now examine the magnitude of the modulus, which we wish to be polynomial. Based on LWE, to support homomorphic evaluation of a circuit \(g_2\) of depth d requires the modulus to grow exponentially in d. Therefore, only when d is a fixed logarithmic function in the security parameter \(\lambda \), would the modulus be a fixed polynomial in \(\lambda \) as desired.

Following a technique used in [22], we can generically bootstrap to 2rNISC supporting circuits \(g_2\) with unbounded polynomial depth, with the help of a \(\mathsf {PRF}\) in \(\mathrm {NC}^1 \) and Yao’s garbled circuits. At a high-level, \(P_1\) is going to hide the sender’s string \(\ell _b\) in a garbled circuit \(\hat{G}_{\ell _b}\) for a function \(G_{\ell _b}(\varLambda )\) that on input a randomized encoding \(\varLambda \), outputs \(\ell _b\) iff \(\varLambda \) evaluates to b. At evaluation time, the evaluator will obtain the set of labels \({\{\bar{\ell }_j\}}\) of \(\hat{G}_{\ell _b}\) corresponding exactly to a randomized encoding \(\varLambda \) of \((g_2, \boldsymbol{x}_2)\) generated using pseudorandom coins expanded via \(\mathsf {PRF}\) on a key \(k_2\) belong to the receiver \(P_2\). Then the evaluator can recover \(\ell _b\) iff \(g_2(\boldsymbol{x}_2) =b\). Crucially, the task for revealing the labels corresponding to \(\varLambda \) can exactly be accomplished using 2rNISC for logarithmic-depth receiver’s circuits, as every bit of \(\varLambda \) can be computed by a logarithmic-depth circuit evaluated on \((\boldsymbol{x}_2, k_2)\) if \(\mathsf {PRF}\in \mathrm {NC}^1 \). Correspondingly, every party now needs to commit to their private input \(\boldsymbol{x}\) and a PRF key k. This yields our final 2rNISC for functional OT from LWE with polynomial modulus and \(\mathsf {PRF}\) in \(\mathrm {NC}^1 \).

2.3 Step 2: 2rNISC for Functional OT to General mrNISC for \(\mathrm {P} \)

We construct general mrNISC for polynomial-sized circuits from 2rNISC for functional OT following a similar approach as [22], which in turn is based on the round collapsing approach for constructing 2-round MPC protocols started in [39, 50]. The round-collapsing approach collapses an inner MPC protocol with a polynomial L number of rounds into a 2-round outer MPC protocol, essentially by letting every party garble its next-step message function for computing the inner MPC messages. The challenge lies in how to enable the garbled circuits generated independently by different parties “talk” to each other: the output of one party’s garbled circuit is the input of another party’s garbled circuit. What is new in this work is that we use 2rNISC for functional OT to enable this, which is weaker than the tools used in previous works. Specifically, the work of [22] proposed and constructed a primitive called Witness Encryption for NIZK of commitments, which is a witness encryption scheme for verifying NIZK proof of the correctness of deterministic computation over committed values. In comparison, 2rNISC is weaker (in particular, is implied by WE for NIZK of commitments) and has a simpler definition, thanks to which we manage to instantiate it from LWE and PRF in \(\mathrm {NC}^1 \). Next, we give an overview of our mrNISC from 2rNISC for functional OT.

Round Collapsing via 2rNISC for Functional OT. In mrNISC, each party \(P_i\) uses 2rNISC for functional OT to encode its private input \(x_i\) and a PRF key \(\mathrm {fk}_i\), \(((\hat{x}_i, \mathrm {fk}\rho _i), s_i) \leftarrow \mathsf {Com}(x_i, \rho _i)\). The PRF key will be used to expand pseudo-random coins for running the inner MPC protocol and generating garbled circuits described below.

A subset I of parties \({\{P_i\}}_{i \in I}\) wishes to compute \(f(z, {\{x_i\}}_{i \in I})\). Assume that each party \(P_1\) in the inner MPC broadcasts one message \(m_i^\ell \) in each round \(\ell \); but we now want to carry out this multi-round interaction non-interactively. To do so, each \(P_i\) sends one garbled circuit \(\hat{\mathsf {F}}_i^\ell \) per round \(\ell \in [L]\) of the inner MPC protocol corresponding to the next message function \(\mathsf {F}_i^\ell \) of \(P_i\). This garbled circuit takes as input all the messages \(\boldsymbol{m}^{<\ell } = {\{m^{l}_j\}}_{l < \ell , j\in [n]}\) sent in previous rounds, and outputs the next message \(m^\ell _i\) of \(P_i\) of the inner MPC (or the output for the last round \(\ell = L\)).

For an evaluator to compute the output from these garbled circuits \({\{\hat{\mathsf {F}}_i^\ell \}}_{\ell \in [L], i \in [n]}\), we need a mechanism to reveal the labels of \(P_i\)’s garbled circuits \(\hat{\mathsf {F}}_i^\ell \) that correspond to the correct messages of the inner MPC. More specifically, let \(k_0, k_1\) be two labels of \(P_i\)’s garbled circuit \(\hat{\mathsf {F}}^\ell _i\) for an input wire that takes in the t’th bit \(y = m^l_{j,t}\) of a message from \(P_j\). The goal is revealing only \(k_y\), which can be accomplished using exactly 2rNISC for functional OT.

First, we let \(k_0, k_1\) be expanded from \(P_i\)’s PRF key \(\rho _i\), that is \((k_0, k_1) = g_1(x_i,\mathrm {fk}_i)\) for some well-chosen \(g_1\). Second, \(y = m^1_{j}\) is \(P_j\)’s inner MPC message computed from its input \(x_j\) and randomness expanded from \(\rho _j\); hence, \(y = g_2(x_i,\rho )\) for some \(g_2\). Therefore, to reveal \(k_y\), we can modify garbled circuits of \(P_i\) and \(P_j\) to additionally output the right 2rNISC computation encodings:

• \(\hat{\mathsf {F}}^{\ell -1}_i\) for round \(\ell -1\) additionally outputs \(\alpha _i\leftarrow \mathsf {Encode}((g_1, g_2),\)\((\hat{x}_i, \hat{\mathrm {fk}}_i),(\hat{x}_j, \hat{\mathrm {fk}}_j),s_i)\).

• \(\hat{\mathsf {F}}^{l}_j\) for round l where \(P_j\) outputs \(m^l_j\) additionally outputs \(\alpha _j\leftarrow \mathsf {Encode}((g_1, g_2), (\hat{x}_i, \hat{\mathrm {fk}}_i),(\hat{x}_j, \hat{\mathrm {fk}}_j),s_j)\).

By the correctness and security of 2rNISC, the evaluator can recover only \(k_y\) as desired.

We do not know however how to prove the above construction secure. The issue is that the PRF key \(\mathrm {fk}_i\) is used to generate the labels of all the garbled circuits and our security hybrids switch garbled circuits to simulated ones, one by one. Concretely, to switch the garbled circuit for round \(\ell \) into a simulated one, its input labels must first be switched to uniformly random ones (instead of being PRF outputs). The usual solution for that is to use the pseudorandom property of the PRF. Unfortunately, we cannot do that, because the secret key \(\mathrm {fk}_i\) of the PRF is an input of the 2rNISC for functional OT for the rounds after round \(\ell \). To solve this issue, our final scheme actually uses \(L+1\) PRF keys, one for the randomness of the inner MPC and one for the labels of the garbled circuit for each of the L rounds. To make sure that the input encodings do not depend on the parameters of computations later, we employ a constant round inner MPC protocol, that is, \(L = O(1)\).