12 Ingredients for adaptive corruptions
Status. Everything in this chapter is formalized, and no originality is claimed. Section 2.5 describes what a simulator must explain when the prover is corrupted during or after the protocol of [ JKO13 ] . This chapter formalizes some protocol-specific facts behind that description. The equivocation condition of Definition 12.1 is the condition on the receiver’s message and randomness in [ GKPS18 , Sect. 3, Definition 3.1 ] , in a perfect version; the rest of that definition (a two-round OT that securely realizes the OT functionality in the common reference string model, and a simulator that uses only the trapdoor of the setup) is not formalized, and neither is DDH. The equivocation of the PVW receiver in decryption mode is the equivocation step of the proof of [ GKPS18 , Theorem 3.2 ] , and the explanation of the prover follows [ GKPS18 , Sect. 3.2 ] . The other statements we have not found published as such: that the explained PVW secret decrypts, and that messy mode does not satisfy the condition, follow from the form of the keys; the Chou–Orlandi equivocation given the sender’s secret follows from the form of the messages; the equivocation of the hash commitment applies the programming of the random oracle recalled in [ GKPS18 , Sect. 1.2 ] to the games of Chapter 7; and soundness in decryption mode combines Theorem 9.9 with the indistinguishability of the modes [ PVW08 , Theorem 5.2 ] . Adaptive security itself, which needs a model of execution with corruptions such as the one of universal composability [ Can20 , Sect. 7.1 ] , is not defined here: the theorems below are some ingredients of a simulation, not the simulation. Among the missing ingredients are the consistency of the Chou–Orlandi outputs with an explained message, the composition of the explanations of the OT and of the commitment, zero knowledge with the PVW OT in decryption mode, and extraction against a corrupted prover.
12.1 The equivocation condition for the receiver
Let the receiver of an OT send \(\mathit{msg}(\sigma , r)\) for the choice bit \(\sigma \) and the randomness \(r\). It satisfies the equivocation condition, with simulated message \(\mathit{sim}\) and explanations \(e_0, e_1\), if each \(e_\sigma \) is a bijection of the randomness and
A simulator sends \(\mathit{sim}(r)\) for a uniform \(r\), without the choice bit; told \(\sigma \) later, it explains its message by the randomness \(e_\sigma (r)\), which is uniform because \(e_\sigma \) is a bijection. This is the condition on messages and randomness of [ GKPS18 , Sect. 3, Definition 3.1 ] , where the explained randomness is only required to be statistically close to the honest one; here it has exactly the same distribution. That definition also asks for a two-round OT that securely realizes the OT functionality in the common reference string model, with explanations computed by a simulator from the trapdoor of the setup; these requirements are not part of Definition 12.1, and who can compute the explanations is said for each instance below.
On a decryption-mode common string, with \(g_1 = y \cdot g_0\), \(y \neq 0\) and \(h_b = x \cdot g_b\), the PVW receiver satisfies the equivocation condition with simulated message \(\mathit{keyGen}(0, r)\), \(e_0(r) = r\) and \(e_1(r) = y^{-1} r\); the explanation uses the trapdoor \(y\) of the decryption setup. Moreover, for any explanations satisfying the condition, the explained secret \(e_\sigma (r)\) decrypts what the sender encrypts on branch \(\sigma \) under the simulated key.
By Definition 9.6, \(\mathit{keyGen}(1, r) = \mathit{keyGen}(0, y r)\), so \(\mathit{keyGen}(1, y^{-1} r) = \mathit{keyGen}(0, r)\); multiplication by \(y^{-1}\) is a bijection of \(\mathbb {Z}_q\). This is the equivocation step of the proof of [ GKPS18 , Theorem 3.2 ] and the algorithm \(\mathrm{TrapKeyGen}\) of [ PVW08 , Sect. 5.3 ] . The simulated key is the key of the choice \(\sigma \) with secret \(e_\sigma (r)\), so the second claim is the correctness of decryption (Lemma 9.2).
On a messy common string the PVW receiver does not satisfy the equivocation condition, for any simulated message and explanations.
If \(\mathit{keyGen}(0, r_0) = \mathit{keyGen}(1, r_1)\), then \(r_0 g_0 = r_1 g_1\) and \(r_0 x_0 g_0 = r_1 x_1 g_1\), so \((x_0 - x_1) r_0 g_0 = 0\) and \(r_0 = 0\), since \(x_0 \neq x_1\) and \(g_0 \neq 0\). Hence \(e_0\) is identically \(0\), and it is not a bijection.
In our reading, this is why the instantiation of [ GKPS18 , Sect. 3.3 ] uses decryption mode: in messy mode the key determines the branch, which is what makes extraction possible (Lemma 9.4).
Let \(A = a \cdot g\). The receiver message \(B = b \cdot g + wA\) satisfies the equivocation condition with simulated message \(b \cdot g\) and explanations \(e_0(b) = b\), \(e_1(b) = b - a\).
\((b - a) \cdot g + a \cdot g = b \cdot g\), and \(b \mapsto b - a\) is a bijection.
The explanation needs the sender’s secret \(a\), which is not a trapdoor of a common string, so this does not make the Chou–Orlandi OT receiver equivocal in the sense of [ GKPS18 , Definition 3.1 ] . The simulator knows \(a\) when it plays the honest verifier, and otherwise learns it only at the open-all step (Section 2.5).
12.2 Explaining the prover
Let the OT receiver satisfy the equivocation condition, and let the verifier choose its message (the garbled circuit, the OT inputs and the seed it opens) as a function of the prover’s OT messages. Let \(C(w) = 1\), and let \(r_j\) be the simulator’s randomness for the \(j\)-th OT. With the explained randomness \(e_{w_j}(r_j)\) the prover’s OT messages are the simulated ones \(\mathit{sim}(r_j)\), and the verifier’s view of the prover is the output of the simulator of Theorem 4.5. The explained randomness is uniform when \(r\) is. Here only the receiver’s first message is a real OT message: the delivery of the labels is the ideal one of Chapter 4.
The first claim is the definition, coordinate by coordinate. Then the verifier’s messages are the same in both cases, and Theorem 4.5 gives the second claim. The explanation is a bijection in each coordinate.
According to [ GKPS18 , Sect. 3.2 ] , with an ideal commitment and an OT that is receiver equivocal in their sense, the prover’s view of the OT is all a simulator must explain when the prover is corrupted after the execution, since every step of the prover after the oblivious transfers is independent of the witness. Theorem 12.5 proves the part of this that concerns the receiver’s messages and the verifier’s view, with ideal delivery of the labels; for the PVW OT, Theorem 12.2 adds that the explained secret decrypts the label of the actual choice.
12.3 Equivocating the hash commitment
With the hash commitment of Chapter 7, a prover corrupted after committing and before opening hands over its output label \(Z_w\) and its commitment randomness \(r\). In the real execution its commitment is \(G(Z_w, r)\). The simulator commits instead to a uniform \(c\), without the witness, and at the corruption reveals \((Z_w, r)\) and sets \(G(Z_w, r) := c\); this is possible in the programmable random oracle model [ GKPS18 , Sect. 1.2 ] . We reuse the games of Definition 7.3, with the prover’s check of the opened seed removed (it always passes), so that the last message of the real game is always \((Z_w, r)\). The corruption thus takes place after the verifier has sent its seed, and the state revealed is only \((Z_w, r)\); the prover’s OT messages are handled by Theorem 12.5, and the two explanations are not composed here.
Let a malicious verifier make \(q_1\), \(q_2\) and \(q_3\) oracle queries before the commitment, between the commitment and the corruption, and after the corruption. Over \(G\), \(c\) and \(r\) uniform, the probabilities that it outputs \(1\) in the real execution and against the simulator differ by at most \((q_1 + q_2)/|R|\).
Off the bad event \(\mathrm{Bad}_{23}\) of Lemma 7.6, the hybrid of Lemma 7.5, which programs the oracle already before the second phase, and the simulator differ only in the answers of the second phase, and these do not hit the programmed point (Lemma 7.2). Since the check always passes, the last message is never an abort, and the bad event reduces to a query of the second phase at the commitment point; the queries of the third phase are answered by the programmed oracle in both games and cost nothing. The rest is the counting of Theorem 7.7, applied to the verifier without its third phase.
12.4 Soundness in decryption mode
The PVW receiver satisfies the equivocation condition in decryption mode, while the soundness of Theorem 9.9 uses messy mode, where the sender is statistically protected. Switching the modes costs the DDH advantage of the acceptance probability.
Let \(C\) be unsatisfiable, \(q {\gt} 2\), and let the cheating prover depend on the common string and make at most \(N_1\) and \(N_2\) queries in its two phases. Averaged over the decryption-mode setup, the verifier accepts with probability at most
where \(p_{\mathrm{acc}}\) is the acceptance probability as a function of the common string. The bound holds on average over the setup, not for each string; as in Theorem 9.20, the efficiency of the distinguisher \(p_{\mathrm{acc}}\) is outside the formalization.