- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
For fixed \(G\), summed over \(\Delta \neq 0\), the real randomness for which the first query of step 2 to \(G\) answered with the commitment is at the target, outside \(\mathrm{Zero} \cup \mathrm{Both}\), is at most the sum over \(\gamma \) of the randomness \(\rho \) for which \(\mathcal{A}_\gamma \) wins. By Theorem 10.17, with \(\Delta \) and \(\omega \) uniform, its probability is at most \((Q + 1)/(|V| - 1) + Q/|V|\).
With \(\omega \) uniform,
where \(a_j\) is uniform in \(\mathbb {Z}_q\) and \(\sigma \) uniform, independent: the right side is the sum of the square Diffie–Hellman advantages of the solvers.
For every seed there are pads \(K_i \in V\), one per position, such that the ideal garbler with the constant pads \(K_i\) produces the real material.
Step \(k\) of the real game is bad if its action is a query \((i, y)\) at a multiplexer \(i\) with selector \(s\), and either \(s\) is known at step \(k\) and \(y = X^{(k)}_s + \Delta \), or \(s\) is unknown at step \(k\) and \(y \in \{ Z_s, Z_s + \Delta \} = \{ X^{(k)}_s, X^{(k)}_s + \Delta \} \).
The garbler samples \(\Delta \in V \setminus \{ 0\} \), the zero-labels of the inputs and of the constants, and a random oracle \(H\), and sends the material \(\mathsf{M}\). The adversary then interleaves, in any order chosen adaptively:
queries \((i, y)\) to \(H\);
label requests: for an input \(j\) not yet requested and a bit \(b\) of its choice, it receives the label \(L_j + b\Delta \).
It takes \(q\) actions in all, queries and requests together. In the formalization a repeated request of an input is answered with the label given the first time, whatever the bit. At the end the requested bits form \(x\) (unrequested bits are \(0\)) and the adversary outputs a label \(Z\). It wins if \(Z = X_{\mathrm{out}} + \Delta \), where \(X_{\mathrm{out}}\) is the active output label for \(x\).
The adversary is deterministic (a randomized one is a family indexed by its coins) and takes \(q\) actions, each a query \((i, y)\) to \(H\) or a request \((j, b)\) for an input \(j {\lt} m\). Only the first request of an input counts: later requests of the same input are answered with the label of the first bit. The real randomness is \((L, L_c, H, J)\): the zero-labels of the inputs and of the constants, the hash and a junk component, which the real game does not use. A query \((i, y)\) is bad for the final input if \(y = S_i + \Delta \), where \(S_i\) is the active label, for the final \(x\), of the selector of the multiplexer at position \(i\). The simulated game is the one of Definition 10.3, with randomness \((R, A, H', T)\): requested labels, active constant labels, hash and ciphertexts.
The simulator sends uniform ciphertexts \(T_i\) and uniform active constant labels, answers every label request with a fresh uniform label \(R_j\) whatever the bit, and answers queries with a random function \(H'\). It never uses \(\Delta \); we sample \(\Delta \) at the end. All active labels are defined by evaluation: for an input \(x\), the active label of an input \(j\) is \(R_j\), and the evaluator reads \(H'\) at the active selector labels.
A query strategy chooses each query from the previous answers. A run queries a point \(p\) if one of its queries is \(p\).
A cheating prover chooses its OT bits \(x\) and computes the label it commits to from the material and the labels it received. Ideal commitment makes this label independent of the later opening. In the authenticity game an adversary receives the material and the active labels of an input \(x\) of its choice, and wins if it outputs the inactive output label \(\operatorname {lab}_\Delta (L_{\mathrm{out}}, 1 - v)\), where \(v\) is the plaintext output on \(x\).
A cheating prover sees a view of the garbling, makes \(q_1\) queries to \(G\) and commits to \(c\); after the opening it makes \(q_2\) queries and opens a point. The verifier accepts if the opened point has the target label and its value is \(c\). The extractor returns the label of the first first-phase query answered with \(c\). It does not see the opening, so it is an adversary for the authenticity game.
A node is one of \(\mathsf{input}(j)\), \(\mathsf{const}(b)\), \(\mathsf{xor}(a, b)\) and \(\mathsf{mux}(s, z, o)\), where \(j, a, b, s, z, o \in \mathbb {N}\) and \(b \in \{ 0, 1\} \). A circuit is a list of nodes. The operands are positions of earlier nodes; a position that does not refer to an earlier node reads the default wire (value \(0\), label \(0\)).
The coins are \(\gamma = (a, H_K', e')\) with \(a \in \mathbb {Z}_q^k\), \(H_K' : [k] \times \mathbb {G} \to V\) and \(e' \in (V \times V)^k\). The adversary \(\mathcal{A}_\gamma \) of the adaptive game runs the prover as follows.
It sends \(A_j = a_j g\), answers the queries of step 1 with \(H_K'\), and obtains \(B\); it computes the key points and the early ones (it knows \(a\)).
For each \(j\) and \(c \in \{ 0, 1\} \): if \(K^c_j\) is early, it requests the bit \(c\) of input \(j\), receives \(X\), and puts \(e_{j,c} = X + H_K'(j, K^c_j)\); otherwise \(e_{j,c} = e'_{j,c}\). It gives the prover the material of the game and \(e\).
At each step of step 2 it forwards the query to \(H\) to the game, answers the query to \(G\) with \(G\), and answers the query \((j, P)\) to \(H_K\) as follows. If \(P = K^c_j\), \(K^c_j\) is not early, and this is the first query at \(K^c_j\), it requests the bit \(c\) of input \(j\), receives \(X\), and answers \(e_{j,c} + X\); a later query at the same point gets the same answer. Every other query gets \(H_K'(j, P)\).
Its guess is the first component of the first query of step 2 to \(G\) whose answer is the commitment, and \(0\) if there is none.
It makes \(n_1\) queries to \(H\) and at most \(2k\) requests. In the formalization each input gets two actions before the masked pairs and each step two actions after them (a request or a query to \(H\) outside the circuit, which answers \(0\) and is never bad), so it takes exactly \(Q = 2(k + n_1)\) actions; a request is made at every query at a key point that is not early, not only the first, and the game answers repeated requests consistently.
The group \(\mathbb {G}\) has prime order \(q\) and \(g\) is a generator. The verifier samples, for each input \(j {\lt} k\), a secret \(a_j \in \mathbb {Z}_q\) and sends \(A_j = a_j g\); the seed \((\Delta , L, L_c)\), with \(\Delta \) uniform in \(V \setminus \{ 0\} \); and three independent random oracles: the hash \(H\) of the garbling, the key hash \(H_K(j, \cdot ) : \mathbb {G} \to V\) of the OT (separated from \(H\) by its domain), and the commitment oracle \(G\). The cheating prover
sees \(A\), makes \(n_0\) queries to \(H_K\), and sends \(B_j\) for every \(j\);
sees the material and the masked label pairs \(e_j = (L_j + H_K(j, a_j B_j),\; L_j + \Delta + H_K(j, a_j(B_j - A_j)))\), makes \(n_1\) steps, each with one query to \(H\), \(H_K\) and \(G\), and commits \(c\);
sees the seed and the secrets \(a_j\), makes \(n_2\) steps, and opens \((z, r)\).
The verifier accepts if \(z\) is the \(1\)-label of the output and \(G(z, r) = c\).
In a run of the prover, let \(B_j\) be its message for input \(j\). The key points of \(j\) are \(K^0_j = a_j B_j\) and \(K^1_j = a_j (B_j - A_j)\); they differ by \(a_j A_j = a_j^2 g\) (Lemma 8.9), so they are distinct when \(a_j \neq 0\). A query to \(H_K\) is at \(K^c_j\) if it is the point \((j, K^c_j)\); the key hash is separated by the index \(j\), so a query \((j', K^c_j)\) with \(j' \neq j\) is not at a key point of \(j\). The key point \(K^c_j\) is early (\(\mathrm{Pre}^c_j\)) if some query of step 1, before \(B\) is sent, is at it. We write \(\mathrm{Zero}\) for the event that some \(a_j = 0\), and \(\mathrm{Both}\) for the event that, for some \(j\), the prover queries both \(K^0_j\) and \(K^1_j\) before it commits.
The real randomness is \(\omega = (a, H_K, J_K, \rho )\), where \(J_K \in (V \times V)^k\) is junk that the game does not use (it only makes the two sides of the same size). Let \(e\) be the real masked pairs of the run of \(\omega \). The map \(\Phi \) sends \(\omega \) to \((\gamma , \rho )\) with \(\gamma = (a, H_K', e')\), where, for every \(j\) and \(c\) such that \(K^c_j\) is not early, \(H_K'(j, K^c_j) = J_{K, j, c}\) and \(e'_{j,c} = e_{j,c}\), and, for every early \(K^c_j\), \(e'_{j,c} = J_{K, j, c}\); at all other points \(H_K' = H_K\). Without \(\mathrm{Zero}\) the two key points of an input are distinct, so these replacements do not collide.
The receiver’s message is \(B = b \cdot g + wA\), and it unmasks \(e_w - H_K(b \cdot A)\). For the analysis we write \(m_c(A, B) = e_c - H_K(\log _g(B - cA) \cdot A)\), the label of the choice \(c\) unmasked with the key of a receiver whose message is \(B\).
The coins are \(\sigma = (a_{-j}, \rho , H_K^*, e^*, J^*)\): the secrets of the other inputs, the randomness \(\rho \) of the garbling, a key hash \(H_K^* : [k] \times \mathbb {G} \to V\), a pair \(e^* \in V \times V\), and junk \(J^* \in (V \times V)^{k - 1}\) that it does not use. In the formalization the coins have the type of the real randomness, with \(a_j = 0\) and \(e^*\) stored as the junk of \(j\). Given \(A \in \mathbb {G}\), the solver \(S_{j,i,i'}\) runs the verifier and the prover, with \(A_j = A\) and \(A_{j'} = a_{j'} g\) for \(j' \neq j\), as follows.
It garbles with \(\rho \). For \(j' \neq j\) it computes the masked pair \(e_{j'}\) as the verifier does, with \(H_K^*\), since it knows \(a_{j'}\). For \(j\) it sends \(e_j = e^*\).
It answers the key queries in order. The query number \(i\), at a point \((j_i, P_i)\), gets \(e^*_0 + L_j\), and the query number \(i'\), at \((j_{i'}, P_{i'})\), gets \(e^*_1 + L_j + \Delta \). A later query at the same point as query \(i\) (resp. \(i'\)) gets the same answer. Every other key query \((j'', P)\) gets \(H_K^*(j'', P)\). It answers \(H\) with the \(H\) of \(\rho \) and \(G\) with \(G\).
It outputs \(P_i - P_{i'}\); the prover makes exactly \(n_K\) key queries before it commits, so both points exist for \(i, i' {\lt} n_K\).
The solver does not use \(a_j\): it only needs \(A\), through the prover’s view.
Let \(\omega = (a, H_K, J_K, \rho )\) be outside \(\mathrm{Zero}\), with real masked pairs \(e\) and key points \(K^0_j, K^1_j\). The map \(\Psi _j\) sends \(\omega \) to \((a_j, \sigma )\) with \(\sigma = (a_{-j}, \rho , H_K^*, e^*, J^*)\), where \(e^* = e_j\), \(J^* = (J_{K, j'})_{j' \neq j}\), and \(H_K^*\) is \(H_K\) with its values at \((j, K^0_j)\) and \((j, K^1_j)\) replaced by \(J_{K,j,0}\) and \(J_{K,j,1}\).
A malicious verifier runs in three phases with adaptive queries to \(G\): \(q_1\) queries and then the material and the OT pairs; after the commitment, \(q_2\) queries and then the opened seed; after the prover’s last message, \(q_3\) queries and then its output bit. In the real execution the prover commits with \(G(Z_w, r)\), where \(Z_w\) is its output label, and sends \((Z_w, r)\) if the opening passes the check. The simulator commits to a uniform \(c\), and if the opening passes the check it computes \(Z = L_{\mathrm{out}} + \Delta \) from the seed, sends \((Z, r)\) and programs \(G(Z, r) := c\). It does not use the witness. The hybrid uses the real commitment point \(p = (Z_w, r)\), a uniform commitment \(c\), and the oracle \(G[p := c]\) after the commitment.
A copy consists of a claimed seed, the material and the pair of labels offered for each input. It is good when it passes the check of Definition 4.2: its material is the garbling of \(C\) with its seed and its pairs are \((L_j, L_j + \Delta )\). Opening a copy reveals the seed, so goodness is checked by garbling again.
The evaluator knows the value and the active label of every wire. At a multiplexer with selector value \(v_s\) and active selector label \(S\), it takes the candidate selected by \(v_s\), with active label \(Y\), and outputs the label \(H(i, S) + Y\), plus \(T_i\) if \(v_s = 1\). The active inputs for \(x\) are the labels \(\operatorname {lab}_\Delta (L_j, x_j)\).
In the real game the material uses the pads \(H(i, S + \Delta ) + c\, \Delta \) and the adversary wins if it outputs \(A + \Delta \). In the simulated game the material uses independent pads \(K \in V^n\), so nothing the adversary sees depends on \(\Delta \); it wins with the same condition, and it hits if one of its queries is an inactive point \((i, S_i + \Delta )\) of the simulated trace.
The garbler’s seed consists of \(\Delta \) and the zero-labels of the inputs and of the constants; the hash is a map \(H \colon \mathbb {N}\times V \to V\) (gate position, label). The node at position \(i\) receives a zero-label \(L_i\) and publishes some material:
\(\mathsf{input}(j)\): \(L_i\) is the zero-label of input \(j\); no material.
\(\mathsf{const}(b)\): \(L_i\) is the zero-label of the constant; the material is its active label \(\operatorname {lab}_\Delta (L_i, b)\).
\(\mathsf{xor}(a, b)\): \(L_i = L_a + L_b\) (Free XOR); no material.
\(\mathsf{mux}(s, z, o)\): \(L_i = H(i, L_s) + L_z\), and the material is the single ciphertext
\[ T_i = H(i, L_s) + H(i, L_s + \Delta ) + L_z + L_o . \]
The ideal garbler runs alongside the evaluator. It receives the active input labels, the active labels of the constants, the hash \(H\) and a pad for each multiplexer, and it never uses \(\Delta \). At a multiplexer in position \(i\), with active selector label \(S\), active candidate labels \(Z\), \(O\) and candidate values \(v_z\), \(v_o\), it publishes
The atoms are the symbols \(a_j\), for the inputs \(j\), and \(b_i\), for the multiplexers \(i\). The linear part \(\ell ^{(k)}_w \in \mathbb {F}_2^{\mathrm{atoms}}\) of a wire is defined by induction:
an input \(j\): \(a_j\) if \(j \notin R_k\), and \(0\) if \(j \in R_k\); a constant: \(0\);
an XOR \(w = a \oplus b\): \(\ell ^{(k)}_a + \ell ^{(k)}_b\);
a multiplexer \(i\): \(\ell ^{(k)}_{c_i}\) if \(\ell ^{(k)}_{s_i} = 0\), and \(b_i + \ell ^{(k)}_{c_i}\) otherwise.
A wire is known at step \(k\) if \(\ell ^{(k)}_w = 0\), and unknown otherwise. The linear part depends only on the circuit, \(R_k\) and \(x^{(k)}\), not on the randomness.
A malicious verifier makes \(q_0\) queries to \(G\) and sends the messages \(A\); after the receiver messages \(B\) it makes \(q_1\) queries and sends the material and the masked pairs; the remaining phases are those of Definition 7.3, and the opening also contains the OT secrets. For fixed \(B\) it is a verifier of Chapter 7 whose OT pairs are \((m_0(A, B), m_1(A, B))\). The prover’s check verifies \(A = a \cdot g\), that the material is the garbling of the opened seed, and that both masked labels of every input unmask, with the sender’s keys, to \((L_j, L_j + \Delta )\). It does not use the witness.
For an input \(x \colon \mathbb {N}\to \{ 0, 1\} \), the values of the nodes of \(C\) are computed in order: \(x_j\), \(b\), \(v_a \oplus v_b\), and \(v_o\) or \(v_z\) according to \(v_s\).
The cheating prover receives the material and the active labels of its OT input \(x\), and at each step makes one query to the garbling hash \(H\) and one to the commitment oracle \(G\). A prover that interleaves its queries arbitrarily is of this form after padding. It makes \(n_1\) steps, commits, sees the opened seed, makes \(n_2\) more steps and opens a point. The verifier accepts if the point has the target label \(L_{\mathrm{out}} + \Delta \) and its value is the commitment.
A common string is a tuple \((g_0, h_0, g_1, h_1)\) of group elements. It is messy, with trapdoor \((x_0, x_1)\), if \(g_0, g_1 \neq 0\), \(h_b = x_b \cdot g_b\) and \(x_0 \neq x_1\); only the extraction uses the trapdoor. The receiver with choice \(\sigma \) and secret \(r\) sends \(\mathit{pk} = (r \cdot g_\sigma , r \cdot h_\sigma )\). The encryption of \(m \in \mathbb {G}\) on branch \(b\) with coins \((s, t)\) is
and \((c_0, c_1)\) decrypts with \(r\) to \(c_1 - r \cdot c_0\). This is [ PVW08 , Sect. 5.3 ] , where encryption is built on the algorithm \(\mathrm{Randomize}\) of [ PVW08 , Lemma 5.1 ] .
A common string is in decryption mode if \(h_b = x \cdot g_b\) for a common \(x\) and \(g_1 = y \cdot g_0\) with \(y \neq 0\). Then the key of the choice \(1\) with secret \(r\) is the key of the choice \(0\) with secret \(y r\) (trapdoor key generation, [ PVW08 , Sect. 5.3 ] ).
For choice bits \(x\), the hybrid \(\mathrm{Hyb}_x\) sends the keys of \(x\) and runs the simulator of Theorem 7.7. The simulator of the protocol is \(\mathrm{Hyb}_0\): it sends the keys of the choice \(0\) and does not use the witness. As a function of the common string, the probability \(p_x\) that the verifier outputs \(1\) in \(\mathrm{Hyb}_x\) is computed without the witness (beyond the bits \(x\)) and without any trapdoor.
The common string is messy and fixed. The cheating prover sends keys \(\mathit{pk}_j\), one for each input; the verifier rejects if some \((\mathit{pk}_j)_1 = 0\). Otherwise it sends, for each input \(j\) and each branch \(b\), the encryption on branch \(b\) of \(\iota (L_j + b\Delta )\), where \(\iota \) is any map from labels to \(\mathbb {G}\), with uniform coins. The rest is the protocol of Theorem 7.15, except that after the opening the prover also sees all the coins of the OT, as in the open-all phase of [ JKO13 , Appendix A ] .
A malicious verifier sees the prover’s keys \(\mathit{pk}_j = \mathrm{keyGen}(w_j, r_j)\); the rest is as in Definition 7.3, with the ciphertexts of both branches in its first message and all the coins of the OT in its opening. The prover decrypts the label of its choice and decodes it with a left inverse of \(\iota \). Its check after the opening: the material is the garbling of the opened seed, and every ciphertext is the encryption of the label of its branch with the opened coins. It does not use the witness.
A deterministic adversary chooses each query from the material and the previous answers, and its output from the material and all \(q\) answers. A randomized adversary is a family of these indexed by its coins.
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
The trace records, for each position \(i\) that holds a multiplexer, its active selector label \(S_i\) and the XOR \(c_i\) of its candidate values. The garbler reads \(H\) at \((i, S_i)\) and the pad at \((i, S_i, c_i)\). In the real scheme the inactive point of position \(i\) is \((i, S_i + \Delta )\).
A possibly malicious verifier sends arbitrary material, an arbitrary pair of labels to the OT functionality for each input, and an arbitrary seed as its opening. A receiver with choice bits \(x\) gets the first or second label of each pair. The honest verifier with seed \(\sigma \) sends the garbling of \(C\), the pairs \((L_j, L_j + \Delta )\), and \(\sigma \).
The honest prover evaluates the material on the labels it received. After the opening it checks that the material is the garbling of \(C\) with the opened seed and that every OT pair is \((L_j, L_j + \Delta )\). The verifier’s view is the opened label if the check passes, and an abort otherwise. The simulator outputs \(L_{\mathrm{out}} + \Delta \), computed from the opened seed, if the check passes, and an abort otherwise; it does not use the witness.
Let \(\Delta \neq 0\) and \(k {\lt} q\). The map of Lemma 10.5 for the game truncated to \(k\) steps is injective on the real randomness whose first bad step is \(k\). On its image the simulated game, for the same \(k\) steps and the same action at step \(k\), has: the action at step \(k\) is a query \((i, y)\) at a multiplexer, and, with \(X\) the simulated active label of its selector \(s_i\) for \(x^{(k)}\), either \(y = X + \Delta \), or \(s_i\) is unknown at step \(k\), \(y = X\), and no query before step \(k\) is at a point \((i', X_{s_{i'}})\) of a multiplexer \(i'\) whose selector is unknown at step \(k\).
If some query is bad for the final input, some step is bad. If \(k\) is the first bad step, the game truncated to its first \(k\) steps has no query bad for its final input, which is \(x^{(k)}\).
For each \(k\), the simulated randomness for which the action at step \(k\) is a query \((i, y)\) with \(s_i\) unknown at step \(k\), \(y = X_{s_i}\), and no earlier query at the active label of a selector unknown at step \(k\) (the condition of Lemma 10.13; in particular none at the point of \(\beta ^*\) for \(s = s_i\), when \(\beta ^*\) is some \(b_{i^*}\)), is at most a fraction \(1/|V|\) of all of it.
In the simulated game at step \(k\), give the atoms the values \(\alpha (a_j) = R_j\) and \(\alpha (b_i) = H'(i, X_{s_i})\), the labels being those for \(x^{(k)}\). Let \(s\) be an unknown wire, and let \(\beta ^*\) be \(b_{i^*}\) for the largest \(i^*\) with \(b_{i^*}\) in \(\ell ^{(k)}_s\) if there is one, and some \(a_j\) in \(\ell ^{(k)}_s\) otherwise. Add \(v\) to the randomness at \(\beta ^*\): to \(R_j\), or to \(H'\) at the point \((i^*, X_{s_{i^*}})\). Then the labels of the wires before position \(i^*\) do not change, and \(X_s\) changes by exactly \(v\).
For \(\Delta \neq 0\), map \((L, L_c, H, J)\) to \((R, A, H', T)\), where \(R_j = L_j + x_j \Delta \) for the final \(x\), \(A\) are the active constant labels, \(H'\) is \(H\) with its values at the inactive points of the final \(x\) replaced by \(J\) (Lemma 6.6), and \(T_i\) is the real ciphertext of node \(i\) if it is a multiplexer and the pad \(J_i\) of Lemma 6.6 otherwise; the injectivity below uses both. The simulated material of the image is the real material. Without a bad query, the simulated game on the image runs exactly as the real game, and a real win is a simulated win.
If a run does not query \(p\), reprogramming the oracle at \(p\) changes none of its answers.
The adversary wins the authenticity game if and only if it outputs \(A + \Delta \), where \(A\) is the active output label that the evaluator computes from the material.
If the prover is accepted and the extractor does not win, then a fresh first-phase query got the answer of an earlier, different one, or a fresh second-phase query got the answer \(c\), or the opened point was never queried and its value is \(c\). Each of these events has probability at most \(1/|D|\) for a fixed pair, query or point.
If \(C\) reads only the inputs \(j {\lt} k\) and \(C(w) = 1\), then whenever the check passes the honest prover’s label is the \(1\)-label \(L_{\mathrm{out}} + \Delta \) of the opened seed.
Let \(\omega \) be outside \(\mathrm{Zero}\) and \(\mathrm{Both}\), and \(\Phi (\omega ) = (\gamma , \rho )\).
(Same run.) The run of the prover in the real game with \(\omega \), up to its commitment, is its run inside \(\mathcal{A}_\gamma \) playing the adaptive game with \(\rho \).
(Injectivity.) \(\Phi \) is injective on the complement of \(\mathrm{Zero} \cup \mathrm{Both}\).
(Wins.) If, in the real run, the first query of step 2 to \(G\) answered with the commitment is at the target label, then \(\mathcal{A}_\gamma \) wins the adaptive game with \(\rho \).
Let \(\omega \) be outside \(\mathrm{Zero}\), in \(\mathrm{Both}_{j,i,i'}\), and \(\Psi _j(\omega ) = (a_j, \sigma )\).
(Same run.) The run of the prover in the real game with \(\omega \), up to its commitment, is its run inside \(S_{j,i,i'}\) with coins \(\sigma \) and input \(A = a_j g\).
(Injectivity.) \(\Psi _j\) is injective on \(\mathrm{Both}_{j,i,i'} \setminus \mathrm{Zero}\).
(Wins.) \(S_{j,i,i'}\) with coins \(\sigma \) wins on \(a_j\): it outputs \(a_j^2 g\).
For a fixed \(G\), the extractor, which replays the first phase and outputs the label of the first \(G\) query answered with the commitment, is an adversary of Theorem 6.12. If \(C\) is unsatisfiable and the extractor returns the target label, this adversary outputs the inactive output label.
Let \(E\) be a set of oracles, and let \(p(G)\) be a point and \(f(G)\) a value that, for \(G \in E\), do not change when \(G\) is reprogrammed at \(p(G)\). Then \(G \in E\) and \(G(p(G)) = f(G)\) for at most a fraction \(1/|D|\) of the oracles.
If every evaluated wire so far carries its plaintext value \(v\) and the label \(\operatorname {lab}_\Delta (L, v)\) of its zero-label \(L\), the same holds after evaluating one more node.
If the first phase does not query \(p\), swapping the value \(G(p)\) with \(c\) turns the hybrid into the real execution. The swap is an involution on these pairs \((G, c)\), so the hybrid and the real execution output \(1\) equally often on them.
The hybrid and the simulator agree unless the second phase, or the third phase after an abort, queries \(p\).
If every input node of \(C\) reads an input \(j {\lt} k\), the evaluation depends only on the input wires \(j {\lt} k\).
Let \(x'\) agree with \(x^{(k)}\) on \(R_k\). There is \(\varphi : \mathrm{atoms} \to \mathbb {F}_2\) with \(v_w(x') + v_w(x^{(k)}) = \sum _\beta \ell ^{(k)}_w(\beta ) \varphi (\beta )\) for every wire \(w\). In particular a known wire has the same value, and in the real game the same active label, on \(x'\) and on \(x^{(k)}\).
For \(j \le k\) there is a linear map \(\psi \) with \(\ell ^{(k)}_w = \psi (\ell ^{(j)}_w)\) for every wire \(w\). In particular a wire known at step \(j\) is known at step \(k\).
If the check passes, the honest prover’s label is \(\operatorname {lab}_\Delta (L_{\mathrm{out}}, v)\), where \(v\) is the plaintext output on \(w\) and \(L_{\mathrm{out}}\), \(\Delta \) come from the opened seed.
Fix the labels. Sampling the coins of both branches is the same as sampling the ciphertexts of the messy branches and the coins of the other branches: the coins of a messy branch are the preimage of its ciphertext.
Let \(\mathrm{ext}(\mathit{pk})\) be \(0\) if \(\mathit{pk}_2 = x_0 \cdot \mathit{pk}_1\) and \(1\) otherwise. If the common string is messy and \(\mathit{pk}_1 \neq 0\), the branch \(1 - \mathrm{ext}(\mathit{pk})\) satisfies the hypothesis of Lemma 9.3. On the other hand, for \(\mathit{pk} = (0, 0)\) the second component of every ciphertext is the message.
If \(g_b \neq 0\) and \(\mathit{pk}_2 \neq x_b \cdot \mathit{pk}_1\), then for every message \(m\) the encryption on branch \(b\) is a bijection from the coins \(\mathbb {Z}_q^2\) onto \(\mathbb {G}^2\). In particular, with uniform coins the ciphertext is uniform whatever \(m\) is. This is the second case of [ PVW08 , Lemma 5.1 ] , in exact form.
The messy setup is the distribution of random tuples conditioned on \(a, b \neq 0\), and the decryption setup is the distribution of DDH tuples conditioned on \(a \neq 0\).
If the adversary wins the real game with \(H\), it wins or hits in the simulated game with \((H', K)\).
The receiver obtains \(m_w(A, B)\), a function of the sender’s messages and of \(B\) only. If \(A = a \cdot g\), then \(m_c(A, B) = e_c - H_K(a \cdot (B - cA))\), which the receiver can compute once \(a\) is opened.
Let the seed consist of \(\Delta \), zero-labels \(L^{\mathrm{in}}\) of the inputs \(j {\lt} k\) and zero-labels \(L^{\mathrm{c}}\) of the constants; the zero-labels of the inputs \(j \geq k\) are \(0\). Let \(x_j = 0\) for \(j \geq k\), so that the active labels of these inputs are \(0\) as well (with \(x_j = 1\) the active label would be \(\Delta \) itself, as for \(C = [\mathrm{input}(k)]\)). Then the material of the real garbling, and the game in which the adversary also receives the active labels of \(x\), coincide with the game of Theorem 6.9 with the fixed active labels \(L^{\mathrm{in}}_j + x_j\Delta \) and \(L^{\mathrm{c}}_i + b_i \Delta \).
Fix \(\Delta \neq 0\). Given \((H, J)\) with \(J \in V^n\), let \(H'\) be \(H\) with its value at each inactive point \((i, S_i + \Delta )\) replaced by \(J_i\), and let \(K_i = H(i, S_i + \Delta ) + c_i\Delta \) at multiplexers and \(K_i = J_i\) elsewhere. Then the simulated game with \((H', K)\) has the same material, wires and trace as the real game with \(H\), and the map \((H, J) \mapsto (H', K)\) is injective.
Two runs of the ideal garbler whose hashes and pads agree at the points named by the trace of the first produce the same material, the same wires and the same trace.
Let \(C\) be the circuit \(x_0 \oplus x_1\), and let \(a \neq 0\). A verifier that sends the honest material of \(C\) but offers the OT pairs \((0, a)\) for input \(0\) and \((0, 0)\) for input \(1\) receives the label \(a\) from a prover with witness \((1, 0)\) and the label \(0\) from a prover with witness \((0, 1)\). Both are witnesses, so a prover that sends its label without checking reveals its first witness bit. Whatever seed the verifier opens, the prover’s check rejects these messages, since the pairs are not of the form \((L_j, L_j + \Delta )\) for a single \(\Delta \), so in the full protocol the view is an abort for both witnesses (Theorem 4.5).
In the adaptive authenticity game, an adversary taking \(q\) actions wins with probability at most
With \(\Delta \) uniform on \(V \setminus \{ 0\} \) and the rest uniform, a query bad for the final input occurs with probability at most \(q \bigl( 1/(|V| - 1) + 1/|V| \bigr)\), for an adversary taking \(q\) actions.
Let \(V\) be finite. With \(\Delta \) uniform on \(V \setminus \{ 0\} \) and the zero-labels and the hash uniform, the adversary wins without a bad query with probability at most \(1/(|V| - 1)\). Hence it wins with probability at most \(1/(|V| - 1)\) plus the probability of a bad query.
The probability that the verifier accepts a cheating prover is at most the probability that the extractor outputs the target label, plus
For every evaluation set \(E\), an opened copy is bad, or an evaluated copy outputs \(C(x)\) with its label, or \(E\) is exactly the set of bad copies. The last event has probability at most \(1/\binom {N}{t}\) for a uniform \(t\)-subset, and exactly \(2^{-N}\) with independent fair coins.
If \(E\) is uniform among the subsets of size \(t \le N\), the garbler cheats with probability at most \(1/\binom {N}{t}\), with equality when \(|B| = t\).
If each circuit is evaluated or opened with an independent fair coin, every garbler cheats with probability exactly \(2^{-N}\).
For an unsatisfiable circuit, the verifier accepts with probability at most
where \(Q = 2(k + n_1)\) is the number of actions of the adversary of Lemma 11.6 in the adaptive game, \(n_K = n_0 + n_1\) is the number of key queries, and \(S_{j,i,i'}\) are explicit square Diffie–Hellman solvers built from the prover (Definition 11.8). A solver depends on the commitment oracle \(G\) and on \(\Delta \), and \(\mathrm{Adv}_{\mathrm{sqDH}}(S_{j,i,i'})\) is the probability, over a uniform \(\alpha \in \mathbb {Z}_q\) and the coins of the solver, that it outputs \(\alpha ^2 g\) on input \(\alpha g\), averaged over \(G\) and \(\Delta \neq 0\). The advantages are added, not averaged, over the \(k\, n_K (n_K - 1)\) solvers.
Let \(|V| \geq 2\), let the seed of the verifier, the hash \(H\) and the commitment oracle \(G\) be uniform, and let \(C\) be unsatisfiable. A cheating prover with \(n_1\) steps before the commitment and \(n_2\) after it is accepted with probability at most
In the formalization the hypothesis on \(C\) is weaker: \(C(x) = 0\) for the input \(x\) that the prover gives to the OT, which is fixed in advance, with \(x_j = 0\) for \(j \geq k\).
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|\).
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.
Let \(V\) be finite with \(|V| \geq 2\), and let the garbler choose \(\Delta \neq 0\), the hash \(H\) and the zero-labels of the inputs and of the constants uniformly. Let \(x\) be an input fixed in advance, with \(x_j = 0\) for \(j \geq k\) as in Lemma 6.11. An adversary that sees the material and the active labels of \(x\), and makes \(q\) adaptive queries to \(H\), outputs the inactive output label with probability at most \((q + 1)/(|V| - 1)\).
If \(C(w) = 1\), then against the honest verifier with seed \(\sigma \) the label the prover sends is \(L_{\mathrm{out}} + \Delta \), computed from \(\sigma \). It does not depend on the witness.
Let \(V\) be finite with \(|V| \geq 2\). Fix the circuit, the active labels and \(H\), and let \(\mathcal{A}\) be any map from materials to \(V\). For any \(m\), let the pads of the positions \(i {\lt} m\) be the entries of \(K \in V^m\) and the other pads be \(0\). Among the pairs \((\Delta , K)\) with \(\Delta \neq 0\) and \(K \in V^m\), at most \(|V|^m\) satisfy \(\mathcal{A}(\mathsf{M}) = A(\mathsf{M}) + \Delta \), where \(\mathsf{M}\) is the material with pads \(K\). With \(\Delta \) uniform on \(V \setminus \{ 0\} \) and \(K\) uniform, the success probability is at most \(1/(|V| - 1)\).
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.
For every function \(F\) of the common string with values in \([0, 1]\), the averages of \(F\) over the messy and the decryption setups differ by at most the DDH advantage of \(F\), read as a function of the tuple, plus \(3/q\).
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.
For an unsatisfiable circuit and a messy common string, with the seed, the hashes and the coins of the OT uniform, the verifier accepts with probability at most
the bound of Theorem 7.15.
For every common string, every malicious verifier and every witness of a circuit that reads only the inputs \(j {\lt} k\),
Let the verifier depend on the common string and make at most \(Q\) queries. Averaged over the messy setup, the real execution and the simulator differ by at most
Let the verifier depend on the common string and make at most \(Q\) queries. Averaged over a nonempty set \(S_m\) of common strings, the real execution and the simulator differ by at most
for every set \(S_d\) of decryption-mode strings.
The material of the real garbling is the material of the ideal garbler with the pads
Here \(S + \Delta \) is the inactive selector label of the multiplexer.
Let \(V\) be finite with \(|V| \geq 2\). Summed over \(\Delta \neq 0\), the hash functions for which a \(q\)-query adversary outputs the inactive output label number at most \((q + 1)\, |V|^{n |V|}\). With \(\Delta \) uniform on \(V \setminus \{ 0\} \) and \(H\) uniform, the success probability is at most
Let a receiver make \(n\) queries to the key hash, at points \(Q_0, \dots , Q_{n-1}\) that, like its message \(B\), are functions of \(A\) alone: it does not adapt to the answers of the hash or to the masked labels (the general case is Chapter 11). For uniform \(a\), the probability that it queries both key points of an input is at most the sum, over the \(n^2\) pairs of query positions \((i, j)\), of the probability that the solver \(A \mapsto Q_i - Q_j\) computes \((a a) \cdot g\) from \(a \cdot g\); hence at most \(n^2\) times the best square Diffie–Hellman advantage.
If \(C(w) = 1\), then for every message of the verifier its view of the honest prover equals the output of the simulator. In particular the view is the same for any two witnesses.
For every malicious verifier and every witness \(w\) of a circuit that reads only the inputs \(j {\lt} k\), the probabilities that the verifier outputs \(1\) in the real execution and with the simulator differ by at most
The simulator chooses the receiver messages \(B\) uniformly and runs the simulator of Theorem 7.7.
For every malicious verifier and every witness \(w\) with \(C(w) = 1\), the probabilities that the verifier outputs \(1\) in the real execution and with the simulator differ by at most