Zero knowledge from privacy-free garbled circuits

3 Privacy-free Free-XOR garbling

Labels live in a vector space \(V\) over \(\mathbb {F}_2\); for instance \(V = \mathbb {F}_2^{128}\), that is, 128-bit strings with XOR. A wire carries one of two labels, \(L\) for the bit \(0\) and \(L + \Delta \) for the bit \(1\), where \(\Delta \in V\) is a global offset chosen by the garbler. The evaluator holds one of them, the active label; the other one is inactive.

3.1 Circuits and plaintext evaluation

Definition 3.1 Circuits
✓
#

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 multiplexer \(\mathsf{mux}(s, z, o)\) outputs the value of \(o\) if \(s\) is \(1\) and the value of \(z\) otherwise; AND and OR are multiplexers with a constant candidate. Accepting arbitrary positions avoids carrying a well-formedness hypothesis through every statement.

Definition 3.2 Plaintext evaluation
✓
#

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

3.2 Garbling and evaluation

Definition 3.3 Labels of a bit
✓
#

For a zero-label \(L\) and a bit \(b\), \(\operatorname {lab}_\Delta (L, b) = L + b\, \Delta \).

Definition 3.4 Garbling
✓

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 . \]
Remark 3.5 The multiplexer is a half-gate
#

Since \(\mathsf{mux}(s, z, o) = z \oplus (s \wedge (z \oplus o))\), the multiplexer is an AND gate whose first input \(s\) is known to the evaluator, followed by a free XOR with \(z\). The evaluator half-gate of Zahur, Rosulek and Evans [ ZRE15 , Sect. 3.1 ] garbles \(c = a \wedge b\), with \(a\) known to the evaluator and zero-labels \(A\), \(B\), by choosing the zero-label \(C = H(A)\) and sending the single ciphertext \(H(A) \oplus H(A \oplus R) \oplus B\), where \(R\) is the global offset. With \(A = L_s\), \(B = L_z + L_o\) (the zero-label of \(z \oplus o\)) and \(R = \Delta \), this is \(T_i\), and the free XOR with \(z\) turns \(C\) into \(L_i = H(i, L_s) + L_z\). The gate position \(i\) in the hash plays the role of their gate index \(j\) [ ZRE15 , Sect. 3.2 ] . Garbling every AND gate this way, with free XOR gates, is their privacy-free scheme [ ZRE15 , Sect. 6 ] .

Definition 3.6 Evaluation
✓

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

3.3 Correctness

Lemma 3.7 One step
✓
#

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.

Proof ▶

Only the multiplexer needs a computation. If \(v_s = 0\) the evaluator holds \(S = L_s\) and gets \(H(i, L_s) + L_z + v_z \Delta = \operatorname {lab}_\Delta (L_i, v_z)\). If \(v_s = 1\) it holds \(S = L_s + \Delta \) and gets

\[ H(i, L_s + \Delta ) + L_o + v_o\Delta + T_i = H(i, L_s) + L_z + v_o \Delta , \]

since every other term appears twice and \(V\) has characteristic \(2\).

Theorem 3.8 Correctness
✓
#

For every circuit \(C\), seed, hash \(H\) and input \(x\), evaluating the garbling of \(C\) on the active inputs of \(x\) gives, at every node \(i\), the plaintext value \(v_i\) and the label \(\operatorname {lab}_\Delta (L_i, v_i)\).

Proof ▶

Induction on the nodes, with Lemma 3.7.

Remark 3.9
#

No hypothesis on \(H\) or on \(\Delta \) is needed: correctness is pure algebra in characteristic \(2\). It is the correctness of the scheme for an honest garbler.