# 「Cryptography-MIT6875」: Lecture 9

**Topics Covered: **

- Quadratic Residue and Quadratic Residuosity Assumption
- Goldwasser-Micali Encryption and Homomorphism
- Diffie-Hellman Key Exchange
- El Gamal Encryption

In last blog is showed one of the constructions of public-key encryption using Trapdoor Permutations, RSA encryption.

The gist in this blog is the remaining three constructions of public-key encryption.

**Constructions of Public-Key Encryption: **

- Trapdoor Permutations (RSA)
*Quadratic Residuosity/Goldwasser-Micali**Diffie-Hellman/El Gamal**Learning with Errors/Regev*

# Quadratic Residue

## QR mod P

Let $P$ be prime.

We saw (in Lecture 6) that __exactly half__ of $\mathbb{Z}_P^*$ are squares.

Define **Legendre symbol** $\left(\frac{x}{P}\right)=1$ is $x$ is *square*, $-1$ if $x$ is *not a square*, and $0$ if $x=0\mod P$.

We can **tell efficiently** whether $x$ is a *quadratic residue* mod P using **Legendre symbol.**

Then we split $\mathbb{Z}_P^*$ in half, one is **square** and the other is **non-square.**

It is **easy** to compute square roots mod $P$.

Besides, it’s an **explicit** formula for the case where $P=3\pmod 4$.

**Claim:**

The square roots of $x \mod P$ are $\pm x^{(P+1) / 4}$.

**Proof:**

## QR mod N

Now, let $N=PQ$ be a **product of two primes** and look at $\mathbb{Z}_N^*$.

Define **Jacobi symbol** $\left(\frac{x}{N}\right)=\left(\frac{x}{P}\right) \left(\frac{x}{Q}\right)$ to be $+1$ if $x$ is __a square mod both__ $P$ and $Q$ __or a non-square mod both__ $P$ and $Q$.

So we can also split $\mathbb{Z}_N^*$ in half, and the **Jacobi symbol** for __one half is $+1$ and the other is $-1$.__

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$.__

The **key** is __Law of Quadratic Reciprocity.__

The one thing to **notice** is that the **Legendre symbol**$\left(\frac{x}{P}\right)$ tells you **exactly** whether $x$ is the square mod $P$ or not.

But the **Jacobi symbol** $\left(\frac{x}{N}\right)=1$ only gives you **partial information** that is square mod both $P$ and $Q$ **or** non-square mod both $P$ and $Q$.

But $x$ is **square** mod $N$ **iff** $x$ is square mod $P$ and it is a square mod $Q$.

Hence, there are __two cases for $Jac_{+1}$.__

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

The Jacobi symbol can be $+1$ even though $x$ is not square mod $N$, so it’s **pseudo-square.**

The **conjecture** is that __distinguishing between $QR_N$ and $QNR_N$ is__ a **hard problem.**

We cannot distinguish from squares and pseudo-squares.

Can we use this hardness?

## Finding Square Roots Mod N

The fact is __finding square roots__ mod $N$ is **as hard as** __factoring__ $N$.

### Suppose we know P and Q.

Suppose we know $P$ and $Q$, and we want to find the square root of $x \mod N$.

We can find the square root of $x\mod N$ by following **algorithm**.

**Algorithm:**

- Find the square roots of $y\mod P$ and $y\mod Q$.
- $x=y_P^2\mod P$
- $x=y_Q^2\mod Q$

- Let $y=c_Py_P+c_Qy_Q$ where the
*CRT coefficients.*- $c_P=1\mod P \text{ and }0 \mod Q$
- $c_Q=0\mod P \text{ and }1 \mod Q$

- Then $y$ is
**a square root**of $x\mod N$.

**Proof:**

The proof is easy using CRT.

- $y^2 = (c_Py_P + c_Qy_Q)^2\mod N$
- We can map $y^2$ to pair $(y^2\mod P, y^2\mod Q)$
- Then we get pair $(y_P^2\mod P,y_Q^2 \mod Q)$
- That is $x$.
- Moreover, we can get $x=y^2\mod N \longleftrightarrow \begin{array}{c}x=y^2\mod P \\x=y^2 \mod Q\end{array}$.

Therefore, the **takeaway** is if $x$ is a *square*, it __has $4$ distinct square roots__ $\mod N$.

Because it *respectively* has $2$ distinct square roots $\mod P$ and $\mod Q$.

### Suppose we know square root.

Suppose we have a box that computes square roots $\mod N$.

The thing to notice is that the box **only returns one square** $y$ as it has $4$ distinct square roots.

So if we feed the box $x=z^2\mod N$ for *a random* $z$ of our choice, the __box can return other square root.__

We can use the box to factor $N$.

Feed the box $x=z^2 \mod N$ for a random $z$.

**Claim:**

With probability $1/2$, $\operatorname{gcd}(z+y,N)$ is a non-trivial factor of $N$.

**Proof:**

- Notation:
- $z$ denotes the square root of $x$, which is known.
- $x$ denotes the input of box s.t. $x=z^2 \mod N$.
- $y$ denotes the output of box s.t. $x=y^2\mod N$, which
__could be different with $z$ .__

- We know $y^2=z^2\mod N$.
- $N\mid y^2-z^2$
- $N\mid (y-z)(y+z)$

- There are
**three cases.**- If $N\mid (y-z)$, we can get $y=z\mod N$. (Useless)
- If $N\mid (y+z)$, we can get $y=-z\mod N$. (Useless)
- If $N\nmid (y-z)$ and $N\nmid (y+z)$, what can we get ?
- $(y-z)$ and $(y+z)$
__respectively have a factor__of $N$ since $N=PQ$. - So $\operatorname{gcd}(z+y,N)$ is a non-trivial factor of $N$.

- $(y-z)$ and $(y+z)$

- Hence, $\operatorname{gcd}(z+y,N)$ is a non-trivial factor of $N$ if $y\ne z$ and $y\ne-z$.

The probability is $1/2$. - QED.

It’s a very clever trick to factor.

I know a solution to a problem that turns it into an Oracle.

The Oracle could actually help me in solving another problem.

It’s an example of the **reduction**.

## Quadratic Residuosity Assumption(QRA)

Finding square roots is as hard as factoring $N$.

Moreover, **recognizing squares** $\mod N$ also **seems hard** as we mentioned above.

# Goldwasser-Micali (GM) Encryption

**Goldwasser-Micali (GM) Encryption** is under the **Quadratic Residuosity Assumption.**

## GM Scheme

$Gen(1^n)$:

Generate random $n$-bit prime $p$ and $q$ and let $N=pq$.

Let $y\in QNR_N$ be some

**quadratic non-residue**with*Jacobi symbol*$+1$.Let $pk=(N,y)$.

Let $sk=(p,q)$.

$Enc(pk,b)$ where $b$ is

__a bit:__- Generate random $r\in\mathbb{Z}_N^*$.(randomness)
- Output $\begin{cases}r^2\mod N &, \text{if }b =0 \\r^2y\mod N &,\text{if }b=1 \end{cases}$.

$Dec(sk,c)$:

- Check if $c\in\mathbb{Z}_N^*$ is a quadratic residue using $p$ and $q$.
- If yes, output $0$ else $1$.

If $b=0$, the encryption is $r^2$, which is **quadratic residue** with *Jacobi symbol* $+1$.

If $b=1$, the encryption is $r^2y$, which is **quadratic non-residue** with *Jacobi symbol* $+1$.

Although you __know the Jacobi symbol__ is $+1$, you **have no idea** that __the ciphertext is square or pseudo square.__

Hence, **IND-security** follows directly **from the quadratic residuosity assumption.**

## GM is a Homomorphic Encryption

Given a GM-ciphertext of $b$ and a GM-ciphertext of $b’$, I can compute a GM-ciphertext of $b+b’\mod 2$ **without knowing anything about $b$ or $b’$.**

$Enc(pk,b)$ where $b$ is a bit:

Generate random $r\in\mathbb{Z}_N^*$ and output $r^2y^b\mod N$.

**Claim:**

$Enc(pk,b)\cdot Enc(pk,b’)$ is an encryption of $b\oplus b’=b+b’\mod2$.

**Proof:**

- Consider $c_1=r_1^2y^b$ and $c_2=r_2^2y^{b’}$.
- $c_1\cdot c_2 = r_1^2r_2^2 y^{b+b’}$ .
- $c_1\cdot c_2$ is QR if $b+b’=0\mod 2$.

The takeaway here is $QR\cdot QR=QR$ and $QNR\cdot QNR=QR$.

# Diffie-Hellman Key Exchange

The **main idea** is the __commutativity in the exponent__, $(g^x)^y=(g^y)^x$, where $g$ is an element of some group.

So you can compute $g^{xy}$ given either $g^x$ and $y$, or $g^y$ and $x$.

We elaborated the **Diffie-Hellman Assumption** in Lecture 6.

**Diffie-Hellman Assumption(DHA):**

Hard to compute $g^{xy}$ given only $g,g^x$and $g^y$.

**Diffie-Hellman Key Exchange:**

- Let $p=2q+1$ be a safe prime, and $g$ be the generator of $QR_p$.
- Alice picks a random number $x\in \mathbb{Z}_q$ and sends $g^x\mod p$ to Bob.
- Bob picks a random number $y\in\mathbb{Z}_q$ and sends $g^y\mod p$ to Alice.

- Alice and Bob have the shared key $k=g^{xy}\mod p$
- Alice computes it by $g^y$ and $x$.
- Bob computes it by $g^x$ and $y$.

## El Gamal Encryption

- $Gen(1^n)$:
- Generate an $n$-bit safe prime $p=2q+1$ and a generator $g$ of $\mathbb{Z}_p^*$.

Let $h=g^2\mod p$ be a**generator**of $QR_p$.

Choose a**random**number $x\in \mathbb{Z}_q$. - Let $pk=(p,h,h^x)$.
- Let $sk=x$.

(Finding $sk$ from $pk$ is the*discrete logarithm problem*.)

- Generate an $n$-bit safe prime $p=2q+1$ and a generator $g$ of $\mathbb{Z}_p^*$.
- $Enc(pk,m)$ where $m\in QR_p$.
- Generate
**random**$y\in\mathbb{Z}_q$. (randomness) - Output $(h^y,h^{xy}\cdot m)$.

- Generate
- $Dec(sk=x,c)$
- Compute $h^{xy}$ using $h^y$ and $x$.
- Divide the second component to retrieve $m$.

**Decisional Diffie-Hellman Assumption (DDHA):**

Hard to distinguish between $g^{xy}$ and a uniformly random group element, given $g,g^x$ and $g^y$.

That is the following two distributions are *computationally indistinguishable:*

$(g,g^x,g^y,g^{xy})\approx (g,g^x,g^y,u)$

From DDH assumption, we know

- It’s
*hard to distinguish*between $(h,h^x,h^y,h^{xy})$ and $(h,h^x,h^y,u)$. - Moreover, it’s
*hard to distinguish*between $(h,h^x,h^y,h^{xy})$ and $(h,h^x,h^y,h^{xy}\cdot m)$ since $m$ is random, so is $m\cdot h^{xy}$. - So it’s
*hard to distinguish*between $(h,h^x,h^y,h^{xy}\cdot m)$ and $(h,h^x,h^y,h^{xy})$.

Hence, DH/El Gamal is **IND-secure** under the **DDH assumption.**

The source of **hardness** is __different in RSA and GM__. There is no factoring and only DH problem.

## Which Group to Use

**Quadratic Residue Group:**

We used the $QR_P$ group for a safe prime $P=2Q+1$ where $Q$ is prime so far. The order of the group is $Q$.

But it is **not used** in practice.

Because **discrete log** can be *broken* in **sub-exponential** time $2^{\sqrt{\log P\log\log P}}$.

It’s better than $poly(P)$ but worse than $poly(\log P)$.

And the $poly(\log P)$ is what we’re referring to $poly(n)$.

**Elliptic Curve Groups:**

In practice, we use **Elliptic Curve Groups** in DH/El Gamal.

It is the set of solutions $(x,y)$ to the equation $y^2=x^3+ax+b\pmod P$ together with a very cool group addition law.

The **best known discrete log algorith**m is $\mathcal{O}(\sqrt{P})$ time!

That says that we can use **much smaller keys**. We can use 160-bit $P$ to suffice “80-bit security”.

# Summary

We have elaborated three constructions of public-key encryption.

**Constructions of Public-Key Encryption: **

*Trapdoor Permutations (RSA)**Quadratic Residuosity/Goldwasser-Micali**Diffie-Hellman/El Gamal*- Learning with Errors/Regev

If **factoring** is easy, __RSA is broken__ (and that’s the only known way to break RSA).

If **factoring** is easy, __Goldwasser-Micali is broken__ conjecturing that finding square roots or recognizing the squares are both as hard as factoring.

Moreover, the __discrete problem__ is similarly broken to **factoring** in *quantum computer.*

Hence, the preceding three constructions are dead if the quantum computer comes out.

Yet **learning with errors** is *post-quantum secure* as far as we know.

We will see more when we do homomorphic encryption.

## Practical Considerations

There are some practical considerations.

How do I know the public key?

**Public-key Infrastructure**: a directory of identities together with their public keys.- But it needs to be “
**authenticated**”.

Otherwise Eve could replace Bob’s $pk$ with her own.

Public-key encryption is

**orders of magnitude slower**than secret-key encryption.We mostly showed how to

__encrypt bit-by-bit__! Super-duper**inefficient**.__Exponentiation__takes $O(n^2)$ time as opposed to typically__linear time__for secret key encryption (AES).The $n$

__itself is large__for PKE (RSA: $n\ge 2048$) compared to SKE (AES: $n=128$).

(For Elliptic Curve El-Gamal, it’s $320$ bits.We can solve problem 1 and minimize problems 2&3 using

**hybrid encryption.**

**Hybrid Encryption**- To encrypt a long message $m$ (think 1GB)
- Pick a random key $K$ (think 128 bits) for a secret-key encryption.
- Encrypt $K$ with the $PKE$: $PKE.Enc(pk,K)$.
- Encrypt $m$ with the $SKE$: $SKE.Enc(K,m)$.

- To decrypt:
- Recover $K$ using $sk$.
- Then using $K$, recover $m$.

- To encrypt a long message $m$ (think 1GB)

「Cryptography-MIT6875」: Lecture 9