Sequentially composing ZK (cont.) and black box simulated ZK

Cryptography 2019-02-19

The materials in this post are mostly from the talk by Alon Rosen in the BIU school, but some proofs are written by myself. So feel free to contact me in case there are any typos or mistakes.

The protocol from yesterday

Recall the protocol from yesterday. (Prof. Rosen cited as [GMR’85])

Given $x$ as common input to $(P(x),V(x)):$

:
sample .
- If $b = 0$ send $z \gets y^2$ to $P$ ;
- If $b = 1$ send $z \gets xy^2$ to $P$ .
:
- If $z \in QR_{N}$ send $b' = 0$ to $V$ ;
- Otherwise send $b' = 1$ to $V$ .
$V$ accepts iff $b = b'$ .

The argument for ZK was invalid. That is due to the fact that we need to show that for any verifier $V$ (including malicious ones which might deviate from the protocol) there is a simulator for it. But we have only shown that for an honest verifier we can simulate the view.

Non-ZK-ness of the protocol

The protocol turns out to be only honest verifier zero knowledge (HVZK).

To see why, notice that a cheating verifier can choose $b$ on purpose, and not to sample $y$ at all. He can decide to send $b = 0$ and choose $z$ to be some specific number on which he need to decide whether $z \in QR_\mathbb{N}$ . In this case, the returned bit $b'$ signifies the answer.

This might be adversarially utilized when composing protocols. For example, one can imagine that in a certain protocol $\pi$ some party $P$ needs to prove that it can decide $QR_\mathbb{N}$ . Then when the protocols are running together, this particular party may use the other protocol to cheat (though contrived, there are real protocols (with computational simulation) that break down when running in parallel, one is mentioned in the talk Alon Rosen: Lower Bounds and Limitations on Zero Knowledge in the school).

ZK with auxiliary input

A better definition for ZK that enables sequential composition is as follows.

(ZK with auxilary input) An IP $(P,V)$ is said to be zero-knowledge with auxiliary input if for any PPT verifier $V^*$ there exists a PPT simulator $S$ such that,

$\forall x \in L, z \in \{0,1\}^*, S(x,z) \equiv$ View $(P(x), V(x,z))$ .

Where $z$ represents the context (auxiliary input) and the $\equiv$ corresponds to perfect (statistical, computational) indistinguishablility respectively.

Proving closure under sequential composition

Using the previous definition, one can prove that ZK is closed under sequential composition.

Suppose $(P,V)$ is ZK with auxiliary input, then $(P, V)^t$ where the protocol is sequentially executed $t$ times, is also ZK with auxiliary input.

This can be proven by induction.

Suppose the claim is true for $t = n$ . Then there is a simulator $S_n$ for the view produced by $(P, V)^n$ . To simulate $(P,V)^{n + 1}$ , on input $(x,z)$ , we first run $S(x,z)$ to obtain a view $\mathcal{v}$ for the first execution. Then we feed this view into the auxiliary input of $S_n$ , i.e. we run $S_n(x, \mathcal{v})$ to obtain $v_n$ . Now $(v, v_n) \equiv (v, (P, V(x, v))^n) \equiv (P, V)^{n + 1})$ by perfect simulation of $S_n$ and by the fact that the state that is passed from the first execution to the second distributes exactly as $v$ , by perfect simulation of $S$ . Therefore the above procedure describes a perfect simulator for $(P, V)^{n + 1}$ .

The black box simulation barrier

Wow the protocol by Barak using non-black-box simulation is really amazing and I am still trying to understand the constructions. I will definitely try to explain the protocols in the following posts if I have time.

But, why would we need the non-black-box simulation in the very first place?

Here I will describe the so-called black box simulation barrier, which seems to be first published by Goldreich and Krawczyk in 1990 (Paper).

The theorem goes as follows.

The following condition hold for an IP $(P, V)$ for a language L if and only if L $\in$ BPP.

It has constant-round, i.e. the number of rounds of exchanging messages is bounded by a constant;
It is Arthur-Merlin, i.e. the verifier does not have hidden randomness from the prover;
It admits black-box simulation. That is to say, for any $V^*$ , there is a simulator $S^{V^*}$ which is an oracle machine that treats $V^*$ as a black-box, and that $S^{V^*}(x)$ produces a simulated view that is computationally indistinguishable from a real execution by $(P, V^*)(x)$ .

A trivial case

The proof is a bit complicated. Here let us consider a very much simplied situation (or because the author is very sleepy).

Let $(P,V)$ be an ZK interactive proof system for L in which the protocol consists of a single message $y$ from $P$ to $V$ . Then L $\in$ BPP.

In the following by $V(r, y)$ we mean the verifier is given random coins $r$ and received message $y$ from the prover. Let $S$ be the simulator for $V$ , then the following is a PPT algorithm for L.

On input $x$ :

Let $(r, y) \gets S(x)$ ;
Accept iff $V(r,y)$ accepts.

If $x \notin$ L then $\Pr_s[V(r,y) = 1] \le \frac{1}{3}$ because otherwise, the prover $P^*$ that always sends $y$ violates soundness.

If $x \in$ L, suppose $\Pr_s[V(r,y) = 1] < \frac{2}{3}$ . Then we can build a distinguisher $D$ for attacking $S$ which runs step 2 of the above procedure. When given simulated views, $D$ output 1 with probability less than $\frac{2}{3}$ , but when given real views in the protocol, the distinguisher outputs 1 with probability 1 due to completeness. Therefore $\Pr_s[V(r,y) = 1] \ge \frac{2}{3}$ .

Hence L $\in$ BPP.

Reference:

Alon Rosen: Introduction to Zero Knowledge, talk & slides. (Day 1 of BIU school)

Alon Rosen: Lower Bounds and Limitations on Zero Knowledge. (Day 2 of BIU school)

Oded Goldreich, Hugo Krawczyk: On the Composition of Zero-Knowledge Proof Systems.

official site of BIU Winter School.