Zero knowledge from privacy-free garbled circuits

10 Adaptive authenticity

Status. No originality is claimed for this chapter. We expect a bound of this kind to be known to specialists, but we have not found a published statement of it (see below). Everything in it is formalized: the reduction to the bad event (Section 10.3) and the bound on the bad event (Section 10.4).

Where the problem comes from. In the protocol of [ JKO13 ] the problem does not arise: the OT is the functionality \(\mathcal{F}_{\mathrm{COT}}\), which fixes the prover’s choice bits before the garbled circuit is sent ( [ JKO13 , Fig. 3 and Fig. 6 ] ), and the authenticity needed is static [ JKO13 , Definition 2 ] . It arises only when \(\mathcal{F}_{\mathrm{COT}}\) is replaced by an OT from which the receiver’s choice cannot be extracted when its message is sent, as with the Chou–Orlandi protocol of Chapter 8, whose receiver message \(B\) does not fix the choice. As Byali, Patra, Ravi and Sarkar [ BPRS17 , Sect. 3 ] and Doerner, Kondi, Lee and shelat [ DKLs18 , App. A ] point out, a corrupted receiver can delay the decryption, so a simulator cannot extract its choice before the end of the protocol. Chou and Orlandi acknowledge the issue in the revised version of their paper [ CO15 , Sect. 1.1 ] , where the attacking party is called the sender, and note that it matters, for instance, when the OT is combined with garbled circuits. They withdraw the claim of UC security and suggest, as a remedy, a receiver message that proves timely decryption. This is a different issue from the one raised by Genç, Iovino and Rial [ GIR ] , who point out a flaw in the UC security proof of [ CO15 ] for a corrupted sender; a claim of theirs about a corrupted receiver, made in an earlier version, was withdrawn [ GIR , Sect. 1 ] . An OT that realizes \(\mathcal{F}_{\mathrm{COT}}\) avoids it; Chapter 9 does this with the OT of [ PVW08 ] .

With the Chou–Orlandi OT the receiver’s message \(B\) does not commit to a choice: the prover receives both masked labels of every input together with the material, and it decides which key point of \(H_K\) to query, that is, which label to unmask, after seeing the material. Soundness with the real OT therefore needs authenticity when the input \(x\) is chosen adaptively, after the material and possibly after queries to \(H\). The bound of Chapter 6 is for a fixed \(x\), and its proof writes the material through the ideal garbler for that \(x\) (Theorem 5.3), which is circular when \(x\) is chosen later. Bellare, Hoang and Rogaway [ BHR12 ] define adaptive authenticity in two forms [ BHR12 , Sect. 4, Fig. 6 ] : \(\mathrm{aut1}\), where the adversary chooses \(x\) after seeing the garbled circuit, and \(\mathrm{aut2}\), where the bits of \(x\) are chosen one at a time and each one is answered with its token. The game below is \(\mathrm{aut2}\), with access to the random oracle added. Their results (Theorems 5 and 6, proved in their full version) are transforms that turn any statically secure scheme into an adaptively secure one, by masking the garbled circuit until the input is given; they do not say whether privacy-free Free-XOR garbling itself is \(\mathrm{aut2}\)-secure, which is what we would need here. More recently, Barnum, Heath, Kolesnikov and Ostrovsky prove adaptive security of unmodified schemes, half-gates among them, in the non-programmable random oracle model [ BHKO26 ] ; but their notion is adaptive privacy [ BHKO26 , Definition 5 ] (and obliviousness), not authenticity, and their argument ( [ BHKO26 , Theorem 9 ] : query hiding plus private rekeying) is of the same kind as the bad event of Section 10.4. Guo, Yang, Wang, Yu and Liu prove that unmodified half-gates (the version with privacy, with a hash built from a random permutation) is adaptively secure in the non-programmable random permutation model [ GYWYL , Sect. 5, Theorem 1 ] ; their notion is again simulation-based privacy [ GYWYL , Definition 1 ] , and their method, the H-coefficient technique, bounds the statistical distance between the real and the simulated transcripts. We have not found a published statement of adaptive authenticity for privacy-free garbling.

10.1 The game

Definition 10.1 Adaptive authenticity game
✓

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\).

If the adversary has requested every input that the circuit reads, it can compute \(X_{\mathrm{out}}\) from the material, the requested labels and the queries \((i, S_i)\) at the active selector labels, and then winning amounts to finding \(\Delta \). In general it must produce \(X_{\mathrm{out}} + \Delta \), and an unrequested input read by the circuit only makes this harder.

Remark 10.2 The model
#

The hash is a uniformly random function \(H\) and the adversary is computationally unbounded; only its number \(q\) of actions is bounded. Authenticity is a game, not a simulation-based notion: no simulator answers the adversary’s queries, so the oracle is never programmed. The simulated game of Definition 10.3 and the maps between randomness of Lemmas 10.5 and 10.15 are devices of the proof, which counts the values of \((\Delta , L, L_c, H)\) for which the adversary wins; the bound is a statement about the real game with \(H\) uniform. The distinction between programmable and non-programmable random oracles, which matters for the simulation-based privacy results of [ BHKO26 ] and [ GYWYL ] , does not arise here. What the bound does assume is the random oracle model itself, with \(H\) used only by the garbling scheme; instantiations of \(H\) are not covered (see Chapter 14), and in a protocol that uses a hash elsewhere the garbling must hash in a separate domain (Remark 10.18). Circuits are lists of nodes in evaluation order, and every operand refers to an earlier position; “position” and “largest \(i\)” below refer to this order.

10.2 The simulated game

Definition 10.3 Simulated game
✓

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.

10.3 The real game without bad queries

The zero-labels \(L_s\) of the simulated game of Definition 10.3 depend on the final choice \(x\), so two runs with different completions do not share them. This breaks a direct extension of the injection of Chapter 6: the map from real to simulated randomness has to know \(x\) to move the hash values at the inactive points, and on a run with a bad query \(x\) cannot be read back from the image. We therefore take the bad event in the real game, where the two points \(L_s\), \(L_s + \Delta \) of every selector are fixed by the garbler’s randomness, and for the final \(x\).

Definition 10.4 The adaptive game in Lean
✓

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.

Section 10.4 bounds the probability of a query bad for the final input.

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.

Proof ▶

Requests are answered with \(R_j\) in both games, since the first requested bit is the final one. Queries are answered by \(H\) and \(H'\), which differ only at the inactive points. The active output label is the same with \(H\) and with \(H'\), because the evaluator reads the hash only at active points.

Lemma 10.6 Injectivity
✓

For \(\Delta \neq 0\) the map of Lemma 10.5 is injective on the real randomness without a bad query.

Proof ▶

The image determines the run of the simulated game, which is the real run, hence the final \(x\). Then \(R\) and \(A\) give \(L\) and \(L_c\). The material determines the pads of Lemma 6.6 at the multiplexers, and \(T\) gives them elsewhere; with \(H'\), injectivity of the map of Lemma 6.6 gives \((H, J)\).

Theorem 10.7 Winning without a bad query
✓

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.

Proof ▶

For each \(\Delta \neq 0\), Lemmas 10.5 and 10.6 inject the real wins without a bad query into the simulated wins. The simulated game does not use \(\Delta \), so each simulated randomness wins for at most one \(\Delta \). Sum over \(\Delta \) and swap the sums.

With Theorem 10.7, Theorem 10.17 reduces to Theorem 10.16, the bound on bad queries.

10.4 Bad queries

We bound the probability of a query that is bad for the final input. The difficulty is that this event is not decided at the time of the query: whether a point is inactive depends on bits the adversary requests later. We replace it by an event that is decided at the time of the query, and for that we need to know which selector labels the adversary can know at that time. A selector whose value is fixed by the bits requested so far does not qualify: the XOR of two wires that always carry opposite values has a fixed value, but its label may involve hash values the adversary has never seen. The right notion is a combinatorial “linear part” of each label.

Fix the adversary and a step \(k\). Let \(R_k\) be the set of inputs requested before step \(k\), and \(x^{(k)}\) the input formed by the bits requested before step \(k\), with \(0\) elsewhere. For a wire \(w\), \(v_w(x)\) is its value on the input \(x\) and \(X^{(k)}_w\) its active label for \(x^{(k)}\); in the real game \(X^{(k)}_w = Z_w + v_w(x^{(k)}) \Delta \), where \(Z_w\) is the zero-label. For a multiplexer at position \(i\), \(s_i\) is its selector and \(c_i\) the candidate selected by \(v_{s_i}(x^{(k)})\).

Definition 10.8 Linear part
✓
#

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.

The atom \(b_i\) stands for the hash value \(H(i, X^{(k)}_{s_i})\) read by the evaluator at an unknown selector, and \(a_j\) for the label of an input not yet requested. Lemma 10.14 makes this precise.

Lemma 10.9 Known wires are determined
✓

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)}\).

Proof ▶

Put \(\varphi (a_j) = x'_j + x^{(k)}_j\) and \(\varphi (b_i) = v_i(x') + v_i(x^{(k)}) + v_{c_i}(x') + v_{c_i}(x^{(k)})\), and argue by induction on the position. Inputs, constants and XORs are immediate. At a multiplexer with an unknown selector the claim is the definition of \(\varphi (b_i)\) together with the induction hypothesis for \(c_i\). At a multiplexer with a known selector the selector has the same value on \(x'\) and on \(x^{(k)}\) by induction, so both select \(c_i\), and \(v_i = v_{c_i}\) on both inputs. The active label is \(Z_w + v_w \Delta \).

Lemma 10.10 Monotonicity
✓

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\).

Proof ▶

Put \(\psi (a_t) = a_t\) if \(t \notin R_k\) and \(0\) otherwise, and \(\psi (b_i) = \ell ^{(k)}_i + \ell ^{(k)}_{c^{(j)}_i}\), where \(c^{(j)}_i\) is the candidate selected at step \(j\). By induction on the position: XORs are linear; at a multiplexer with a selector unknown at step \(j\), \(\psi (\ell ^{(j)}_i) = \psi (b_i) + \psi (\ell ^{(j)}_{c^{(j)}_i}) = \ell ^{(k)}_i + \ell ^{(k)}_{c^{(j)}_i} + \ell ^{(k)}_{c^{(j)}_i} = \ell ^{(k)}_i\). At a multiplexer with a selector known at step \(j\), the selector is known at step \(k\) (its linear part is \(\psi (0) = 0\)), and by Lemma 10.9, since \(x^{(k)}\) agrees with \(x^{(j)}\) on \(R_j\), it has the same value at both steps; so the same candidate \(c\) is selected, and \(\ell ^{(k)}_i = \ell ^{(k)}_c = \psi (\ell ^{(j)}_c) = \psi (\ell ^{(j)}_i)\).

Definition 10.11 Bad step
✓
#

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 \} \).

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)}\).

Proof ▶

Let the query at step \(k\) be bad for the final input \(x\): \(y = X_s + \Delta \) for the active label \(X_s\) of \(s\) on \(x\). Since \(x\) agrees with \(x^{(k)}\) on \(R_k\), if \(s\) is known at step \(k\) then \(X_s = X^{(k)}_s\) by Lemma 10.9; otherwise \(y\) is one of \(Z_s, Z_s + \Delta \) anyway. For the second claim, let \(j {\lt} k\) and let the query at step \(j\) be \((i, y)\) with selector \(s\). If \(s\) is known at step \(j\), then \(X^{(k)}_s = X^{(j)}_s\) by Lemma 10.9, and \(y \ne X^{(j)}_s + \Delta \) because step \(j\) is not bad. If \(s\) is unknown at step \(j\), \(y\) is neither of its two points.

Lemma 10.13 The image of a first bad step
✓

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\).

Proof ▶

Injectivity is Lemma 10.6 for the truncated game, which has no bad query by Lemma 10.12. The simulated run on the image coincides with the real run for \(k\) steps (Lemma 10.5), so the action at step \(k\) is the same, and the active labels for \(x^{(k)}\) are the same in both games, because the evaluator reads the hash only at active points. A selector unknown at step \(k\) is unknown at every earlier step (Lemma 10.10), so a query at one of its points before step \(k\) would be a bad step.

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\).

Proof ▶

Write \(\delta \) for the change. By induction on the position, \(\delta X_w = \sum _\beta \ell ^{(k)}_w(\beta )\, \delta \alpha (\beta )\). XORs are linear. At a multiplexer with an unknown selector, \(X_i = \alpha (b_i) + X_{c_i}\), plus \(T_i\) if the selector is \(1\). At a multiplexer with a known selector, \(X_i = H'(i, X_{s_i}) + X_{c_i}\) (plus \(T_i\)); the selector label does not change (its linear part is \(0\)), and neither does \(H'\) at gate \(i\), since \(i \neq i^*\). The atoms change as follows: \(\delta \alpha (\beta ^*) = v\); the other \(a_j\) do not change; \(\delta \alpha (b_i) = 0\) for \(i {\lt} i^*\), because the labels before \(i^*\) do not change (by the same induction, the linear parts of those wires involve only such atoms). Since \(\ell ^{(k)}_s\) contains no \(b_i\) with \(i {\gt} i^*\), \(\delta X_s = v\).

Lemma 10.15 Fresh labels
✓

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.

Proof ▶

Map a pair \((\sigma , v)\), with \(\sigma \) in this set and \(v \in V\), to \(\sigma \) shifted by \(v\) at \(\beta ^*\). The shift does not change the view up to step \(k\): \(R_j\) is not requested before step \(k\), and \(H'\) changes at a point not queried before step \(k\). So the image determines the run up to step \(k\), hence \(x^{(k)}\), the linear parts, \(\beta ^*\) and its point (the labels before \(i^*\) do not change). Then \(v = X_{s_i} - y\) on the image, by Lemma 10.14, and \(\sigma \) is recovered. So the map is injective, and the set has at most \(|\mathrm{Sim}| / |V|\) elements.

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.

Proof ▶

By Lemma 10.12 it suffices to bound, for each \(k {\lt} q\), the randomness whose first bad step is \(k\). Fix \(\Delta \neq 0\) and inject it into the simulated randomness by Lemma 10.13. The images with \(y = X + \Delta \) occur, for each simulated randomness, for at most one \(\Delta \), since the simulated game does not use \(\Delta \). The others lie, for every \(\Delta \), in the set of Lemma 10.15. Summing over \(\Delta \), the count is at most \(|\mathrm{Sim}| + (|V| - 1)|\mathrm{Sim}|/|V|\); divide by \((|V| - 1) |\mathrm{Sim}|\) and sum over \(k\).

Theorem 10.17 Adaptive authenticity
✓

In the adaptive authenticity game, an adversary taking \(q\) actions wins with probability at most

\[ \frac{q + 1}{|V| - 1} + \frac{q}{|V|} . \]

For \(|V| \geq 2\) this is at most \((2q + 1)/(|V| - 1)\), an elementary inequality that is not part of the formal statement.

Proof ▶

Theorem 10.7 and Theorem 10.16.

Remark 10.18 The Chou–Orlandi OT
#

Theorem 10.17 is used in Chapter 11, with Lemma 8.9 (both labels of an input require solving square Diffie–Hellman) and a simulation of the OT layer by label requests, to extend the soundness of Chapter 7 to the Chou–Orlandi OT. The OT derives its keys with a hash as well. Theorem 10.17 is for an oracle used only by the garbling, so the two must hash in separate domains (for instance with distinct prefixes), which makes them independent random oracles.