Zero knowledge from privacy-free garbled circuits

6 Authenticity in the random oracle model

We work in the random oracle model [ BR93 ] . The hash is now a uniformly random function \(H \colon \{ 0, \dots , n - 1\} \times V \to V\), where \(n\) is the number of nodes, and \(\Delta \) is uniform on \(V \setminus \{ 0\} \). The adversary sees the material, makes \(q\) adaptive queries to \(H\), and outputs a label. The active labels of the inputs and of the constants are first fixed parameters; Theorem 6.12 at the end of the chapter removes this restriction and bounds the real garbling with uniform zero-labels.

6.1 The trace of the garbler

Definition 6.1 Trace
✓

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

Lemma 6.2 Congruence
✓

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.

Proof ▶

Induction on the nodes; a node reads only the hash and the pad of its own position.

6.2 Adversaries and the two games

Definition 6.3 Adversary
✓
#

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.

Lemma 6.4 Identical until bad
✓
#

Two oracles that agree at every query the adversary asks give the same answers.

This is the deterministic core of the fundamental lemma of game playing of Bellare and Rogaway [ BR06 , Lemma 2 ] ; see also Shoup [ Sho04 ] . In the proofs below it is used through injections between sets of randomness rather than through probabilities.

Proof ▶

Induction on the number of queries.

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.

6.3 The reduction

Lemma 6.6 Moving the inactive values into the pads
✓

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.

Proof ▶

Active and inactive points differ because \(\Delta \neq 0\), so \(H'\) agrees with \(H\) at the active points, and the pads agree by construction; Lemma 6.2 gives the first claim. Both traces coincide, so \(H\) is recovered from \(H'\) off the inactive points and from \(K\) at them, and \(J\) from \(H'\) at the inactive points and from \(K\) elsewhere.

Lemma 6.7
✓

If the adversary wins the real game with \(H\), it wins or hits in the simulated game with \((H', K)\).

Proof ▶

If it does not hit, its queries avoid the inactive points, where alone \(H\) and \(H'\) differ; by Lemma 6.4 it gets the same answers, hence outputs the same label.

Lemma 6.8
✓
#

For fixed \((H', K)\), at most \(q + 1\) values of \(\Delta \) give a simulated win or a hit.

Proof ▶

A win fixes \(\Delta = Z - A\), and the \(k\)-th query \((i, y)\) hits only for \(\Delta = y - S_i\).

Theorem 6.9 Authenticity in the random oracle model
✓
#

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

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

For each \(\Delta \), Lemmas 6.6 and 6.7 inject the real wins, times \(|V|^n\) choices of \(J\), into the simulated wins or hits. Summing over \(\Delta \) and swapping the sums, Lemma 6.8 bounds the total by \((q + 1)\) times the number of pairs \((H', K)\). Divide by \(|V|^n\).

6.4 The real garbling

Lemma 6.10
✓
#

The ideal garbler reads the active label of a constant only at the bit of that constant.

Proof ▶

Induction on the nodes.

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

Proof ▶

Theorem 5.3 and Lemma 6.10.

Theorem 6.12 Authenticity of the real garbling
✓
#

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

Proof ▶

For fixed \(\Delta \), the maps \(L^{\mathrm{in}} \mapsto L^{\mathrm{in}} + x\Delta \) and \(L^{\mathrm{c}} \mapsto L^{\mathrm{c}} + b\Delta \) are bijections. By Lemma 6.11 the sum over \(\Delta \) and the zero-labels becomes a sum over the active labels, outside, of the sums of Theorem 6.9, inside.

Remark 6.13
#

The bound of Theorem 6.9 does not use characteristic \(2\): it holds for labels in any finite abelian group. Theorem 6.12 does use it, through Theorem 5.3. With \(128\)-bit labels the authenticity advantage of an adversary making \(q\) hash queries is at most \((q + 1)/(2^{128} - 1)\). Theorem 4.8 suggests the same bound for the soundness error of the protocol in the hybrid model; the formal statement, with the hash commitment and a prover with a bounded number of queries, is Theorem 7.15.