Zero knowledge from privacy-free garbled circuits

7 A hash commitment instead of the ideal one

In this chapter the commitment functionality of Chapter 4 is replaced by the hash commitment \(c = G(Z, r)\), where \(G \colon V \times R \to D\) is a random oracle and \(r\) is uniform in a finite set \(R\). The oblivious transfer stays ideal. Zero knowledge becomes statistical, with a simulator that programs the oracle, and soundness becomes extraction plus a binding error.

7.1 Oracle runs

Definition 7.1 Runs
✓
#

A query strategy chooses each query from the previous answers. A run queries a point \(p\) if one of its queries is \(p\).

Lemma 7.2 Reprogramming an unqueried point
✓
#

If a run does not query \(p\), reprogramming the oracle at \(p\) changes none of its answers.

Proof ▶

Induction on the number of queries.

7.2 Zero knowledge

Definition 7.3 Malicious verifier and the three games
✓

A malicious verifier runs in three phases with adaptive queries to \(G\): \(q_1\) queries and then the material and the OT pairs; after the commitment, \(q_2\) queries and then the opened seed; after the prover’s last message, \(q_3\) queries and then its output bit. In the real execution the prover commits with \(G(Z_w, r)\), where \(Z_w\) is its output label, and sends \((Z_w, r)\) if the opening passes the check. The simulator commits to a uniform \(c\), and if the opening passes the check it computes \(Z = L_{\mathrm{out}} + \Delta \) from the seed, sends \((Z, r)\) and programs \(G(Z, r) := c\). It does not use the witness. The hybrid uses the real commitment point \(p = (Z_w, r)\), a uniform commitment \(c\), and the oracle \(G[p := c]\) after the commitment.

Lemma 7.4
✓
#

If \(C(w) = 1\), the simulator’s last message is the honest prover’s. In the formalization the hypothesis is that the prover’s check is sound (Lemma 8.6), which for the check of Definition 4.2 follows from \(C(w) = 1\); the same hypothesis is used in Lemma 7.6.

Proof ▶

Lemma 4.3.

If the first phase does not query \(p\), swapping the value \(G(p)\) with \(c\) turns the hybrid into the real execution. The swap is an involution on these pairs \((G, c)\), so the hybrid and the real execution output \(1\) equally often on them.

Proof ▶

By Lemma 7.2 the first phase, hence \(p\), is the same for \(G\) and for \(G[p := c]\); after the swap the real commitment is \(G[p := c](p) = c\).

Lemma 7.6 Hybrid and simulator
✓

The hybrid and the simulator agree unless the second phase, or the third phase after an abort, queries \(p\).

Proof ▶

After a successful opening both use \(G[p := c]\) in the third phase, by Lemma 7.4; elsewhere apply Lemma 7.2.

For every malicious verifier and every witness \(w\) with \(C(w) = 1\), the probabilities that the verifier outputs \(1\) in the real execution and with the simulator differ by at most

\[ \frac{q_1 + q_2 + q_3}{|R|} . \]
Proof ▶

By Lemmas 7.5 and 7.6, the two probabilities differ by at most the probability of the bad events. None of the queries involved depends on \(r\): before the opening the simulator does not use \(r\), and after an abort it never reveals it. So each query hits \(p = (Z_w, r)\) for at most one value of \(r\).

7.3 Soundness

Definition 7.8 Cheating prover and extractor
✓

A cheating prover sees a view of the garbling, makes \(q_1\) queries to \(G\) and commits to \(c\); after the opening it makes \(q_2\) queries and opens a point. The verifier accepts if the opened point has the target label and its value is \(c\). The extractor returns the label of the first first-phase query answered with \(c\). It does not see the opening, so it is an adversary for the authenticity game.

Let \(E\) be a set of oracles, and let \(p(G)\) be a point and \(f(G)\) a value that, for \(G \in E\), do not change when \(G\) is reprogrammed at \(p(G)\). Then \(G \in E\) and \(G(p(G)) = f(G)\) for at most a fraction \(1/|D|\) of the oracles.

Proof ▶

The map \((G, x) \mapsto G[p(G) := x]\) is injective on the pairs with \(G \in E\) and \(G(p(G)) = f(G)\): the image determines \(p(G)\), hence \(G\) off \(p(G)\), and \(G(p(G)) = f(G)\) is determined too.

If the prover is accepted and the extractor does not win, then a fresh first-phase query got the answer of an earlier, different one, or a fresh second-phase query got the answer \(c\), or the opened point was never queried and its value is \(c\). Each of these events has probability at most \(1/|D|\) for a fixed pair, query or point.

Proof ▶

If the opened point was queried in the first phase, the first query answered with \(c\) has a different label, and the first occurrence of the opened point is fresh. Otherwise the first occurrence of the opened point in the second phase, or the point itself, is fresh. In each case apply Lemma 7.9.

Theorem 7.11 Soundness with a hash commitment
✓

The probability that the verifier accepts a cheating prover is at most the probability that the extractor outputs the target label, plus

\[ \frac{q_1^2 + q_2 + 1}{|D|} . \]
Proof ▶

Sum the bounds of Lemma 7.10 over the \(q_1^2\) pairs, the \(q_2\) queries and the opened point.

7.4 End-to-end soundness

The cheating prover receives the material and the active labels of its OT input \(x\), and at each step makes one query to the garbling hash \(H\) and one to the commitment oracle \(G\). A prover that interleaves its queries arbitrarily is of this form after padding. It makes \(n_1\) steps, commits, sees the opened seed, makes \(n_2\) more steps and opens a point. The verifier accepts if the point has the target label \(L_{\mathrm{out}} + \Delta \) and its value is the commitment.

For a fixed \(H\), the prover answers its own \(H\) queries and is a prover of Definition 7.8 for the oracle \(G\), accepted exactly when the paired prover is. For a fixed \(G\), a strategy that answers its own \(G\) queries is an adversary for the oracle \(H\).

Proof ▶

Induction on the number of steps.

Lemma 7.14 The extractor is an authenticity adversary
✓

For a fixed \(G\), the extractor, which replays the first phase and outputs the label of the first \(G\) query answered with the commitment, is an adversary of Theorem 6.12. If \(C\) is unsatisfiable and the extractor returns the target label, this adversary outputs the inactive output label.

Proof ▶

On an unsatisfiable circuit the active output label is \(L_{\mathrm{out}}\), by Theorem 3.8, so the target \(L_{\mathrm{out}} + \Delta \) is the inactive output label.

Theorem 7.15 End-to-end soundness
✓

Let \(|V| \geq 2\), let the seed of the verifier, the hash \(H\) and the commitment oracle \(G\) be uniform, and let \(C\) be unsatisfiable. A cheating prover with \(n_1\) steps before the commitment and \(n_2\) after it is accepted with probability at most

\[ \frac{n_1 + 1}{|V| - 1} + \frac{n_1^2 + n_2 + 1}{|D|} . \]

In the formalization the hypothesis on \(C\) is weaker: \(C(x) = 0\) for the input \(x\) that the prover gives to the OT, which is fixed in advance, with \(x_j = 0\) for \(j \geq k\).

Proof ▶

For fixed \(H\) and seed, Theorem 7.11 and Lemma 7.13 bound acceptance by the extractor’s success plus \((n_1^2 + n_2 + 1)/|D|\). For fixed \(G\), Lemma 7.14 and Theorem 6.12 bound the extractor’s success by \((n_1 + 1)/(|V| - 1)\). Sum over all the randomness.