Zero knowledge from privacy-free garbled circuits

5 Authenticity: where \(\Delta \) enters the view

The evaluator can compute every active label from the material and the active inputs, and the inactive label of a wire is the active one plus \(\Delta \). Authenticity therefore amounts to the impossibility of finding \(\Delta \). In this chapter we show that \(\Delta \) reaches the evaluator’s view only through the hashes of the inactive selector labels.

Lemma 5.1
✓

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.

Proof ▶

By Theorem 3.8, \(A = \operatorname {lab}_\Delta (L_{\mathrm{out}}, v)\), and \(\operatorname {lab}_\Delta (L_{\mathrm{out}}, 1 - v) = A + \Delta \).

5.1 The ideal garbler

Definition 5.2 Ideal garbler
✓

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

\[ T_i = H(i, S) + Z + O + \mathrm{pad}_i(S, v_z \oplus v_o) . \]
Theorem 5.3 The real material is ideal
✓

The material of the real garbling is the material of the ideal garbler with the pads

\[ \mathrm{pad}_i(S, c) = H(i, S + \Delta ) + c\, \Delta . \]

Here \(S + \Delta \) is the inactive selector label of the multiplexer.

Proof ▶

By induction on the nodes. If the two materials coincide before node \(i\), the evaluation reaches node \(i\) with the same wires, and by Lemma 3.7 each wire carries the label \(\operatorname {lab}_\Delta (L, v)\) of its zero-label \(L\) and its plaintext value \(v\). At a multiplexer the two hashes \(H(i, L_s)\), \(H(i, L_s + \Delta )\) are \(H(i, S)\) and \(H(i, S + \Delta )\) in some order, and \(Z + O + (v_z \oplus v_o)\Delta = L_z + L_o\). A case analysis on \(v_s, v_z, v_o\) shows that the entries of node \(i\) coincide too.

Corollary 5.4
✓

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.

Proof ▶

The ideal garbler reads the pad of position \(i\) only once, at position \(i\); take \(K_i\) to be the value it reads.

5.2 The bound in the ideal model

Theorem 5.5 Authenticity in the ideal model
✓

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

Proof ▶

The material does not depend on \(\Delta \), so for each \(K\) the condition determines \(\Delta \).

The bound holds for every fixed value of the active labels and of \(H\), hence on average over any distribution of them independent of \((\Delta , K)\). In the real scheme the pads are hashes at inactive points; the next chapter justifies the replacement by uniform pads in the random oracle model.