# 「Cryptography-MIT6875」: Lecture 16

**Topics Covered: **

- IP for Quadratic Non-Residuosity
- Non-interactive ZK
- NIZK in The Common Random String(CRS) Model
- Construction in CRS Model: Blum-Feldman-Micali’88 (quadratic residuosity)
- NIZK for QNR
- NIZK for 3SAT

- Proofs vs. Argument

At the end of last blog, we said that Non-Interactive Zero-Knowledge (NIZK) is __achievable in random oracle model.__

Today, we move to the __NIZK in the common random string model.__

# The Power of Interactive Proofs

Before proceeding to NIZK, let’s focus on **the power of Interaction Proofs(IP).**

**Is IP more powerful than NP ?**

We have been __using interaction to get zero knowledge proofs for NP.__

Indeed, __interaction is necessary.__

But, never mind zero knowledge for a moment.

Can you **prove more stuff with interactive proofs** than with traditional (i.e. NP) proofs ?

The thing to point is that we know **there is NP proof for quadratic residues**, i.e. proof = the square root, but **there is no NP proof for quadratic non-residues.**

In Lecture 14, we gave __interactive proofs for quadratic residuosity.__

Indeed, we can also __give an (honest-verifier perfect ZK) interactive for__ **quadratic non-residuosity.**

### IP for QNR

The prover wants to **convince** the verifier __that the $y$ is a quadratic non-residuosity.__

The interactive protocol is as shown below.

** ZK Proof for Quadratic Non-residue: **

- Verifier:
- pick a random $r$
- pick a random $b\gets{0,1}$
- send $s=r^2y^b$

- Prover:
- guess $b’$

- Verifier Check: $b=b’$

The protocol is **complete**, **sound** and **(honest-verifier perfect) zero-knowledge.**

*Completeness: *

Recall that the completeness is the property of the protocol when the prover and the verifier are both honest.

If $y$ is __non-square, the prover should be able to win.__

The thing to point is that the prover knows $y$ is non-square, so __maybe the she is unbounded or she knows the factorization__ of $N$ since there is no NP proof for QNR.

Hence, if $y$ is **non-square**, then the __prover can tell $s$ is square or non-square to answer $b’$.__

*Soundness: *

Recall that the soundness is the property of the protocol against malicious prover.

If $y$ is a square, then $r^2y^b$ is also a square.

Hence, the prover **cannot cheat the verifier** with probability __better than__ $1/2$.

Then we can __use sequential repetition or parallel repetition__ to reduce the soundness error.

*Honest-Verifier Perfect Zero Knowledge: *

Recall that the **zero-knowledge** is the property of the protocol against verifier.

The view of $V$ is $(r,b,b’)$, so the simulator can do exactly what $V$ dose.

The simulated view is $(r,b,b’=b)$ for a random $r$ and a random $b$.

Similarly, although there is __no NP proof__ for graph non-isomorphism, there is __an (honest-verifier perfect) interactive proof__ for **graph non-isomorphism.**

It turns out that **IP can prove more stuff than NP.**

Indeed, the **IP = PSPACE >> NP.**

**PSPACE** is the __set of things that we can decide__ if we have polynomial memory to work __with but potential exponential time.__

It’s surprising that we can prove such a language, i.e. QNR, using interactive proofs.

# NIZK: The Common Random String Model

In last blog is introduced that we can achieve **NIZK in the random oracle model.**

In this section, we will introduce another way, **the common random string model.**

In this model, there is __an angle coming up with random sequence of polynomial bits.__

The angle could be the sunspots.

**Completeness**: For every $G\in 3COL$, $V$ accepts $P$’s proof.**Soundness**: For every $G\notin3COL$ and any “proof” $\pi^\star$, $V(CRS,\pi^\star)$ accepts with probability $\le neg(n)$.**Zero Knowledge**: There is a PPT simulator such that for every $G\in 3COL$, $S$ simulates the view of the verifier $V$.$$

S(G)\approx(CRS\gets D, \pi \gets P(G,\text{colors})

$$- The view of verifier is $(CRS, \pi)$.
- The
**simulator**has to produce the simulated view**without knowing the witness and the CRS.**So the simulator has to__fake potentially the common random and the proof.__ - If we sort of
**change the definition**that the__simulator gets a common random string__and has to**produce the view with a fixed CRS**, then this definition is impossible to achieve.

For the same reason that we prove the NIZK is impossible (Lecture 15), it dose__not satisfy the soundness.__

Similarly, the **Common Reference String Model** is that there is an __angle coming up the random product of two primes__, not a sequence of random bits. And it cannot be achieved by the sunspots.

# Construct NIZK in the CRS Model

There are several constructions of NIZK in the CRS model.

**Blum-Feldman-Micali’88 (quadratic residuosity)**- Feige-Lapidot-Shamir’90 (factoring)
- Groth-Ostrovsky-Sahai’06 (bilinear maps)
- Canetti-Chen-Holmgren-Lombardi-Rothblum^2-Wichs’19 and Peikert-Shiehian’19 (learning with errors)

In this Lecture, we will introduce the first construction.

## Blum-Feldman-Micali’88 (quadratic residuosity)

- Review our number theory hammers & polish them.
- Construct
**NIZK for**a special NP language, namely**quadratic non-residuosity.** - Bootstrap to
**NIZK for 3SAT**, an NP-complete language.

### Quadratic Residuosity

Let $N=pq$ be a product of two large primes.

Jacobi symbol ($Jac$) divides $\mathbb{Z}_N^*$ evenly unless $N$ is a perfect square.

- $Jac_{-1}$: non-squares
- $Jac_{+1}$: pseudo-squares

A **surprising fact** is Jacobi symbol $\left(\frac{x}{N}\right)=\left(\frac{x}{P}\right) \left(\frac{x}{Q}\right)$ is __computable in poly. time without knowing $p$ and $q$.__ (using Law of Quadratic Reciprocity.[* 二次互反定理])

$x$ is square mod $N$ iff $x$ is square mod $p$ and square mod $q$, so we can even $Jac_{+1}$.

- $QR_N$: the set of squares mod $N$.
- $QNR_N$: the set of non-squares mod $N$. (but with Jacobi symbol $+1$)

We call $N$ good if exactly __half the elements__ of $\mathbb{Z}_N^*$ __with Jacobi symbol__ $+1$ are squares.

Exactly half residues **even** iff $N=p^iq^j$ is odd, and $i,j\ge 1$, not both even.

If $N$ is good, there is an important property is if $y_1$ and $y_2$ are both in $QNR$, then their product $y_1y_2$ is in $QR$.

(This property will be used in the following NIZK for QNR)

But if $N$ has three or more prime factors, **the fraction of residues is smaller.**

Besides, the property, “ if $y_1$ and $y_2$ are both in $QNR$, then their product $y_1y_2$ is in $QR$”, is **no longer satisfied.**

** Quadratic Residuosity Assumption (QRA): **

Let $N=pq$ be a product of two large primes.

No PPT algorithm can **distinguish** between a random element of $QR_N$ from a random element of $QNR_N$ **given only** $N$.

### NIZK for QNR

Define the NP language **GOOD** with instance $(N,y)$ where

- $N$ is
**good**; and - $y\in QNR_N$ (that is, $y$ has Jacobi symbol $+1$ but is not a square mod $N$)

The non-interactive protocol is as follows.

The prover wants to convince the verifier that $(N,y)$ is good.

** NIZK for QNR: **

- $CRS = (r_1,r_2,\dots,r_m)$ where each $r_i$ is sampled from $Jac_N^{+1}$.
- The
**proof**is $\forall i: \sqrt{r_i}$ or $\sqrt{yr_i}$ - The
**verifier check**- $N$ is odd
- $N$ is not a prime power
- $N$ is not a perfect square
- (
**Fact**: If the preceding three passes, then__at most half__of $Jac_N^{+1}$ are squares.) - I received either
__a mod-$N$ square root__of $r_i$ or $yr_i$.

*Completeness: *

If $N$ is good and $y\in QNR_N$, the prover can compute either $\sqrt{r_i}$ or $\sqrt{yr_i}$.

- The prover has a knowledge that $y$ is
**non-residuosity.**So, maybe__she is unbounded or knows the factorization of $N$.__ - If $r_i\in QR_N$: the prover can compute $\sqrt{r_i}$.
- If $r_i\in QNR_N$: $yr_i$ is
**square**by the property above so the prover can compute $\sqrt{yr_i}$.

*Soundness: *

What if $N$ has more than $2$ prime factors ?

No matter what $y$ is, for **half** the $r_i$ , both $r_i$ and $yr_i$ are **not** quadratic residues.

So the prover __cannot compute either $\sqrt{r_i}$ or $\sqrt{yr_i}$ for half the $r_i$.__

- Suppose $N=pqr$
- The fraction of quadratic residues in $Jac_{+1}$ is $1/4$.
- Besides, the property, “ if $y_1$ and $y_2$ are both in $QNR$, then their product $y_1y_2$ is in $QR$”, is
**no longer satisfied.**

*Perfect Zero Knowledge Simulator S: *

First pick the proof $\pi_i$ to be random in $\mathbb{Z}_N^*$.

Then **reverse-engineer the CRS**, letting $r_i=\pi_i^2$ or $r_i=\pi_i^2/y$ randomly.

The distribution of simulated view is **identical** to the real view.

### NIZK for 3SAT

**Boolean Variables**: $x_i$ can be either true(1) or false(0).- A
**Literal**is either $x_i$ or $\overline{x_i}$ - A
**Clause**is a__disjunction of literals.__- A Clause is
**true**if any one of the literals is true. - E.g. $x_1\vee x_2\vee \overline{x_5}$ is true as long as $(x_1,x_2,x_5)\ne(0,0,1)$

- A Clause is
- A
**3-SAT formula**is a__conjunction of many 3-clauses.__- A 3-SAT formula $\Psi$ is
**satisfiable**if there is an assignment of values to the variables $x_i$ that makes all its clauses true. - $\Psi=\left(x_{1} \vee x_{2} \vee \overline{x_{5}}\right) \wedge\left(x_{1} \vee x_{3} \vee x_{4}\right)\wedge\left(\overline{x_{2}} \vee x_{3} \vee \overline{x_{5}}\right)$

- A 3-SAT formula $\Psi$ is

Recall NIZK for QNR.

We saw a way to show that a pair $(N,y)$ is GOOD. That is:

- the following is the picture of $\mathbb{Z}_N^*$ and
- for every $r\in Jac_{+1}$, either $r$ or $ry$ is a quadratic residue.

The prover wants to __convince the verifier that $\Psi$ is satisfiable.__

The input $\Psi=\left(x_{1} \vee x_{2} \vee \overline{x_{5}}\right) \wedge\left(x_{1} \vee x_{3} \vee x_{4}\right)\wedge\left(\overline{x_{2}} \vee x_{3} \vee \overline{x_{5}}\right)…$ with $n$ variables and $m$ clauses.

The non-interactive protocol is as follows.

** NIZK for 3SAT: **

- $CRS=(r_1,r_2,…)$ where each $r_i$ is sampled from $Jac_N^{+1}$.

Note: Similarly, we can Let CRS be random numbers and interpret them as elements of $\mathbb{Z}_N^*$, and both the prover and the verifier filter out $Jac_N^{-1}$.

- Prover picks an $(N,y)$ and
**proves that it is GOOD.**(as defined above) - Prover
**encodes the satisfying assignment**and sends the**encode variables**$(y_1,\dots,y_n)$ to $V$.

We should__hide the values to achieve zero knowledge__so the encoding is indeed a commitment.- $y_i\gets QR_N$ if $x_i$ is false (encryption of $0$ is a residue)
- $y_i \gets QNR_N$ if $x_i$ is true (encryption of $1$ a non-residue)
- For the literal $x_i$,
- $Enc(x_i)=y_i$
- $Enc(\overline{x_i})=yy_i$

**exactly one**of the $Enc(x_i)$ or $Enc(\overline{x_i})$ is a**non-residue.**- A
**residue**is indeed__the encryption of 0(false)__ - A
**non-residue**is indeed__the encryption of 1(true)__

- A

**Prove**that__(encoded) assignment satisfies each clause.__- For each clause, say $x_1\vee x_2\vee \overline{x_5}$, we
**WANT to SHOW**: $x_1$ OR $x_2$ OR $\overline{x_5}$ is**true**. - Let $(a_1=y_1,b_1=y_2,c_1=yy_5)$ denote the
__encoded variables.__ - So, each of them is either $y_i$ (if the literal is a var) or $yy_i$ (if the literal is a negated var).
- Now, we
**WANT to SHOW**: $a_1$ OR $b_1$ OR $c_1$ is a**non-residue**.

- For each clause, say $x_1\vee x_2\vee \overline{x_5}$, we

A **terrible way** is to prove $a_1$ is non-residue or $b_1$ is non-residue.

If the prover convinces the verifier that $a_1$ is non-residue, $P$ indeed tells $V$ that $x_1$ is true(1).

Hence, we want to __prove one of them is a non-residue__ **without telling the verifier that which one is non-residue.**

__ WANT to SHOW: __ $a_1$

**OR**$b_1$

**OR**$c_1$ is

__a non-residue__

Equivalently, the

**signature**of $(a_1,b_1,c_1)$ is**NOT**(QR, QR, QR).A

**clever idea**is to generate seven additional triples.- The original triple is $(a_1,b_1,c_1)$.
- This
**8 triples**__span all possible QR signatures.__ - There is
**one triple is (QR, QR, QR)**, e.g. the second triple, and__reveal the square roots of this triple.__ - Then we can
__prove the origin triple is NOT (QR, QR, QR).__

Proof consists of two parts

**Proof of Coverage**: show that the**8 triples span all possible QR signatures.**- For
__each__of poly. many triples $(r,s,t)$ from CRS, show__one of the 8 triples has the same signature.__ - That is, there is a triple $(a_i,b_i,c_i)$ s.t. $(ra_i,sb_i,tc_i)$ is (QR, QR, QR)

- For
- Show
**one triple**(except the original triple) is**(QR, QR, QR) and reveal the square roots.**

Hence, **the full proof** is as follows.

Prover picks an $(N,y)$ and

**proves that it is GOOD.**Prover

**encodes the satisfying assignment**and sends the**encode variables**$(y_1,\dots,y_n)$ to $V$.Prove that (encoded) assignments

**satisfy each clause.**For each clause, construct the proof $\rho$ =

__(7 additional triples, square root of the second triples, proof of coverage).__

Completeness and Soundness can be inherited from NIZK for QNR.

*Computational Zero Knowledge Simulator S: *

Simulator picks $(N,y)$ where $y$ is a **quadratic residue.**

- Simulated view of $(N,y, \pi)$
- Pick the proof $\pi_i$ to be random in $\mathbb{Z}_N^*$.
- Reverse-engineer the CRS, letting $r_i=\pi_i^2$ or $r_i=\pi_i^2/y$ randomly.

- Then $r_i=\pi_i^2$ and $r_i=\pi_i^2/y$ are both
__residues__. - The distribution of simulated view is
**computationally indistinguishable**to the real view.

- Simulated view of encoded assignments $(y_1,\dots, y_n)$
- $y_i \gets QNR_N$ whether $x_i$ is true or false (encryptions are
**both non-residues**)- $Enc(x_i)=y_i$ (encryption of $1$ is a non-residue)
- $Enc(\overline{x_i})=yy_i$ (encryption of $0$ is a non-residue)

**Encoding of ALL literals can be set to true.**

- $y_i \gets QNR_N$ whether $x_i$ is true or false (encryptions are

# Proofs vs. Argument

Before proceeding to the evolution of proofs, let’s discuss the **difference** between __proofs and arguments.__

The main difference is the **definition in soundness.**

In Lecture 14, we gave the **definition of soundness in Proofs** that __nobody can convince you a false statement__. We mentioned that the soundness holds **agains unbounded provers.**

**Arguments** is where the soundness holds **against only computational bounded provers.**

It’s actually weakening the notion of proof.

Why do we still introduce the the argument ?

- It allows us to get
**perfect zero knowledge for all of NP.**

Recall__perfect ZK proofs do not exist for NP-complete languages,__unless the polynomial hierarchy collapses. It turns out that if we weaken the notion of proofs, then we can construct the perfect zero knowledge systems. - It allows us to
**get very short proof**= succinct arguments or SNARGs.

SNARKs : succinct arguments of knowledge.

# The Evolution of Proofs

Proofs have been evolving over generations.

**CLASSIC Proofs**(Complexity class: NP) Prover writes down a string (proof); And Verifier checks.**INTERACTIVE Proofs**(Complexity class: IP = PSPACE >> NP) Prover and verifier talk back and forth. In last blog, we introduced the zk proof for**quadratic non-residue.****PROBABILISTICALLY CHECKABLE Proofs**(Complexity class: NEXP >> PSPACE) Non-interactive, but verifier only looks at 3 bits of proof.- MULTIPROVER interactive proofs
- Proofs in the wild: ZCash

「Cryptography-MIT6875」: Lecture 16