# 「Cryptography-MIT6875」: Lecture 15

**Topics Covered: **

- Sequential vs Parallel Repetition: reduce soundness error
- Proof of Knowledge
- PoK of DLOG

- Non-Interactive ZK(NIZK)
- NIZK in The Random Oracle Model
- NIZK for 3COL

- NIZK in The Common Random String Model (Lecture 16)

- NIZK in The Random Oracle Model

# Recap

Recap **NP Proofs.**

Give NP Proofs for the NP-complete problem of __graph 3-coloring.__

- Prover $P$: has a
__witness__, the 3-coloring of $G$. - $P$ gives the proof,
__the solution to 3-coloring__of $G$, to $V$. - Verifier $V$ checks:
- only 3 colors are used
- any two vertices connected by an edge are colored differently.

The verify learned __the graph $G$ is 3-colorable and the 3-coloring solution.__

So NP proofs reveal too much information.

With **Zero-knowledge (Interactive) Proofs**, the verifier can only learns the graph $G$ is 3-colorable without knowing the solution.

- Prover $P$:
__permute__the colors__commit__to each color- send all the commitments to the verifier.

- Verifier $V$: pick a random edge
- Prover $P$: open the vertices of the edge.
- Verifier $V$ checks the openings & the colorings of two vertices are different.

Besides, we proved the 3COL Protocol is completeness, soundness and zero-knowledge in previous blog.

**Completeness**: For every $G\in 3COL$, $V$ accepts $P$’s proof.**Soundness**: For every $G\notin 3COL$ and any cheating $P^*$, $V$ rejects $P^*$’s proof with probability $\ge 1-neg(n)$.**Zero-knowledge**: For every cheating $V^*$, there is a PPT simulator $S$ such that for every $G\in 3COL$, $S$ simulates the view of $V^*$.

# Sequential vs Parallel Repetition

The 3COL protocol __has a large soundness error__ of $1-1/|E|$, the probability that $V$ accepts even though $G\notin 3COL$.

## Reducing Soundness Error

But it brings about the **problem** that __it costs a lot of rounds.__

An alternative way is parallel repetition.

Note: Preserving the ZK property in general means that it is ZK __against malicious verifier.__

This theorem tells that **some protocols in parallel repetition is not zero-knowledge** against malicious verifier.

And the following theorem tells us that __the parallel repetition of 3COL protocol is not zero-knowledge__ if we run it in many and many times in parallel.

Fortunately, we have zero-knowledge protocols **in const rounds** with __exponentially small soundness error__, rather in a million rounds.

# Proofs of Knowledge

So far, we focus on the **decision problem**: $y\in \mathcal{L}$ or $y\notin \mathcal{L}$.

(e.g. $y$ is quadratic residue $\mod N$ or it is not.)

Here is a **different scenario** that __Alice has the knowledge__, the discrete log of $y$ assuming $g$ is a generator.

And Alice wants to __convince Bob the discrete log of $y$ always exists.__

In this scenario the **prover wants to convince the verifier** that __she knows a solution to a problem__, e.g. that she knows the discrete log of $y$.

It is difficult to formulate it as the decision problem.

It is **Proof of Knowledge.**

Likewise, we can define the completeness, soundness and zero-knowledge.

**Completeness**: When Alice and Bob run the protocol where Alice has input $x$, Bob outputs accept.**Soundness**: How to define soundness that Alice dose not have the knowledge ?

It is difficult to**formulate the leak of knowledge.****Zero-knowledge**: There is a simulator that, given only $y$, outputs a view of Bob that is indistinguishable from his view in an interaction with Alice.

## Extractor

The **main idea of Goldreich** is that __if Alice knows $x$, there must be a way to “extract it from her”.__

It’s not about putting diodes on her brain. [*diode 二极管]

It’s sort of talking to Alice.

The extractor is indeed the **expected ppt adversary.**

We will not dig into the definition but give an example of PoK.

## ZK Proof of Knowledge of Discrete Log.

The protocol is as follows.

**ZK Proof of Knowledge of DLOG:**

- Prover: Pick a random $r$ and send $z=g^r$ to Verifier.
- Verifier: Pick a random challenge $c$
- Prover: Answer the challenge
- If $c=0$: send $s=r$
- If $c=1$: send $s=r+x$

- Verifier: Accept iff $g^s=z\cdot y^c$.

The above protocol is completeness, soundness and zero-knowledge.

The completeness and zero-knowledge is well proven.

*Completeness: *

- If the prover has the discrete log of $y$, the verifier accepts with probability 1.
- $g^s=g^{r+cx}=g^r\cdot (g^{x})^c=z\cdot y^c$

*Zero-knowledge: *

- The real view of $V^*$ is $\texttt{view}_{V^*}=(z,c,s)$
- The simulator works as follows
- Generate $z=g^s/y^c$ for a random $s$ and a random $c$.
- Feed $z$ to verifier and get the challenge $c^*=V^*(z)$.
- If $c^*=c$, output as the simulated transcript.
- If $c^*\ne c$, back to step 1 and repeat.

- The simulated view is
**identical**to the view in real execution.

*Soundness: *

The

**key**is to__construct an extractor by the contradiction.__If the protocol is of

**soundness**, the cheating prover $P^*$ can convince the verifier with probability $1/2$.Assume for the

**contradiction**that $P^*$__convinces the verifier with probability $\ge 1/2+1/poly$.__Then the prover $P^*$

__should prepare for both challenges.__It’s easy to

**extract**the discrete log of $y$ form $P^*$.- Runs $P^*$ with $c=0$ and gets $s_0$.
__Rewind__$P^*$ to the first message.- Runs $P^*$ with $c=1$ and gets $s_1$.

- By
**contradiction**, $g^{s_0}=z$ and $g^{s_1}=zy$ with probability $1/poly$. - That is $g^{s_1-s_0}=y$ w.p. $1/poly$.
- So $s_1-s_0$ is the discrete log of $y$ w.p. $1/poly$.

It’s known as Schnorr proof, or Schnorr Signature.

# Non-Interactive ZK

Let’s proceed to the next topic.

Can we make proofs **non-interactive** again ?

The **advantages** of **Non-Interactive ZK (NIZK)**:

- $V$
__dose not need to be online__during the proof process. - Proofs are
__not ephemeral__, can stay into the future.[*ephemeral 短暂的]

## NIZK is Impossible

Firstly, we claim that **NIZK is impossible.**

Suppose there were an __NIZK proof system for 3COL.__

The NIZK proof is of completeness and zero-knowledge, but **NOT sound.**

**Proof:**

**Completeness**: When $G$ is in 3COL, $V$ accepts the proof $\pi$.**Zero Knowledge**: PPT**simulator**$S$,__given only G in 3COL__, produces an indistinguishable proof $\tilde{\pi}$.

In particular, $V$ accepts $\tilde{\pi}$.Imagine running the

**Simulator**$S$ on a $\underline{G\notin 3COL}$.

It produces a proof $\tilde{\pi}$ which the verifier still accepts!Because $S$ and $V$ are PPT.

They together**cannot tell if the input graph is 3COL**or not without the witness.Therefore, $S$ is indeed

**a cheating prover!**

It__can produce a proof for a $G\notin 3COL$ that the verifier nevertheless accepts.__Ergo, the proof system is

**NOT SOUND.**

## Two Roads to NIZK

But we can __achieve NIZK under some models.__

There are two roads to NIZK.

- Random Oracle Model & Fiat-Shamir Transform
- Common Random String Model

## NIZK: Random Oracle Model

As discussed before **randomness of verifier** for ZK proofs is necessary.

Otherwise, it is not interactive.

More discussion about randomness.

Give an example in **ZK proof of knowledge for discrete log.**

The protocol is **not sound** if $P^*$ __knows the random challenge $c$ beforehand.__

If $P^*$ knows $c=0$ beforehand, it’s useless.

If $P^*$ knows $c=1$ beforehand,

- Send $z=g^s/y$ for random $s$.
- Send $s$.

### NIZK for 3COL

Consider NIZK Proof for 3COL.

Start with the **parallel repetition of 3COL protocol.**

It is complete, has exponentially small soundness error, and is hones-verifier ZK.

Similarly, the randomness is necessary.

Otherwise, the cheating prover can make up message $a$, $z$ beforehand.

However, the protocol can be **non-interactive in the random oracle model.**

But in the **Random Oracle Heuristic world**, the only way to compute $H$, virtually a black box, is by __calling the oracle.__

** Fiat and Shamir (1986): **

Let $c=H(a)$. Now the prover **can compute the challenge herself!**

It is potentially harmful for soundness.

But in random oracle model for $H$, it can **prove soundness.**

「Cryptography-MIT6875」: Lecture 15