Zero knowledge from privacy-free garbled circuits

13 Cut-and-choose against a malicious garbler

When the garbling cannot be opened, for instance because it contains a secret of the garbler, a malicious garbler is handled by cut-and-choose: the garbler sends \(N\) circuits, the evaluator opens some of them and evaluates the others. Classical analyses take a majority vote among the evaluated circuits. Lindell [ Lin13 ] observed that if one good evaluated circuit suffices, choosing each circuit independently with a fair coin gives error \(2^{-N}\). The first section contains the combinatorial core; the second connects it with the garbling of Chapter 3.

Definition 13.1 Cheating
✓
#

Let \(B \subseteq \{ 0, \dots , N - 1\} \) be the set of bad circuits and \(E\) the set of evaluated circuits. The garbler cheats if no opened circuit is bad (it is not caught) and no evaluated circuit is good (there is no correct output).

Lemma 13.2
✓
#

The garbler cheats if and only if \(E = B\).

Proof ▶

The first condition says \(B \subseteq E\), the second \(E \subseteq B\).

Theorem 13.3 A fixed number of evaluated circuits
✓

If \(E\) is uniform among the subsets of size \(t \le N\), the garbler cheats with probability at most \(1/\binom {N}{t}\), with equality when \(|B| = t\).

Proof ▶

By Lemma 13.2 at most one \(t\)-subset lets the garbler cheat, and exactly one if \(|B| = t\).

If each circuit is evaluated or opened with an independent fair coin, every garbler cheats with probability exactly \(2^{-N}\).

Proof ▶

\(E\) is uniform among the \(2^N\) subsets, and exactly one of them is \(B\).

Proposition 13.5
✓
#

\(\binom {N}{t} \le 2^N\). Independent coins are never worse than a fixed number of evaluated circuits.

Remark 13.6
#

The gap is small. For \(N = 40\) the best fixed \(t = 20\) gives \(2^{-37.0}\) against \(2^{-40}\), and for \(N = 96\) it gives \(2^{-92.4}\) against \(2^{-96}\). With independent coins the evaluation set may be empty. Here that event is counted inside the bound \(2^{-N}\); Lindell excludes it (the set of check circuits must not be all of them), so his error is \(1/(2^{s} - 1)\), which he rounds to \(2^{-s}\) [ Lin13 , Theorem 4.1 and its footnote 3 ] . The argument that cheating requires every bad circuit to be evaluated and every good one to be checked is in [ Lin13 , Sect. 2 ] .

13.1 Copies of a garbling

The two hypotheses behind Definition 13.1, that an opened bad circuit is caught and that a good evaluated circuit produces the correct output, follow from the garbling of Chapter 3. How the evaluator chooses among the outputs of several evaluated circuits, some of them bad, is not modeled.

Definition 13.7 Copies
✓

A copy consists of a claimed seed, the material and the pair of labels offered for each input. It is good when it passes the check of Definition 4.2: its material is the garbling of \(C\) with its seed and its pairs are \((L_j, L_j + \Delta )\). Opening a copy reveals the seed, so goodness is checked by garbling again.

Lemma 13.8 One good evaluated copy suffices
✓
#

A good copy evaluated on \(x\) outputs the plaintext value \(C(x)\) and the label of that value.

Proof ▶

Theorem 3.8.

For every evaluation set \(E\), an opened copy is bad, or an evaluated copy outputs \(C(x)\) with its label, or \(E\) is exactly the set of bad copies. The last event has probability at most \(1/\binom {N}{t}\) for a uniform \(t\)-subset, and exactly \(2^{-N}\) with independent fair coins.

Proof ▶

Lemma 13.2 with \(B\) the set of bad copies, Lemma 13.8, and Theorems 13.3 and 13.4.

Remark 13.10
#

The evaluator receives its input labels through the offered pairs, as in an oblivious transfer. The consistency of the garbler’s own inputs across the evaluated copies is not modeled.