8 A real oblivious transfer: zero knowledge
In this chapter the ideal OT is replaced by the oblivious transfer of Chou and Orlandi [ CO15 , Sect. 2.1 ] . In their notation the sender sends \(S = yB\), the receiver with choice \(c\) sends \(R = cS + xB\), and the keys are \(H_{(S,R)}(yR - jT)\) with \(T = yS\); below \(A = S\), \(a = y\), \(b = x\) and \(g = B\). Their key hash is seeded with \((S, R)\); ours is an arbitrary function, which is enough for zero knowledge, since the theorem holds for every key hash. Let \(\mathbb {G}\) be a group with a generator \(g\): every element is \(b \cdot g\) for a unique \(b \in \mathbb {Z}_q\). In this chapter \(q\) need not be prime; Chapter 11 assumes it. For each input \(j\) the verifier, as sender, sends \(A = a \cdot g\); the prover, as receiver with choice bit \(w\), sends \(B = b \cdot g + wA\); the verifier sends the two labels masked with the keys \(H_K(a \cdot B)\) and \(H_K(a \cdot (B - A))\), and the prover unmasks the label of \(w\) with \(H_K(b \cdot A)\). When the verifier opens its seed it also opens its OT secrets \(a\), so the prover checks both masked labels, not only its own: a verifier cannot make the prover abort depending on \(w\).
8.1 The oblivious transfer
The receiver’s message is \(B = b \cdot g + wA\), and it unmasks \(e_w - H_K(b \cdot A)\). For the analysis we write \(m_c(A, B) = e_c - H_K(\log _g(B - cA) \cdot A)\), the label of the choice \(c\) unmasked with the key of a receiver whose message is \(B\).
For every \(A\) and \(w\), the map \(b \mapsto b \cdot g + wA\) is a bijection. In particular \(B\) is uniform whatever \(w\) is. This is [ CO15 , Lemma 1 ] .
A bijection followed by a translation.
The receiver obtains \(m_w(A, B)\), a function of the sender’s messages and of \(B\) only. If \(A = a \cdot g\), then \(m_c(A, B) = e_c - H_K(a \cdot (B - cA))\), which the receiver can compute once \(a\) is opened.
\(\log _g(B - wA) = b\), and \(\log _g(X) \cdot (a \cdot g) = a \cdot X\).
8.2 Zero knowledge
If every input node of \(C\) reads an input \(j {\lt} k\), the evaluation depends only on the input wires \(j {\lt} k\).
Induction on the nodes.
A malicious verifier makes \(q_0\) queries to \(G\) and sends the messages \(A\); after the receiver messages \(B\) it makes \(q_1\) queries and sends the material and the masked pairs; the remaining phases are those of Definition 7.3, and the opening also contains the OT secrets. For fixed \(B\) it is a verifier of Chapter 7 whose OT pairs are \((m_0(A, B), m_1(A, B))\). The prover’s check verifies \(A = a \cdot g\), that the material is the garbling of the opened seed, and that both masked labels of every input unmask, with the sender’s keys, to \((L_j, L_j + \Delta )\). It does not use the witness.
If \(C\) reads only the inputs \(j {\lt} k\) and \(C(w) = 1\), then whenever the check passes the honest prover’s label is the \(1\)-label \(L_{\mathrm{out}} + \Delta \) of the opened seed.
For every malicious verifier and every witness \(w\) of a circuit that reads only the inputs \(j {\lt} k\), the probabilities that the verifier outputs \(1\) in the real execution and with the simulator differ by at most
The simulator chooses the receiver messages \(B\) uniformly and runs the simulator of Theorem 7.7.
Receiver privacy is perfect, and zero knowledge holds for every key hash \(H_K\).
8.3 Sender security: the square Diffie–Hellman reduction
The two key points of the sender differ by the square Diffie–Hellman value: \(a \cdot B - a \cdot (B - a \cdot g) = (a a) \cdot g\). This is the observation behind the proof of [ CO15 , Lemma 2 ] .
Linearity of the scalar multiplication.
Let a receiver make \(n\) queries to the key hash, at points \(Q_0, \dots , Q_{n-1}\) that, like its message \(B\), are functions of \(A\) alone: it does not adapt to the answers of the hash or to the masked labels (the general case is Chapter 11). For uniform \(a\), the probability that it queries both key points of an input is at most the sum, over the \(n^2\) pairs of query positions \((i, j)\), of the probability that the solver \(A \mapsto Q_i - Q_j\) computes \((a a) \cdot g\) from \(a \cdot g\); hence at most \(n^2\) times the best square Diffie–Hellman advantage.
If \(Q_i = a \cdot B\) and \(Q_j = a \cdot (B - A)\), Lemma 8.9 gives \(Q_i - Q_j = (a a) \cdot g\).
In a group of odd prime order \(q\) the two problems are equivalent; Bao, Deng and Zhu give randomized reductions in both directions [ BDZ03 , Sect. 2.1 ] . The elementary argument below is not formalized here, and it applies as written only to solvers that always succeed. A computational Diffie–Hellman solver, applied to \((a g, a g)\), gives \(a^2 g\). Conversely, from a square solver \(S\), \(ab \cdot g = 2^{-1} \cdot (S((a+b)g) - S(ag) - S(bg))\), since \((a+b)^2 - a^2 - b^2 = 2ab\). For solvers that succeed only with some probability the three calls must be rerandomized, as in [ BDZ03 , Sect. 2.1 ] .
This is the first of three steps towards soundness with the real OT. The other two are in Chapters 10 and 11: the authenticity bound of Chapter 6 is extended to inputs that the prover chooses adaptively, when it queries the key points after seeing the material, and in the random oracle model a label whose key point is never queried is hidden by a uniform mask.