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

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]$

GNI as a Set-Size Problem

Assume $G_0$ and $G_1$ have the same vertex set $[n]$ ; different vertex counts can be checked directly. Define a set of labeled graphs and automorphisms

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

Here $\text{Aut}(H)$ is the set of vertex permutations preserving $H$ . An isomorphism class contains $n!/|\text{Aut}(H)|$ labeled graphs, and each contributes $|\text{Aut}(H)|$ pairs to $S$ . Thus each isomorphism class contributes exactly $n!$ elements

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

Let $N=2n!$ . It suffices to distinguish $|S|=N$ from $|S|=N/2$ . Encode each pair injectively as an $m$ -bit string, using a fixed polynomial-length encoding with padding if necessary

Membership in $S$ has a polynomial-size certificate. For $x=(H,\pi)$ , Merlin supplies a bit $b$ and an isomorphism $\sigma$ from $G_b$ to $H$ . Arthur checks that $\pi$ and $\sigma$ are permutations, $\pi(H)=H$ , and $\sigma(G_b)=H$

Goldwasser-Sipser Set Lower Bound Protocol

More generally, suppose membership in $S\subseteq\{0,1\}^m$ has an efficient verifier, and the promised cases are $|S|=N$ and $|S|\le N/2$

Choose $k$ such that

2^{k-2}\le N<2^{k-1} \qquad p=\frac{N}{2^k}\in\left[\frac14,\frac12\right)

Let $\mathcal H$ be an efficiently sampleable pairwise independent family from $\{0,1\}^m$ to $\{0,1\}^k$ . For example, $h(u)=Au+c$ over $\mathbb F_2$ works when the binary matrix $A$ and vector $c$ are chosen uniformly

Arthur samples $h\in\mathcal H$ and $y\in\{0,1\}^k$ independently and uniformly, and sends their descriptions to Merlin
Merlin sends an $x\in S$ satisfying $h(x)=y$ , together with a certificate of membership in $S$ . If no such $x$ exists, he cannot provide a valid response
Arthur accepts exactly when the membership certificate is valid and $h(x)=y$

Arthur’s message consists entirely of public randomness. Merlin’s task is to show that the randomly selected hash bucket intersects $S$

Completeness and Soundness

Fix any $y$ and let $E_x$ be the event $h(x)=y$ . Pairwise independence gives

\Pr_h[E_x]=2^{-k} \qquad \Pr_h[E_x\cap E_{x'}]=2^{-2k}\quad(x\ne x')

If $|S|=N$ , inclusion-exclusion through pairs gives the lower bound

\begin{aligned} \Pr_h[\exists x\in S:h(x)=y] &\ge\frac{N}{2^k}-\binom N2\frac1{2^{2k}}\\ &\ge p-\frac{p^2}{2} \ge\frac{3p}{4} \end{aligned}

The honest prover finds a valid response whenever the bucket is nonempty, so this also bounds his acceptance probability from below after averaging over $y$

If $|S|\le N/2$ , the union bound instead gives

\Pr_h[\exists x\in S:h(x)=y] \le\frac{|S|}{2^k}\le\frac p2

No dishonest prover can make Arthur accept an empty bucket, because every response must pass the membership check. The one-shot completeness and soundness probabilities are therefore separated by at least $p/4\ge1/16$

Amplification without More Messages

Run $t$ independent copies in parallel: Arthur sends all challenges in one message, Merlin returns all responses in one message, and Arthur accepts if the fraction of valid responses is at least $5p/8$

Let $Z_i$ indicate that the $i$ -th challenged bucket intersects $S$ . These indicators are independent, since they depend only on the independently sampled challenges. The honest prover achieves every available success, while any prover’s number of accepted responses is at most $\sum_i Z_i$

The threshold is at least $p/8$ away from either promised expectation bound. Hoeffding’s inequality gives

\begin{aligned} \Pr[\text{honest prover rejected}]&\le e^{-tp^2/32}\\ \Pr[\text{dishonest prover accepted}]&\le e^{-tp^2/32} \end{aligned}

Since $p\ge1/4$ , each error is at most $e^{-t/512}$ . Taking $t\ge\lceil512\ln3\rceil$ makes both errors at most $1/3$ , and taking $t=O(\log(1/\varepsilon))$ reduces them to $\varepsilon$

For the graph set above, encodings, hash descriptions and membership certificates all have polynomial length. This gives a two-message public-coin protocol for $\text{GRAPH-NONISO}$ with bounded completeness error, establishing $\text{GRAPH-NONISO}\in\text{AM}$

More facts

$\text{IP} = \text{PSPACE}$
$\text{IP}[\ell] = \text{AM}[\ell] = \text{AM}$ for all constant $\ell \geq 2$
Allowing bounded completeness error leaves each of the classes $\text{AM}$ , $\text{MA}$ and $\text{IP}$ unchanged

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 国际许可协议，转载请注明出处。