TCS: Interactive Proofs and Zero-Knowledge

Interactive Proofs and Zero-Knowledge

Interactive Proofs

Interactive Proof Verification

Interactive proof system allows prover $P$ and verifier $V$ to exchange messages before stopping. We restrict $V$ to be PPT while the probabilitic is necessary otherwise this system is $\text{NP}$ as $P$ is stronger than $V$ .

Problem $A$ is in $\text{IP}$ if there is a pair of interactive algorithms $(P, V)$ , with $V$ running in probabilistic polynomial time in the length of input $x$ , such that

(Completeness). If $x\in A$ , then $P(\langle P, V\rangle(x) = 1) = 1$ .
(Soundness). If $x\notin A$ , then for any possibly dishonest $P^{*}$ , we have $P(\langle P, V\rangle(x) = 1) \leq \frac{1}{2}$ .
$(P, V)$ satisfying above is called a proof system for $A$ . We say $A\in\text{IP}[\ell]$ if it has a proof system using $\ell = \ell(|x|)$ times of message exchanges (number of messages, not rounds!).

We have that: $\text{BPP} \subseteq \text{IP}[1]$

Concretely, we consider two problem $\text{GRAPH-ISO}$ (图同构问题) and $\text{GRAPH-NONISO}$ . Easily, $\text{GRAPH-ISO}\in \text{NP}$ since we can choose the isomorphic permutation $\pi$ as witness. Besides, we have $\text{GRAPH-NONISO}\in \text{IP}$ .

The GNI protocol is:

$V$ samples a random $b\in\{0, 1\}$ and a random permutation $\pi$ , send $\pi(G_{b})$ to $P$
$P$ returns an bit $b'$ to $V$ and $V$ accepts iff $b' = b$

As $P$ is all-know, it must have the ability to distinguish $b$ if $G_{0} \not\sim G_{1}$ . But it can just guess arbitarily if they are isomorphic.

Merlin-Arthur (Public-Coin) Protocols (Skip)

A Merlin-Arthur protocol is an interactive proof system where the verifier (Arthur) messages are public random coin flips.

A really simple $V$ !

Let $\text{AM}[\ell]$ to be the Merlin-Arthur protocol with $\ell(|x|)$ messages. Consider $\text{MA} = \text{AM}[1]$ and $\text{AM} = \text{AM}[2]$

Though it seems week, but we have:

Goldwasser-Sipser theorem: $\forall \ell$ , $\text{IP}[\ell]\subseteq\text{AM}[\ell + 2]$

Define a set:

S = \{(H, \pi) \,|\, \pi\in\text{Aut}(H), H\sim G_{0} \text{ or } H\sim G_{1} \}

$\text{Aut}(H)$ represents the automorphism permutation multiplicity. So we have:

|S| = \begin{cases} n! & G_{0} \sim G_{1} \\ 2n! & \text{otherwise} \end{cases}

So the $\text{GRAPH-NONISO}$ is transformed into confirming $|S|$
Let $\mathcal{H}$ be a pairwise independent hash family with $U = \{0, 1\}^{m}$ and $R = \{0, 1\}^{k}$ where $k < m$ .
Then the protocol is:

TODO

More facts

$\text{IP} = \text{PSPACE}$
$\text{IP}[\ell] = \text{AM}[\ell] = \text{AM}$ for all constant $\ell \geq 2$
$\text{AM} = \text{MA} = \text{IP}$ if we allow completeness error

Coin Flipping and Commitment

We want a protocol where Alice and Bob talk to each other and then decide some important thing on the outcome $R(a, b)$ of the coin flip and it makes sure that the result is not biased even if one of them is cheating (malicious). This means:

\begin{align*} P(R = 0) &\leq \frac{1}{2} + \text{negl}(n) \\ P(R = 1) &\leq \frac{1}{2} + \text{negl}(n) \end{align*}

So we need something to hide $a$ which filped by Alice to Bob to avoid bias.

Bit Commitment

The commitment scheme is a protocol consisting of the commit phase and reveal phase.

A PPT protocol $\text{Com}$ is a (computationally hiding and statistically binding) commitment scheme if:

Hiding: $\forall\, x_{0}\neq x_{1}$ , $\text{Com}(x_{0})\approx_{c}\text{Com}(x_{1})$ .
Binding: The probability that Alice can open $\text{Com}(x_{0})$ to $x_{1}$ with $x_{1}\neq x_{0}$ is negligible.

In this $\approx_{c}$ means that one cannot distinguish both is polynomial time.

Intuitively, this definition means Bob(recevier) can hardly verify $x_{0}$ or $x_{1}$ and Alice(sender) can almost always verify them.

Coin Flipping from Bit Commitment

The safe protocol is as follows:

Alice send $\text{Com}(a)$ to Bob with a random $a$
Bob sends $b$ to Alice
Alice opens $\text{Com}(a)$
Set $R = a \oplus b$

Bit Commitment From PRG (Naor’s Construction)

Assume $G$ is a PRG with $\ell(n) = 3n$

In the commit phase:

The receiver sends $x\in\{0, 1\}^{3n}$ ;
The sender samples $m\in\{0, 1\}$ , $z\in\{0, 1\}^{n}$ and sends $y = G(z)\oplus x^{m}$ ;

In the reveal phase:

The sender sends $z$ and $m$ .

Zero-Knowledge Proofs

Definition at first is as follows, in which $\text{view}$ contains the transcript of the interaction(all messages and their probabilities) and local information.

An interactive protocol $(P, V)$ is perfect (statistical or computational) ZK for $A$ if, $\forall$ PPT $V^{*}$ , there exists a PPT simulator $S$ such that $\forall\, x\in A$ , the following two distributions are the same:

$\text{view}_{V^{*}}\langle P, V^{*}\rangle(x)$
$S(x)$

We have $\text{GRAPH-ISO} \in \text{PZK}$ . The protocol is as follows:

$P$ samples a random permutation $\pi$ and sends $G = \pi(G_{0})$ to $V$
$V$ samples a random $b\in\{0, 1\}$ and sends it to $P$
$P$ responds with a proof that $G\sim G_{b}$ with the permutation $\pi\circ\sigma^{b}$

simulator and rewind

To prove this protocol is what we want, we need to prove its completeness, soundness and ZK. The first two are easy to argue, the ZK need a simulator and we generates it as follows:

Choose $a$ uniformly at random.
Sample a random permutation $\pi$ and compute $G = \pi(G_{a})$ .
Randomly sample $r$ and simulate $V^{*}$ with random tape content $r$ .
If $V^{*}$ sends $b = a$ , outputs $(G, \pi)$ as the message and the random tape $r$ as the internal randomness of $V^{*}$ .
If $V^{*}$ sends $b\neq a$ , rewind and start from the beginning.

ZK Proofs for NP

We have:

(Goldreich-Micali-Wigderson). If statistically binding commitments exist, then there exists a zero-knowledge proof system for $\text{3-COLORING}$

The protocol is:

$P$ samples random permutation $\pi: \{0, 1, 2\}\to \{0, 1, 2\}$ .
$P$ sends $\{\text{Com}(\pi(\phi(v))) \,|\, v\in V\}$
$V$ samples a random edge $(u, v)\gets E$ and sends it to $P$
$P$ opens the commitment $c_{u}$ and $c_{v}$
$V$ checks if $\pi(\phi(u)), \pi(\phi(v))\in\{0, 1, 2\}$ and $\pi(\phi(u)) \neq \pi(\phi(v))$

In this, $\phi$ is a coloring scheme

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

TCS-Lecture-D

Interactive Proofs and Zero-Knowledge