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
A query strategy chooses each query from the previous answers. A run queries a point \(p\) if one of its queries is \(p\).
If a run does not query \(p\), reprogramming the oracle at \(p\) changes none of its answers.
Induction on the number of queries.
7.2 Zero knowledge
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 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.
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\).
The hybrid and the simulator agree unless the second phase, or the third phase after an abort, queries \(p\).
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
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
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.
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.
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.
The probability that the verifier accepts a cheating prover is at most the probability that the extractor outputs the target label, plus
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\).
Induction on the number of steps.
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.
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.
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
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\).