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
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 )\).
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.
Induction on the nodes; a node reads only the hash and the pad of its own position.
6.2 Adversaries and the two games
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.
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.
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
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.
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.
If the adversary wins the real game with \(H\), it wins or hits in the simulated game with \((H', K)\).
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.
For fixed \((H', K)\), at most \(q + 1\) values of \(\Delta \) give a simulated win or a hit.
A win fixes \(\Delta = Z - A\), and the \(k\)-th query \((i, y)\) hits only for \(\Delta = y - S_i\).
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
6.4 The real garbling
The ideal garbler reads the active label of a constant only at the bit of that constant.
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 \).
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)\).
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.
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.