Information-Theoretic 2-Round MPC Without Round Collapsing: Adaptive Security, and More | Springer Nature Link

In this section, we build MPRE for degree-3 polynomials in two settings: (i) honest majority, and (ii) OLE correlations. Our road-map is as follows: In Sect. 4.1, we construct a 4-party gadget MPRE; in Sect. 4.2, we construct an MPRE for the 3-party functionality \(\mathsf {3MultPlus}_3\) described below, which computes a degree-3 monomial shifted by some linear terms, in the OLE-correlation model; then in Sect. 4.3, we consider the n-party version of the functionality \(\mathsf {3MultPlus}_n\) and construct an MPRE for it in the honest majority setting.

Finally, \(\mathsf {3MultPlus}\) is complete in the sense that MPRE for the \(\mathsf {3MultPlus}\) functionalities implies MPRE for general degree-3 functionalities. The proof can be found in the full version. All our MPRE have effective degree 2.

4.1 Our 4-Party Gadget MPRE with Leakage

Fix a field \(\mathbb {F}\). We begin with a MPRE with leakage for the following 4-party gadget function

For randomly sampled \(w_1,\ldots ,w_5\), [19, 20] show that \((\phi _1,\ldots ,\phi _6)\) is a randomized encoding of \(abx + \mu + \nu \), where \(\phi _1,\ldots ,\phi _6\) are defined as

[19, 20] guarantee that \(\phi _1,\ldots ,\phi _5\) are i.i.d. uniform despite the value of \((a, b, x, \mu , \nu )\). We would like to transfer this randomized encoding into an effective degree-2 MPRE with leakage.

Lemma 5

The scheme defined in Fig. 3 is an MPRE for the following 4-party gadget function

with the following properties:

1. (I)

   it has effective degree 2;

2. (II)

   tolerates any number of corruptions with leakage \(L_4((x,\mu ),a, b,\nu ) = (a,b)\).

Proof

The correctness is straight forward. The decoding function is the determinant of the matrix in (3), thus

For the adaptive privacy, we need to define the simulator.

• In the real world: For input \(x, a, b, \mu , \nu \)

  • At the outset: Sample random \(w_1,w_3,w_5,w_2',w_2'',w_4',w_4''\), compute \(w_2 = w_2'+w_2''\), \(w_4 = w_4'+w_4''\), compute \((\phi _1,\ldots ,\phi _6)\) according to Eq. (3).

  • \({\textsf {CorruptO}}\): Output \(\phi _1,\ldots ,\phi _6\).

  • \({\textsf {CorruptI}}(1)\): Output \(w_3,w_2',w_4'\).

  • \({\textsf {CorruptI}}(2)\): Output \(\bot \).

  • \({\textsf {CorruptI}}(3)\): Output \(\bot \).

  • \({\textsf {CorruptI}}(4)\): Output \(w_1,w_5,w_2'',w_4''\).

• In the ideal world:

  • At the Outset: Sample random \(\phi _1,\ldots ,\phi _5\),

  • Upon \({\textsf {CorruptO}}\), \({\textsf {SimO}}(y)\): Let \(\phi _6\) be the unique value that \(\det \left[ {\begin{matrix} \phi _1 &{} \phi _2 &{} \phi _6 \\ -1 &{} \phi _3 &{} \phi _4 \\ &{} -1 &{} \phi _5 \end{matrix}}\right] = y\). Output \(\phi _1,\ldots ,\phi _6\).

  • Upon \({\textsf {CorruptI}}(1)\), \({\textsf {SimI}}(1,(x,\mu ))\): Set \(w_3\) as the unique value that \(\phi _3 = x-w_3\).

    If \(P_4\) is not corrupted yet, sample \(w_2',w_4'\) at random.

    If \(P_4\) is already corrupted, subroutine \({\textsf {SimI}}(4,\nu ,(a,b))\) has learned a and has sampled the values of \(w_1, w_5\). Then, set \(w_2,w_4\) to satisfy \(\phi _2 = a w_3 + xw_1 - w_3w_1 -w_2\), \(\phi _4 = - w_4 + w_5 x\), and set \(w_2' = w_2 - w_2''\), \(w_4' = w_4 - w_4''\).

    Output \(w_3,w_2',w_4'\).

  • Upon \({\textsf {CorruptI}}(2)\), \({\textsf {SimI}}(2,a)\): Output \(\bot \).

  • Upon \({\textsf {CorruptI}}(3)\), \({\textsf {SimI}}(3,b)\): Output \(\bot \).

  • Upon \({\textsf {CorruptI}}(4)\), \({\textsf {SimI}}(4,\nu ,(a,b))\): Set \(w_1,w_5\) to satisfy \(\phi _1 = a -w_1\), \(\phi _5 = b - w_5\).

    If \(P_1\) is not corrupted yet, sample \(w_2'',w_4''\) at random.

    If \(P_1\) is already corrupted, subroutine \({\textsf {SimI}}(1,(x,\mu ))\) has learned x and has sampled the value of \(w_3\). Then, set \(w_2,w_4\) to satisfy \(\phi _2 = a w_3 + xw_1 - w_3w_1 -w_2\) and \(\phi _4 = - w_4 + w_5 x\), set \(w_2'' = w_2 - w_2'\), \(w_4'' = w_4 - w_4'\).

    Output \(w_1,w_5,w_2'',w_4''\).

To formally show that adversary cannot distinguish between the real world and the ideal world, we introduce a middle world.

• In the middle world:

  • At the Outset: Sample random \(\phi _1,\ldots ,\phi _5\).

    Let \(\phi _6\) be the unique value that \(\det \left[ {\begin{matrix} \phi _1 &{} \phi _2 &{} \phi _6 \\ -1 &{} \phi _3 &{} \phi _4 \\ &{} -1 &{} \phi _5 \end{matrix}}\right] = abx + \mu + \nu \).

    Solve \(w_1,\ldots ,w_5\) from Eq. (3). Sample \(w_2',w_2''\) as additive sharing of \(w_2\), Sample \(w_4',w_4''\) as additive sharing of \(w_4\).

  • \({\textsf {CorruptO}}\): Output \(\phi _1,\ldots ,\phi _6\).

  • \({\textsf {CorruptI}}(1)\): Output \(w_3,w_2',w_4'\).

  • \({\textsf {CorruptI}}(2)\): Output \(\bot \).

  • \({\textsf {CorruptI}}(3)\): Output \(\bot \).

  • \({\textsf {CorruptI}}(4)\): Output \(w_1,w_5,w_2'',w_4''\).

The real world is indistinguishable from the middle world, due to the security of the randomized encoding in (3).

Comparing the ideal world with the middle world, the only difference is that the computation is deferred in the ideal world: Same as the real world, the simulator in the ideal samples random \(\phi _1,\ldots ,\phi _5\). But the simulator cannot compute \(w_1, \dots , w_5\) at the beginning as it doesn’t know \(a,b,x,\mu ,\nu \) at that moment. Instead, the simulator compute each of \(w_1, \dots , w_5\) once it has the necessary information, using exactly the method as the middle world (i.e. by solving (3)). Thus the ideal world is also indistinguishable from the middle world.

4.2 MPRE for 3-Party \(\mathsf {3MultPlus}\) Using OLE Correlation

In this section, we construct an MPRE for the three party functionality

that has effective degree 2 and tolerates any number of corruptions in the OLE-correlation model.

For randomly sampled \(w_1,\ldots ,w_5\), [19, 20] show that \((\phi _1,\ldots ,\phi _6)\) is a randomized encoding of \(x_1x_2x_3 +\alpha + \beta + \gamma \), where \(\phi _1,\ldots ,\phi _6\) are defined as

[19, 20] guarantee that \(\phi _1,\ldots ,\phi _5\) are i.i.d. uniform despite the value of \((x_1,x_2,x_3, \alpha + \beta + \gamma )\). We would like to transfer this randomized encoding into an effective degree-2 MPRE using OLE correlated randomness.

Notice that \(w_1w_5x_2\) is the only degree-3 monomial in the randomized encoding, and \(w_1,w_5\) belong to the randomness of the randomized encoding. Thus if \(w_1,w_5\) are sampled from OLE correlated randomness, monomial \(w_1w_5x_2\) can be transferred into a degree-2 term. More precisely, let \((w_1,b^{(1)},w_5,b^{(3)})\in \mathbb {F}^4\) be sampled from OLE correlation, it holds that \(w_1w_5 = b^{(1)} + b^{(3)}\). The marginal distribution of \((w_1,w_5)\) is still uniform; and \(w_1w_5x_2\) equals \((b^{(1)} + b^{(3)}) x_2\), which is a degree-2 term. Then the randomized encoding has “effective” degree 2 as it can be computed from

Lemma 6

The MPRE in Fig. 4 for the 3-party functionality \(\mathsf {3MultPlus}_3\) has effective degree 2 and tolerates any number of corruptions, in the OLE-correlation model.

Proof

The correctness is straight forward,

For the adaptive privacy, we need to define the simulator.

• In the real world: For input \(x_1,x_2,x_3,\alpha , \beta ,\gamma \)

  • At the Outset: Sample random \(w_1,w_5, w_2^{(1)},w_2^{(2)},w_2^{(3)}, w_3^{(1)},w_3^{(2)},w_3^{(3)},w_4^{(1)},w_4^{(2)},w_4^{(3)} \in \mathbb {F}\), sample random \(b^{(1)},b^{(3)}\) that \(b^{(1)}+b^{(3)} = w_1w_5\), compute \(w_2 = \sum _{i\in [3]}w_2^{(i)}\), \(w_3 = \sum _{i\in [3]}w_3^{(i)}\), \(w_4 = \sum _{i\in [3]}w_4^{(i)}\), compute \((\phi _1,\ldots ,\phi _6)\) according to Eq. (5).

  • \({\textsf {CorruptO}}\): Output \(\phi _1,\ldots ,\phi _6\).

  • \({\textsf {CorruptI}}(1)\): Output \(w_1,b^{(1)},w_2^{(1)},w_3^{(1)},w_4^{(1)}\).

  • \({\textsf {CorruptI}}(2)\): Output \(w_2^{(2)},w_3^{(2)},w_4^{(2)}\).

  • \({\textsf {CorruptI}}(3)\): Output \(w_5,b^{(3)},w_2^{(3)},w_3^{(3)},w_4^{(3)}\).

• In the ideal world:

  • At the Outset: Sample random \(\phi _1,\ldots ,\phi _5\),

  • Upon \({\textsf {CorruptO}}\), \({\textsf {SimO}}(y)\): Let \(\phi _6\) be the unique value that \(\det \left[ {\begin{matrix} \phi _1 &{} \phi _2 &{} \phi _6 \\ -1 &{} \phi _3 &{} \phi _4 \\ &{} -1 &{} \phi _5 \end{matrix}}\right] = y\). Output \(\phi _1,\ldots ,\phi _6\).

  • Upon \({\textsf {CorruptI}}(1)\), \({\textsf {SimI}}(1,(x_1,\alpha ))\): Set \(w_1\) to satisfy \(\phi _1 = x_1 -w_1\).

    If \(P_3\) is not corrupted yet, sample \(b^{(1)}\) at random.

    If \(P_3\) is already corrupted, subroutine \({\textsf {SimI}}(3,(x_3,\gamma ))\) has set the values of \(w_5,b^{(3)}\). Set \(b^{(1)} = w_1w_5 - b^{(3)}\).

    If both \(P_2\) and \(P_3\) are corrupted, subroutines \({\textsf {SimI}}(2,(x_2,\beta ))\), \({\textsf {SimI}}(3,(x_3,\gamma ))\) have set \(w_j^{(2)},w_j^{(3)}\) for \(j\in \{2,3,4\}\). Then solve \(w_2,w_3,w_4\) from Eq. (4) and set \(w_j^{(1)} = w_j - w_j^{(2)} - w_j^{(3)}\) for \(j\in \{2,3,4\}\).

    If at least one of \(P_2,P_3\) is not corrupted yet, sample \(w_2^{(1)},w_3^{(1)},w_4^{(1)} \in \mathbb {F}\).

    Output \(w_1,b^{(1)},w_2^{(1)},w_3^{(1)},w_4^{(1)}\).

  • Upon \({\textsf {CorruptI}}(2)\), \({\textsf {SimI}}(2,(x_2,\beta ))\): If both \(P_1\) and \(P_3\) are corrupted, subroutines \({\textsf {SimI}}(1,(x_1,\beta ))\), \({\textsf {SimI}}(3,(x_3,\gamma ))\) have set \(w_j^{(1)},w_j^{(3)}\) for \(j\in \{2,3,4\}\). Then solve \(w_2,w_3,w_4\) from Eq. (4) and set \(w_j^{(2)} = w_j - w_j^{(1)} - w_j^{(3)}\) for \(j\in \{2,3,4\}\).

    If at least one of \(P_1,P_3\) is not corrupted yet, sample \(w_2^{(2)},w_3^{(2)},w_4^{(2)} \in \mathbb {F}\).

    Output \(w_2^{(2)},w_3^{(2)},w_4^{(2)}\).

  • Upon \({\textsf {CorruptI}}(3)\), \({\textsf {SimI}}(3,(x_3,\gamma ))\): Set \(w_5\) to satisfy \(\phi _5 = x_3 - w_5\).

    If \(P_1\) is not corrupted yet, sample \(b^{(3)}\) at random.

    If \(P_1\) is already corrupted, subroutine \({\textsf {SimI}}(1,(x_1,\alpha ))\) has set the values of \(w_1,b^{(1)}\). Set \(b^{(3)} = w_1w_5 - b^{(1)}\).

    If both \(P_1\) and \(P_2\) are corrupted, subroutines \({\textsf {SimI}}(1,(x_1,\beta ))\), \({\textsf {SimI}}(2,(x_2,\gamma ))\) have set \(w_j^{(1)},w_j^{(2)}\) for \(j\in \{2,3,4\}\). Then solve \(w_2,w_3,w_4\) from Eq. (4) and set \(w_j^{(3)} = w_j - w_j^{(1)} - w_j^{(2)}\) for \(j\in \{2,3,4\}\).

    If at least one of \(P_1,P_2\) is not corrupted yet, sample \(w_2^{(3)},w_3^{(3)},w_4^{(3)} \in \mathbb {F}\).

    Output \(w_5,b^{(3)},w_2^{(3)},w_3^{(3)},w_4^{(3)}\).

To show the indistinguishability between the real world and the ideal world, we introduce a middle world.

• In the middle world: For input \(x_1,x_2,x_3, \alpha , \beta ,\gamma \)

  • At the Outset: Sample random \(\phi _1,\ldots ,\phi _5\).

    Let \(\phi _6\) be the unique value that \(\det \left[ {\begin{matrix} \phi _1 &{} \phi _2 &{} \phi _6 \\ -1 &{} \phi _3 &{} \phi _4 \\ &{} -1 &{} \phi _5 \end{matrix}}\right] = y\). Solve \(w_1,\ldots ,w_5\) from Eq. (4).

    Sample random \(b^{(1)},b^{(3)}\) that \(b^{(1)}+b^{(3)} = w_1w_5\). For each of \(j\in \{2,3,4\}\), sample random \(w_j^{(1)},w_j^{(2)},w_j^{(3)}\) that \(w_j^{(1)} + w_j^{(2)} + w_j^{(3)} = w_j\).

  • \({\textsf {CorruptO}}\): Output \(\phi _1,\ldots ,\phi _6\).

  • \({\textsf {CorruptI}}(1)\): Output \(w_1,b^{(1)},w_2^{(1)},w_3^{(1)},w_4^{(1)}\).

  • \({\textsf {CorruptI}}(2)\): Output \(w_2^{(2)},w_3^{(2)},w_4^{(2)}\).

  • \({\textsf {CorruptI}}(3)\): Output \(w_5,b^{(3)},w_2^{(3)},w_3^{(3)},w_4^{(3)}\).

The real world is indistinguishable from the middle world, due to the security of the randomized encoding in (3).

Comparing the ideal world with the middle world, the only difference is that the computation is deferred in the ideal world: Same as the real world, the simulator in the ideal samples random \(\phi _1,\ldots ,\phi _5\). But the simulator cannot compute \(w_1, \dots , w_5\) by solving (4) at the beginning as it doesn’t know \(x_1,x_2,x_3,\alpha , \beta ,\gamma \) at that moment. Instead, the simulator compute \(w_1\) once it knows \(x_1\); compute \(w_5\) once it knows \(x_3\); and compute \(w_2,w_3,w_4\) once it knows all the inputs. Thus the ideal world is also indistinguishable from the middle world.

4.3 MPRE for n-Party \(\mathsf {3MultPlus}\) with Honest Majority

We construct an MPRE (Fig. 5) for the n-party functionality

that has effective degree 2 and tolerates minority corruptions. The construction requires \(|\mathbb {F}| > n\).

Additional Notation. Let \(\mathbb {F}\) be a field that \(|\mathbb {F}|>n\), let \(1,\ldots ,n\) denote n distinct non-zero elements in \(\mathbb {F}\). Denote by \(\mathsf {\mathcal {P}}(t, m)\) the set of degree-t polynomials P with constant term m over \(\mathbb {F}\), so that \(Q \leftarrow \mathsf {\mathcal {P}}(t,m)\) refers to sampling a random degree-t polynomial Q whose constant term is m. In addition, \(m ={\text {rec}}(t, (i_1, \sigma _1) \dots , (i_{t+1},\sigma _{t+1}))\) denotes the procedure for reconstructing the constant term from \(t+1\) points on the polynomial via interpolation. For convenience, we also denote by \(\mathsf {\mathcal {P}}(t, m)\mid (i_1, \sigma _1) \dots , (i_{s},\sigma _{s})\) the set of polynomials \(Q \in \mathsf {\mathcal {P}}(t,m)\) such that \(Q(i_1) = \sigma _1,\ldots ,Q(i_s) = \sigma _{s}\), for \(s \le t+1\).

Protocol Overview. We decompose the computation of \(x_1x_2x_3 + \alpha + \beta + \gamma \), into two parts \(x_1 x_2 x_3 + z + s\) and \(\alpha + \beta + \gamma - z - s\) where z is sampled by \(P_1\) and s is jointly sampled by all n parties. Since the second term is linear, we focus on designing an MPRE for the first part.

• \(P_1\) samples \(z \leftarrow \mathbb {F}, Z \leftarrow \mathsf {\mathcal {P}}(n-1,z)\).

• \(P_2\) samples \(Q_2 \leftarrow \mathsf {\mathcal {P}}(t, x_2)\) and \(P_3\) samples \(Q_3 \leftarrow \mathsf {\mathcal {P}}(t, x_3)\).

• \(P_i\) samples \(S(i) \leftarrow \mathbb {F}\), for every \(i \in [n]\).

  Let \(s = {\text {rec}}(n-1,(1,S(1)),\ldots ,(n,S(n))\).

Observe that

Here, we rely on the fact that \(2t \le n-1\). Then, for each \(i=1,2,\ldots ,n\), parties \(P_1,P_2,P_3,P_i\) can run the gadget MPRE described in Sect. 4.1 to compute Y(i)

from which the output party can reconstruct Y and the constant term \(x_1x_2x_3 + z + s\).

Security Intuition. We can prove security of this protocol for up to \(t < n/2\) corruptions. Consider two cases: If \(P_1\) is not corrupted, or corrupted. In the first case, the view of the output party consists of \(\alpha +\beta +\gamma -z - s\), and a degree \(n-1\) polynomial Y with constant term \(x_1x_2x_3+z + s\), which is random thanks to the randomization via Z. Now, suppose the adversary additional corrupts t parties, excluding \(P_1\); call this set of parties T. Then, security of the gadget MPRE tells us that the adversary also learns \(\{ Q_2(i),Q_3(i),S(i) : i \in T \}\). Suppose for now \(2,3 \notin T\). By the property of Shamir’s secret sharing, this leaks no additional information about \(x_1,x_2,x_3\) to the adversary. Now, if \(2 \in T\), then the adversary also learns \(Q_2\), but that is okay since it already learns \(x_2\); the same argument applies to \(3 \in T\).

In the second case that \(P_1\) is corrupted and adversary learns \(x_1\) and all Z(i)’s, the polynomial Y is still a random degree-\((n-1)\) polynomial with constant term \(x_1x_2x_3+z + s\) thanks to the randomization via S. If the adversary corrupts at set T of t parties, including \(P_1\), and learns \(\{ Q_2(i),Q_3(i),S(i) : i \in T \}\), Shamir’s secret sharing, again protects \(x_2,x_3\) from being leaked to the adversary.

Protocol Specification. In short, the MPRE \(\hat{F}\) for \(x_1x_2x_3 + \alpha + \beta + \gamma \) simply computes n 4-party gadget MPRE,

together with the linear term \(\alpha +\beta +\gamma + z + s\). A formal description is in Fig. 5. It is easy to see that \(\hat{F}\) has effective degree 2 since \(\hat{f}\) has effective degree \(\le 2\).

Lemma 7

The MPRE scheme in Fig. 5 for the n-party functionality \(\mathsf {3MultPlus}_n\) has effective degree 2 and satisfies t-adaptive privacy for \(t < n/2\). The construction requires \(|\mathbb {F}| > n\).

Simulator. Observe that the MPRE \(\hat{F}\) invokes the 4-party gadget MPRE \(\hat{f}\) for n times and computes a linear function \(\ell \). By the adaptive security of \(\hat{f}\) and Theorem 2, we have that the parallel composition of all n invokations of \(\hat{f}\) and the linear function \(\ell \) is an MPRE \(\hat{G}\) for the following composed functionality G:

The leakage function of \(\hat{f}\) gives the leakage function of \(\hat{G}\), which is \(L_i\) leaking \((Q_2(i), Q_3(i))\) to \(P_i\) for every i. \(\hat{G}\) is secure against \(t < n/2\) adaptive corruption. Let \(({\textsf {SimI}}_G, {\textsf {SimO}}_G)\) be its simulator. Below, we use this simulator to construct the simulator \(({\textsf {SimI}}_F, {\textsf {SimO}}_F)\) for \(\hat{F}\).

Overview. The encoding of \(\hat{F}\) consists of encoding of \(\hat{f}\) and the output of \(\ell \) with appropriate input / output. The job of \(({\textsf {SimI}}_F, {\textsf {SimO}}_F)\) is: 1) simulate the input / output of calls to \(\hat{G}\), i.e., calls to \(\hat{f}\) and \(\hat{\ell }\), and 2) invoke \(({\textsf {SimI}}_G, {\textsf {SimO}}_G)\) to simulate the encoding and local randomness of all calls to \(\hat{f}\) and \(\ell \). Task 1) requires simulating Y(i), a random n-out-of-n Shamir sharing of \(x_1x_2x_3 + z + s\) belonging to the output of encoding, all Z(i) belonging to \(P_1\), each S(i) belonging to \(P_i\), and each \(Q_2(i), Q_3(i)\) belonging to \(P_2, P_3\) respectively, and leaked to \(P_i\). Consistency between Y(i) and Z(i), S(i) is maintained by “programming” the variable that is simulated the last. This can be done as S(i) Z(i) are all marginally random and provide enough degree of freedom for programming even if all parties were corrupted. Consistency between simulating \(Q_2(i), Q_3(i)\) when \(P_2, P_3\) are corrupted and when \(P_i\) is corrupted can be maintained, thanks to the fact that at most t parties are corrupted and \(Q_2,Q_3\) have degree t with constant term \(x_2, x_3\).

Proof

(Proof of Lemma 7). We start with the formal description of the simulator.

• Upon \({\textsf {CorruptO}}\), \({\textsf {SimO}}(y = x_1x_2x_3+\alpha +\beta +\gamma )\):

  • Sample \(\tau \leftarrow \mathbb {F}\).

  • \(\forall i\), if \(P_1, P_i\) are already corrupted, \( Y(i) = x_1 Q_2(i) Q_3(i) + Z(i) + S(i)\) is fixed.

  • Sample \( O\leftarrow \mathsf {\mathcal {P}}(n-1,\tau ) \mid (i_1, Y(i_1)),\dots , (i_s, Y(i_s))\) conditioned on the list of fixed \((i_j, Y(i_j))\)’s from previous step. (Note that \(s \le t\) points are fixed.)

  Send to adversary \({\textsf {SimO}}_G(y-\tau , ( Y(i))_i)\).

• Upon \({\textsf {CorruptI}}(1)\), \({\textsf {SimI}}(x_1, \alpha )\):

  • Sample \( S(1)\leftarrow \mathbb {F}\).

  • \(\forall i\), if \(P_i\) and the output party are already corrupted, find the unique Z(i) that satisfies the equation \( Y(i) = x_1 Q_2(i) Q_3(i) + Z(i) + S(i)\).

  Send to adversary \({\textsf {SimI}}_G(x_1, \alpha , ( Z(i))_i, S(1))\).

• Upon \({\textsf {CorruptI}}(2)\), \({\textsf {SimI}}(x_2, \beta ))\):

  • \(\forall i\), if \(P_i\) is already corrupted, \( Q_2(i)\) is already fixed.

  • Sample \(Q_2 \leftarrow \mathsf {\mathcal {P}}(t,x_2)\mid (i_1,Q_2(i_1)),\dots , (i_s,Q_2(i_s))\), conditioned on the list of fixed \((i_j, Q_2(i_j))\). (Note that this can be done as \(s \le t\) points are fixed, and \(Q_3\) has degree t.)

  • if \(P_1\) and the output party are already corrupted, find the unique S(2) that satisfies the equation \( Y(2) = x_1 Q_2(2) Q_3(2) + Z(2) + S(2)\).

  Send to adversary \({\textsf {SimI}}_G(x_2, \beta , ( Q_2(i))_i, S(2))\).

• Upon \({\textsf {CorruptI}}(3)\), \({\textsf {SimI}}(x_3, \gamma ))\): Same as in \({\textsf {SimI}}(x_2, \beta )\):

  • \(\forall i\), if \(P_i\) is already corrupted, \( Q_3(i)\) is already fixed.

  • Sample \(Q_3 \leftarrow \mathsf {\mathcal {P}}(t,x_3)\mid (i_1,Q_3(i_1)),\dots , (i_s,Q_3(i_s))\), conditioned on the list of fixed \((i_j, Q_3(i_j))\).

  • if \(P_1\) and the output party are already corrupted, find the unique S(3) that satisfies the equation \( Y(3) = x_1 Q_2(3) Q_3(3) + Z(3) + S(3)\).

  Send to adversary \({\textsf {SimI}}_G(x_3, \gamma , ( Q_3(i))_i, S(3))\).

• Upon \({\textsf {CorruptI}}(i)\), \({\textsf {SimI}}(\bot ))\) for \(i\notin \{1,2,3\}\):

  • If \(P_2\) and/or \(P_3\) is already corrupted, \( Q_2\) and/or \( Q_3\) are fixed. Otherwise, sample \( Q_2(i), Q_3(i) \leftarrow \mathbb {F}\).

  • Sample \(Q_3 \leftarrow \mathsf {\mathcal {P}}(t,x_3)\mid (i_1,Q_3(i_1)),\dots , (i_s,Q_3(i_s))\), conditioned on the list of fixed \((i_j, Q_3(i_j))\).

  • if \(P_1\) and the output party are already corrupted, find the unique S(i) that satisfies the equation \( Y(i) = x_1 Q_2(i) Q_3(i) + Z(i) + S(i)\).

  Send to adversary \({\textsf {SimI}}_G( S(i), Q_2(i), Q_3(i))\).

Correctness of Simulation. We argue that the view of the adversary in the real world and simulation are identically distributed following from the simulation security of \(\hat{G}\) and the fact that the input/output of the invokation of \(\hat{G}\) are simulated perfectly.

Hybrid. More formally, consider the following hybrid, where input/output of the invokation of \(\hat{G}\) is generated at the beginning as in the real world, while the encoding of \(\hat{G}\) is still simulated.

• At the Outset: With knowledge of \(x_1, x_3, x_3, \alpha , \beta , \gamma \).

  • \(\forall i\), sample \(Z(i) \leftarrow \mathbb {F}\). Let \(z = Z(0)\).

  • Sample \(Q_2 \leftarrow \mathsf {\mathcal {P}}(t, x_2)\).

  • Sample \(Q_3 \leftarrow \mathsf {\mathcal {P}}(t, x_3)\).

  • \(\forall i\), sample \(S(i) \leftarrow \mathbb {F}\). Let \(s = S(0)\).

  • \(\forall i\), compute \(Y(i) = x_1Q_2(i)Q_3(i) + Z(i) + S(i)\).

  • Compute \(\tau = x_1x_2x_3 + z + s\), and \(y= x_1x_2x_3 +\alpha +\beta +\gamma \).

• Upon \({\textsf {CorruptO}}\): Send to adversary \({\textsf {SimO}}_G(y-\tau , ( Y(i))_i)\).

• Upon \({\textsf {CorruptI}}(1)\): Send to adversary \({\textsf {SimI}}_G(x_1, \alpha , ( Z(i))_i, S(1))\).

• Upon \({\textsf {CorruptI}}(2)\) Send to adversary \({\textsf {SimI}}_G(x_2, \beta , ( Q_2(i))_i, S(2))\).

• Upon \({\textsf {CorruptI}}(3)\): Send to adversary \({\textsf {SimI}}_G(x_3, \gamma , ( Q_3(i))_i, S(3))\).

• Upon \({\textsf {CorruptI}}(i)\): Send to adversary \({\textsf {SimI}}_G( S(i), Q_2(i), Q_3(i))\).

The only difference between the above hybrid and the real world is whether the encoding of \(\hat{G}\) is simulated or not, it follows from the security of \(\hat{G}\) that the views of the adversary are identically distributed. The only difference between the hybrid and the simulation is whether the input/output of the call to \(\hat{G}\) is generated at the beginning with knowledge of \(x_1, x_2, x_3, \alpha , \beta , \gamma \) or generated in a delayed fashion. Since these two ways of generation yield the same distribution, the hybrid and simulation are also identically distributed. We conclude that the real world and simulation are identically distributed.