# 「Cryptography-MIT6875」: Lecture 13

**Topics Covered: **

- Zero knowledge, definitions and example
- ZK Proof for QR Language.
- honest-verifier ZK
- malicious-verifier ZK

In the following lectures, we will introduce **much more than communicating securely.**

- Complex
**Interactions**: proofs, computations, games. - Complex
**Adversaries**: Alice or Bob, adaptively chosen. - Complex
**Properties**: Correctness, Privacy, Fairness. - Many
**Parties**: this class, MIT, the Internet.

Today’s gist is the proof.

It’s very different from the **classic proofs.**

# NP Proofs

In classic proofs, **prover** __writes down a string(proof) and verifier checks.__

Little formally, it can be formalized as below.

- There is a
**claim**(or theorem), e.g. 15627 is a prime. - There are
**two parties**, a prover and a verifier.- The
**prover**__provide a proof to the verifier.__ - The
**verifier**can__accept or reject the proof.__

- The

## NP Language Definition

The proofs of $\mathcal{NP}$ are efficiently verifiable proofs.

The **prover** has __no computational bounce__ and needs to work hard to produce a proof.

But the **verifier** can efficiently __verify it in polynomial time.__

The $\mathcal{NP}$ proof of a theorem is actually a set of strings which can be written down.

**Definition of Language Procedure: **

A language/decision procedure $\mathcal{L}$ is simply **a set of strings**. So $\mathcal{L}\subseteq \{0,1\}^*$.

The **language** is actually __a set of strings which represent the true statements.__

Look at some examples.

## e.g.1 N=PQ Language

Theorem: $N$ is a produce of two prime numbers.

Prover: Give the

**two prime factors as proof**. $=(P,Q)$.Verifier: Accept if and only if $N=PQ$ and $P,Q$ are primes.

**After interaction**, Bob, the**Verifier knows**- $N$ is a produce of two primes.
**Also**, the**two factors**of $N$.

## e.g.2 QR Language

Theorem: $y$ is a quadratic residue $\mod N$ where $N=PQ$.

Prover: Give

**the square root as proof**. $=x$Verifier: Accept if and only if $y=x^2\mod N$.

**After interaction**, Bob, the Verifier knows- $y$ is a quadratic residue $\mod N$.
- Also,
**the square root**of $y$.

## e.g.3 Graph Isomorphism Language

Theorem: Graphs $G_0$ and $G_1$ are isomorphic.

Prover: Give

**the map of nodes as proof**. $=\pi$Verifier: Accept iff the edge connectivity is retained after mapping.

**After interaction**, Bob, the**Verifier knows**- $G_0$ and $G_1$ are isomorphic.
- Also,
**the isomorphism.**

## e.g.4 Hamiltonian Cycle Language

Theorem: Graph $G$ has a Hamiltonian cycle.

Prover: Give

**the Hamiltonian circle as proof.**Verifier: Accept iff every edge exists.

**After interaction**, Bob, the**Verifier knows**- $G$ has a Hamiltonian cycle.
- Also,
**the Hamiltonian cycle**itself.

Every one of the above can be __reduced to $\mathcal{NP}$-Complete Problem.__

Besides, every proof above **leaks some valuable information** more than the proof itself.

Is there any other way that the prover only tells the verifier whether $y$ is quadratic residue **without telling the square root**?(Example 2)

The point is that we want to reveal the minimal information.

# Interactive Proofs

Before proceeding to Zero Knowledge Proof, let’s start with Interactive Proofs.

Interactive Proof is not a monologue but a **dialogue**.

There are two necessary new ingredients in Interactive Proofs.

**Two (Necessary) New Ingredients: **

**Interaction**: Rather than passively reading the proof, the**verifier**__engages in a conversation with the prover.__**Randomness**: The**verifier**__is randomized__and can make a mistake with a (exponentially small) probability.

## Idea

Let’s start with **solving the Rubik’s Cube.**

**Theorem**: There is an $\le k$ move solution to this cube.

The **idea** is __split the process of resolving in half.__

**Interactive Proof: **

Prover: sends a “random” cube.

Verify: sends a Challenge (0 or 1)

Prover

If Challenge 0: show $k/2$ moves

If Challenge 1: show $k/2$ moves

The **point** is that if the __prover can do both challenges consistently__ (or many and many times), then there exists $k$ moves.

We do not take it seriously since there are many flaws in the above protocol.

We just get some inspiration from it.

## Definition of IP

The **Interactive Proofs** for a Language $\mathcal{L}$ is as follows.

- There is a claim or a theorem.
- Two parties are interacting for a language $\mathcal{L}$.
- Prover:
**Computational Unbounded** - Verifier:
**Probabilistic Polynomial-time**

- Prover:

**Completeness** is a property of the protocol __when $P$ and $V$ are both honest.__

**Soundness** is a property of the protocol __when $P$ is dishonest.__

So soundness is also a property of the verifier.

The **verifier has to be sound** because it has to work against an arbitrary $P$.

## IP for QR Language

We can give the interactive proof for QR.

$\mathcal{L}=\{(N,y): y \textrm{ is a quadratic residue}\mod N\}$**Interactive Proof: **

- Prover: send a random square $s$
- Verifier: flip a coin $b$
**(randomness)** - Prover
- If $b=0$, send $z=r$
- If $b=1$, send $z=rx$ where $y=x^2 \mod N$.

- Verifier: Accept iff $z^2=sy^b \mod N$.

**Completeness: **

*Claim: *

If $(N,y)\in \mathcal{L}$, then the verifier accepts the proof with probability 1.

*Proof: *

- $z^2=(rx^b)^2=r^2(x^2)^b=sy^b$.
- So the verifier’s check passes and he accepts.

**Soundness: **

*Claim: *

If $(N,y)\notin \mathcal{L}$, then for **every cheating prover** $P^*$, the verifier accepts **with probability at most** $1/2$.

*Proof: *

The

**challenge is random**and the**randomness is over the coin.**If the probability

**equals**$1/2$, it means that the cheating prover $P^*$__can only solve one of the challenges, Challenge 0.__**Suppose**the verifier accepts with probability $\ge1/2$.Then,

__there is__some $s\in \mathbb{Z}_N^*$, the**prover**is able to__pass both challenges.__So the prover can produce both $z_0$ and $z_1$ beforehand.

- $z_0:z_0^2=s\mod N$
- $z_1:z_1^2=sy\mod N$

This means $(z_1/z_0)^2=y\mod N$, which tells us that $(N,y)\in \mathcal{L}$. (Contradiction)

Moreover, we can make the probability of soundness **negligible**.

Just **repeat the procedure sequentially $\lambda$ times. **

*Claim: *

If $(N,y)\notin \mathcal{L}$, then for every cheating prover $P^*$, the verifier accepts **with probability at most** $(\frac{1}{2})^\lambda$.

# Zero Knowledge Proof

Actually, the interactive proof for QR language is Zero-Knowledge.

But what dose zero-knowledge mean?

- After the interaction, $V$
**knows:**- The theorem is true; and
**A view**of the interaction (=**transcript + coins**of $V$)

The transcript is all the messages going back and forth.

- $P$ gives
**zero knowledge**to $V$:

When the theorem is true, the view**gives $V$ nothing**that he couldn’t have obtained on his own without interacting with $P$.- That means the view is not going to
**give any new knowledge**that $V$ couldn’t have it on his own. - We can consider the
**knowledge**as__some stuff that we cannot generate in probabilistic poly-time on our own.__

If we are given something we can generate by ourselves, it’s zero-knowledge.

- That means the view is not going to

$(P,V)$ is zero-knowledge if $V$ can **generate his view** of the interaction all by himself in probabilistic polynomial time.

$(P,V)$ is zero-knowledge if $V$ can **“simulate” his view** of the interaction all by himself in probabilistic polynomial time.

We formalize it by the **Simulation Paradigm.**

## The Simulation Paradigm

There are two **indistinguishable distributions.**

- The real view of the interaction: $\texttt{view}_V(P,V)=(s,b,z$).

It consists of- Transcript: $(s,b,z)$
- Coins: $b$

- The simulated view: $\texttt{sim}_S(s,b,z)$

We can give the zero-knowledge definition by the simulation paradigm.

## Zero-knowledge Definition (for honest V)

$(P,V)$ is **zero-knowledge interactive protocol** if it is complete, sound and zero-knowledge.

**Completeness**is a property of the protocol__when $P$ and $V$ are both honest.__**Soundness**is a property of the protocol__when $P$ is dishonest.__- So it’s also a property of the verifier.

The verifier has to be sound because it has to work against an arbitrary $P$.

- So it’s also a property of the verifier.
**Zero-knowledge**is a property__against the verifier.__

Actually, we give the definition of zero-knowledge **against a honest verifier.**

We’ll refine it for any arbitrary verifier in the next section.

There are some analogous definitions of **honest-verifier zero-knowledge.**

## QR Protocol is (honest-V) ZK

**Claim:**

The QR protocol is (honest-verifier) **perfect zero knowledge.**

**Simulator S works as follows: **

- First pick a random bit $b$.
- Pick a random $z\in \mathbb{Z}_N^*$.
- Compute $s=z^2/y^b$.
- Output $(s,b,z)$.

The **simulator** can sort of __permute things which is offline.__

And the **verifier** is __online in the real world.__

**Lemma: **

The simulated transcript is **identically** distributed as the real transcript in the interaction $(P,V)$.

**Proof of Lemma: **

- The thing we need to
**prove**is that__the distribution of every component in the transcript is identical.__ - Real transcript: $\texttt{view}_{V}(P,V)=(s,b,z) $
- $s$ is square as same as random
- $b$ is random coin(since the honest verifier)
- $z=\sqrt{sy^b}$ is random

- Simulated transcript: $\texttt{sim}_S((N,y),1^\lambda)=(s,b,z) $
- $s=z^2/y^b$ is square as same as random ($(N,y)\in \mathcal{L}$ so $y$ is square)

Besides, the distribution of $s$ hides $b$ perfectly. - $b$ is random
- $z$ is random

- $s=z^2/y^b$ is square as same as random ($(N,y)\in \mathcal{L}$ so $y$ is square)
- QED

Actually we only prove the QR protocol is **honest-verifier Zero-knowledge.**

When the theorem is true, the view gives the **honest verifier** $V$ nothing that $V$ couldn’t have it on his own.

What if $V$ is **NOT honest** ?

## Zero-knowledge Definition (for malicious V)

In real world, the verifier could be **malicious** that he can do anything he wants.

We hope the view also gives zero-knowledge to the malicious verifier $V^*$.

The definition for honest verifier undermines the definition for malicious verifier.

Refine the definitions **for malicious verifier** $V^*$.

## QR Protocol is (malicious-V) ZK

The ZK proof for QR language we gave above is actually honest-verifier zero-knowledge.

In this section, we consider the **malicious-verifier zero-knowledge** for QR Protocol.

Recap the zero-knowledge proof for QR Language.

$\mathcal{L}=\{(N,y):y \textrm{ is a quadratic residue }\mod N\}$.- The view of a malicious verifier $V^*$ is $\texttt{view}_{V^*}(P,V^*)=(s,b,z)$.
- When $V^*$ obtains the $s$, the
**only power**that $V^*$ has is to__choose the $b$ in a bizarre fashion rather than random.__ - So the distribution of $b$ is
**not random.** - Let $b=V^*(s)$ denote the bizarre thing generated by $V^*$ after receiving $s$.

- When $V^*$ obtains the $s$, the
- The simulator $S$ only gets an instance of $(N,y)$ and wants to generate $\texttt{sim}_S((N,y),1^\lambda)=(s,b,z)$.

In order to produce the same distribution of $b$, the **simulator** $S$ __needs to interact with the malicious verifier $V^*$.__

It’s sort of a prover which also needs to interact with the verifier.

The only **distinction** is that the **prover** $P$ has to __be online to answer the challenge__ from the verifier $V^*$ and the **simulator** $S$ __can be offline with the goal of generating the view.__

**Claim:**

The QR protocol is (malicious-verifier) **perfect zero knowledge.**

**Simulator S works as follows:**

- First set $s=z^2/y^b$ for a random $z$ and a random $b$ and “feed” $s$ to $V^*$
- Let $b'=V^*(s)$. (generated by $V^*$ in any bizarre fashion rather than random)
- If $b=b’$, output $(s,b,z)$ and stop.
- Otherwise, go back to step 1 and repeat. (also called “
**rewinding**”)

**Lemma: **

- $S$ runs in expected polynomial-time.
- When $S$ outputs a view, it is
**identical**to the view of $V^*$ in a real execution.

Lemma 1 is well proven.

The probability of terminating in one iteration is $1/2$ since $b$ is random.

So the expected iterations is $2$.

**Proof of Lemma 2:**

- We need to
**prove**that__the distribution of every component is identical.__ - Real transcript: $\texttt{view}_{V^*}(P,V^*)=(s,b,z) $
- $s$ is square as same as random
- $b$ is
__generated in any bizarre way__, i.e. $b=V^*(s)$. - $z=\sqrt{sy^b}$ is random

- Simulated transcript: $\texttt{sim}_S((N,y),1^\lambda)=(s,b,y) $
- $s=z^2/y^b$ is square as same as random ($(N,y)\in \mathcal{L}$ so $y$ is square)

Besides, the distribution of $s$ hides $b$ perfectly. - $b$ has
**the same distribution**with $b’=V^*(s)$. - $z$ is random

- $s=z^2/y^b$ is square as same as random ($(N,y)\in \mathcal{L}$ so $y$ is square)
- QED

So far we have proven the QR protocol is (malicious-verifier) zero-knowledge.

## What made ZK Proof possible ?

**Each statement had multiple proofs**of which__the prover chooses one at random.__

(They are $(s,\sqrt{s})$ and $(s,\sqrt{sy})$ as for the QR protocol.)**Each such proof is made of two parts**(as shown above):- seeing either one on its own gives the verifier no knowledge ;
- seeing both imply 100% correctness. (That’s the
**completeness**)

**Verifier choose to see either part, at random.**

(Verifier can choose to see $\sqrt{s}$ or $\sqrt{sy}$ at random)

The prover’s ability to provide either part on demand convinces the verify. (That’s the**soundness**)

The__prover has to prepare both part correctly__, otherwise there is a half chance that he’ll get caught.

「Cryptography-MIT6875」: Lecture 13