Zero knowledge from privacy-free garbled circuits

4 The protocol of Jawurek, Kerschbaum and Orlandi

The prover wants to convince the verifier that it knows \(w\) with \(C(w) = 1\), where \(C\) is a circuit with a designated output node. We follow the protocol \(\pi _{\mathrm{ZK}}\) of [ JKO13 ] (Sect. 4, Theorem 2, and Fig. 6 of the ePrint version), which is stated in the \((\mathcal{F}_{\mathrm{COT}}, \mathcal{F}_{\mathrm{COM}})\)-hybrid model: \(\mathcal{F}_{\mathrm{COT}}\) is an OT with an open-all phase in which the sender reveals all its inputs ( [ JKO13 , Fig. 3 ] , “OT with sender verifiability”), and \(\mathcal{F}_{\mathrm{COM}}\) is an ideal commitment. In \(\pi _{\mathrm{ZK}}\) the prover sends its choice bits to \(\mathcal{F}_{\mathrm{COT}}\) first, and the garbled circuit is sent after the transfer. Our model below abstracts the OT and its open-all phase by the opened seed:

  1. Through the OT functionality the prover receives, for each input \(j\), the label of the bit \(w_j\). The verifier garbles \(C\) with a seed \(\sigma \) and sends the material.

  2. The prover evaluates and commits to the output label \(Z\).

  3. The verifier opens \(\sigma \). The prover garbles again and opens \(Z\) only if the material and the OT labels are the ones that \(\sigma \) determines.

  4. The verifier accepts if and only if \(Z\) is the \(1\)-label \(L_{\mathrm{out}} + \Delta \) of the output node.

4.1 The model

Definition 4.1 Messages of the verifier
✓

A possibly malicious verifier sends arbitrary material, an arbitrary pair of labels to the OT functionality for each input, and an arbitrary seed as its opening. A receiver with choice bits \(x\) gets the first or second label of each pair. The honest verifier with seed \(\sigma \) sends the garbling of \(C\), the pairs \((L_j, L_j + \Delta )\), and \(\sigma \).

Definition 4.2 The prover’s check and the view
✓

The honest prover evaluates the material on the labels it received. After the opening it checks that the material is the garbling of \(C\) with the opened seed and that every OT pair is \((L_j, L_j + \Delta )\). The verifier’s view is the opened label if the check passes, and an abort otherwise. The simulator outputs \(L_{\mathrm{out}} + \Delta \), computed from the opened seed, if the check passes, and an abort otherwise; it does not use the witness.

In the hybrid model the OT functionality gives the verifier nothing, and the commitment functionality gives it only the fact that the prover committed. Its view is therefore the opened label or an abort, a function of its own messages. A randomized verifier is a family of deterministic ones indexed by its coins, so equality of views for every message gives equality of view distributions.

If the check passes, the honest prover’s label is \(\operatorname {lab}_\Delta (L_{\mathrm{out}}, v)\), where \(v\) is the plaintext output on \(w\) and \(L_{\mathrm{out}}\), \(\Delta \) come from the opened seed.

Proof ▶

OT pairs of the form \((L_j, L_j + \Delta )\) hand out the active inputs; apply Theorem 3.8.

4.2 Completeness, zero knowledge, soundness

Theorem 4.4 Completeness
✓
#

If \(C(w) = 1\), the honest prover passes its check and the honest verifier accepts, for every seed.

Proof ▶

The honest messages pass the check by definition, and Lemma 4.3 gives \(Z = L_{\mathrm{out}} + \Delta \).

Theorem 4.5 Perfect zero knowledge against a malicious verifier
✓
#

If \(C(w) = 1\), then for every message of the verifier its view of the honest prover equals the output of the simulator. In particular the view is the same for any two witnesses.

Proof ▶

If the check fails both abort. If it passes, Lemma 4.3 shows that the prover’s label is \(\operatorname {lab}_\Delta (L_{\mathrm{out}}, 1) = L_{\mathrm{out}} + \Delta \), which is the simulator’s output.

Remark 4.6
#

The authenticity notion we use is the static one of [ JKO13 , Definition 2 ] , which Jawurek, Kerschbaum and Orlandi describe as the authenticity of Bellare, Hoang and Rogaway [ BHR12b , Sect. 3.6, game Aut of Fig. 5 ] restricted to their setting: the function has a one-bit output, \(f(x) = 0\), and the adversary must produce the label of the output \(1\). In both the input \(x\) is fixed before the adversary sees the garbled circuit; the adaptive variant, where the input is chosen after, is the subject of Chapter 10. This matches \(\pi _{\mathrm{ZK}}\), where the prover’s choice bits are fixed by \(\mathcal{F}_{\mathrm{COT}}\) before the garbled circuit is sent.

Definition 4.7 Cheating prover and authenticity game
✓

A cheating prover chooses its OT bits \(x\) and computes the label it commits to from the material and the labels it received. Ideal commitment makes this label independent of the later opening. In the authenticity game an adversary receives the material and the active labels of an input \(x\) of its choice, and wins if it outputs the inactive output label \(\operatorname {lab}_\Delta (L_{\mathrm{out}}, 1 - v)\), where \(v\) is the plaintext output on \(x\).

Theorem 4.8 Soundness by reduction to authenticity
✓
#

If no input satisfies \(C\), then for every seed the honest verifier accepts a cheating prover if and only if the prover wins the authenticity game.

Proof ▶

Since the output is \(0\) on every input, the inactive output label is \(L_{\mathrm{out}} + \Delta \), the label the verifier accepts.

A bound on the authenticity advantage, over random seeds and a random hash and for a prover with a bounded number of hash queries, is therefore a bound on the soundness error. Chapters 5 and 6 provide one. The theorem above is for a fixed hash and an arbitrary prover; the formal composition with the bound is Theorem 7.15, which uses Theorem 6.12 directly.

4.3 Without the opening

In the warm-up of Jawurek, Kerschbaum and Orlandi [ JKO13 , Sect. 3 ] the verifier never opens its garbling: the prover sends the output label it computed, and the verifier compares it with the \(1\)-label. This variant is zero knowledge against an honest verifier only. The two statements below make both halves of this precise.

Theorem 4.9 Honest-verifier zero knowledge without opening
✓
#

If \(C(w) = 1\), then against the honest verifier with seed \(\sigma \) the label the prover sends is \(L_{\mathrm{out}} + \Delta \), computed from \(\sigma \). It does not depend on the witness.

Proof ▶

The honest verifier’s messages pass the prover’s check, so Lemma 4.3 applies.

Proposition 4.10 Without the prover’s check, zero knowledge fails
✓

Let \(C\) be the circuit \(x_0 \oplus x_1\), and let \(a \neq 0\). A verifier that sends the honest material of \(C\) but offers the OT pairs \((0, a)\) for input \(0\) and \((0, 0)\) for input \(1\) receives the label \(a\) from a prover with witness \((1, 0)\) and the label \(0\) from a prover with witness \((0, 1)\). Both are witnesses, so a prover that sends its label without checking reveals its first witness bit. Whatever seed the verifier opens, the prover’s check rejects these messages, since the pairs are not of the form \((L_j, L_j + \Delta )\) for a single \(\Delta \), so in the full protocol the view is an abort for both witnesses (Theorem 4.5).

Proof ▶

The output label is the sum of the two received labels: \(a + 0\) for \((1, 0)\), and \(0 + 0\) for \((0, 1)\). For an opened seed with offset \(\Delta \) and input zero-labels \(L_0, L_1\), the check would require \((0, a) = (L_0, L_0 + \Delta )\) and \((0, 0) = (L_1, L_1 + \Delta )\), hence \(\Delta = 0\) and \(a = \Delta = 0\).

This is a simple attack of a malicious verifier on the input phase; the attacks that the opening is meant to prevent are listed in [ JKO13 , Sect. 1 ] .