8 Public Key Encryption

We have seen so far a few examples of symmetric encryption schemes, where knowledge of the encryption key immediately allows for correct decryption. Unlike these, (PKE) schemes uses two keys generated by a common key generation algorithm KeyGen, namely, a public key $pk$ used only in the encryption step, and a secret key $sk$ used only in the decryption step. The idea is for the encryption scheme to be secure even if an adversary knows $pk$ (but not $sk$).

PKE

The advantage of PKEs is that it allows for a simpler key management, as the key can be publicly shared. On the other hand, they are often constructed from complex mathematical objects, relying on strong mathematical assumptions that might eventually be proved wrong, and typically requiring more resources to be calculated.

Two widely used families of PKE are Rivest-Shamir-Adleman (RSA) and ElGamal, which is usually based on elliptic curve cryptography.

8.1 RSA encryption

The KeyGen algorithm for “textbook” RSA is outlined below:

Pick random primes $p\neq q$ of length $\frac{n}{2}$
Define the “RSA modulus” $N = pq$
Select $d \xleftarrow{\$} \{1,\ldots,N-1\}$ coprime with the Euler totient $\varphi(N)=(p-1)(q-1)$, which is itself the number of integers smaller than $N$ that are coprime with $N$
Using the extended Euclidean algorithm, find $e$ such that $ed\equiv 1 \mod \varphi(N)$
$pk := (N, e)$
$sk := (N, d)$

We encrypt a message $m$, which is an integer less than $N$, by $\textrm{Enc}(pk,m):=m^e \bmod N$, and decrypt a cyphertext by $\textrm{Dec}(sk,c):=c^d \bmod N$. For $m<N$, we have \[\begin{equation} \begin{split} \textrm{Dec}(sk, \textrm{Enc}(pk, m)) & = (m^e \bmod N)^d = m^{ed} \bmod N \\ & = m^{ed \bmod \varphi(N)} \bmod N = m^1 \bmod N = m, \end{split} \end{equation}\]

thus the RSA algorithm has correctness. In the third inequality we used Fermat’s little theorem, which states that if two integers $m$ and $N$ are coprime, then $m^{\varphi(N)} \equiv 1 \mod N$, so that

\[\begin{equation} \begin{split} m^{ed}=m^{(ed \mod \varphi(N))+k\cdot\varphi(N)}=m^{(ed \mod \varphi(N))}\cdot(m^{\varphi(N)})^k \\ \equiv m^{(ed \mod \varphi(N))}\cdot 1^k\mod N \end{split} \end{equation}\]

This only works if $m$ and $N$ are coprime, which is not a problem given that finding an $m$ that is not coprime would entail breaking the encryption, as you will see below.

We do not have yet a proof that RSA is secure. Instead, we used the so-called $(t, \epsilon)$-RSA assumption, which states that for each $t$-time classical adversary $A$, \[\Pr[m=m': (pk,sk) \leftarrow\textrm{KeyGen}, m\xleftarrow{\$}\{0,\ldots,N-1\}, c\leftarrow \textrm{Enc}(pk,m), m'\leftarrow A(pk,c)]\leq\epsilon.\] That is, $A$ can decrypt $\textrm{Enc}(pk,m)$ for random $m$ with low probability.

This is believed to hold classically, which means that we cannot decrypt an RSA encryption of a uniformly random plaintext. Currently, the best known approach to attacking RSA works as follows:

Factor $N$ into $p$ and $q$
Compute $\varphi(N) = (p-1)(q-1)$, and use it to find a $d$ such that $ed \equiv 1 \bmod \varphi(N)$
Decrypt normally using $sk = (N,d)$

The best known algorithm for factoring clasically is the general number field sieve (GNFS), with runtime $\mathcal{O}(2^{c\cdot n^{1/3}\cdot(\log n)^{2/3}})$, which is subexponential but superpolynomial (making factoring of larger numbers unfeasible). For reasonable $n$, the RSA assumption is hard to break.

Even classically, “textbook RSA” is not a good encryption scheme. One could encrypt a message from a more restricted message space, for example a single English word. An attacker could simply try encrypting all English words and comparing the result. Additionally, if $m$ comes from the set ${0,\ldots,N^{1/3}}$, there are efficient ways of decoding it, which are beyond the scope of this course. The latter caveat can be overcome by combining it with a variant of a Feistel scheme, for example (RSA-OAEP).

RSA is notably post-quantum secure, since $N$ can be factored in $\mathcal{O}(n^3)$ using Shor’s algorithm, thus $sk$ can be obtained in polynomial time.

8.2 ElGamal encryption

For the ElGamal encryption, we will fix some finite cyclic group $G$ (e.g. numbers mod $p$, $\mathbb{Z}/p\mathbb{Z}$, or elliptic curves). Fix a $g$ of $G$, that is, an element of $G$ such that all elements of $G$ can be written as $g^n$ for some $n \in \mathbb{Z}$. Every cyclic group has at least one such element. We have the KeyGen:

$sk:=x\xleftarrow{\$}\{0,\ldots,|G|-1\}$
$pk:=h:=g^x$

Since $g$ is a generator, $h$ is uniformly distributed among the elements of $G$. We can now encrypt an element $m$ of $G$ and decrypt a cyphertext by:

$\textrm{Enc}(pk,m): r\xleftarrow{\$}\{0,\ldots,|G|-1\}$, return $c:=(g^r, m\cdot h^r)$,
$\textrm{Dec}(sk,c):$ compute $m':=c_2/c_1^x=mh^r/g^{rx}=mh^r/h^r=m$, return $m$.

Note that the cyphertext length is twice the plaintext length.

8.3 IND-CPA security

ElGamal encryption is believed to classically satisfy the security definition IND-CPA (“indistinguishability under chosen plaintext attacks”) under the decisional Diffie-Hellman (DDH) assumption, which is believed to be true for groups like elliptic curves. IND-CPA guarantees that the adversary learns about the plaintext, even if the plaintext is not uniformly random. That is, given the encryption of of two messages $m_0$ and $m_1$, an adversary canot distinguish between $\textrm{Enc}(pk, m_0)$ and $\textrm{Enc}(pk, m_1)$, as illustrated below:

We can formally define it as follows:

Definition 8.1 IND-CPA (public key case) $(\textrm{Enc}, \textrm{Dec})$ is $(t,\epsilon)$-IND-CPA-secure iff for each $t$-time adversary $A$: \[\begin{equation} \begin{split} |\Pr[b=1: pk,sk\leftarrow\textrm{KeyGen()}, m_0,m_1\leftarrow A(pk), c\leftarrow \textrm{Enc}(pk,\color{red}m_0\color{black}), b\leftarrow A(c)]- \\ \Pr[b=1: pk,sk\leftarrow\textrm{KeyGen()}, m_0,m_1\leftarrow A(pk), c\leftarrow \textrm{Enc}(pk,\color{red}m_1\color{black}), b\leftarrow A(c)]|\\ \leq\epsilon. \end{split} \end{equation}\]

If the message space is infinite (e.g. $\{0,1\}^\star$), we typically add the requirement that the adversary must output $m_0$ and $m_1$ with |$m_0$| = |$m_1$|.

Note that, if a PKE scheme has a deterministic encryption algorithm, it cannot be IND-CPA secure. This is because an adversary equipped with $pk$ can simply encrypt one of the messages $m_0$ or $m_1$ and compare it with the received cyphertext. This also means that textbook RSA requires some modifications to become IND-CPA, since it is deterministic. In practical cases, we actually want the encryption to be even more secure than IND-CPA, for it to be secure against chosen attacks (see the IND-CCA definition introduced later).

8.4 Quantum security of ElGamal

To study the quantum security of the ElGamal algorithm, we first need to formulate the :

(Dlog) Given $G$, $g$, $h:=g^x$, find $x \mod |G|$

If you can solve dlog, you can extract $sk$ from $pk$. To solve dlog with a quantum computer, we will use another function $f:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}^n$ defined as $f(a,b):=h^ag^{-b}$. We can verify that $f$ has period $(1,x)$ with respect to component-wise addition:

\[f(a+1,b+x)=h^{a+1}g^{-(b+x)}=h^ag^{-b}hg^{-x}=h^ag^{-b}=f(a,b)\]

We can now use a variant of Shor’s algorithm for dlog. Assume for simplicity that $|G|=2^n$, and recall the definition of the DFT:

$\textrm{DFT} _N = \frac{1}{\sqrt{N}}(\omega^{kl})_{kl}$, with $\omega=e^{2\pi i/N}$ the $N^{\textrm{th}}$ root of unity.

The calculation of $DFT_{2^n}$ can be efficiently done on a quantum computer by a unitary that requires $\mathcal{O}(n^2)$ gates to be implemented. The $DFT$ maps a periodic signal to its frequencies.

Now, define the unitary $U_f: |x,y,z\rangle \rightarrow |x,y,z\oplus f(x,y)\rangle$ an run the following quantum circuit:

Right after applying $U_f$, the state of the quantum system is $|\psi_1\rangle=\sum_{a,b} 2^{-n}|a,b,f(a,b)\rangle$, where the sum runs over all $a$ and $b$ from 0 to $2^n$. After the measurement outcome $y$, our state will be $|\psi_2\rangle=\sum_{a,b} \alpha|a,b,y\rangle$, where the sum will only run over the values of $a$ and $b$ that obey $f(a,b)=y$, and $\alpha>0$ will be some normalization constant. There is a pair $(a_0,b_0)$ such that $f(a_0, b_0)=y$. Then, since $f(a,b)=y=f(a_0, b_0)$, we have that:

\[g^ah^{-b} = g^{a_0}h^{-b_0} \textrm{ iff } g^{a-bx} = g^{a_0-b_0x} \textrm{ iff } a-bx \equiv a_0-b_0x \mod |G|\]

iff $\exists k$ such that $b = b_0+k$ and $a = a_0+kx$. This allows us to rewrite the $|\psi_2\rangle$ as $\sum_k \alpha|a_0+kx, b_0+k\rangle \otimes |y\rangle$. The state after separately applying $DFT$ on the $a$ and $b$ registers can be determined by:

\[\begin{equation} \begin{split} |\psi_3\rangle & = (\textrm{DFT}\otimes \textrm{DFT}) \sum_k |a_0+kx, b_0+k\rangle = \sum_k \textrm{DFT} _{\mu,a_0+kx}\otimes \textrm{DFT} _{\nu, b_0+k}\\ & = \sum_k \omega^{\mu(a_0+kx)}\omega^{\nu(b_0+k)}=\omega^{\mu a_0}\omega^{\nu b_0}\sum_k (\omega^{\mu x+\nu})^k \end{split} \end{equation}\]

The last sum is then equal to $2^n$ if $\mu x+\nu\equiv 0 \bmod 2^n$ and 0 otherwise, which means that any measurement result $(a', b')$ will satisfy $a'x+b'\equiv 0 \bmod 2^n$. If $a'$ is even, this measurement should be discarded, and the algorithm run once again. If $a'$ is odd, then we obtain our $sk$ by $x = -\frac{b'}{a'}\mod 2^n$. This is accomplished in $\mathcal{O}(n^2)$ time plus the time to implement the exponentiation in $G$ with $U_f$, which means that ElGamal is not secure against quantum attacks.