CSE442T Introduction to Cryptography (Lecture 17)

Chapter 3: Indistinguishability and Pseudorandomness

Public key encryption scheme (1-bit)

$Gen(1^n):(f_i, f_i^{-1})$

$f_i$ is the trapdoor permutation. (eg. RSA)

$Output((f_i, h_i), f_i^{-1})$ , where $(f_i, h_i)$ is the public key and $f_i^{-1}$ is the secret key.

$Enc_{pk}(m):r\gets \{0, 1\}^n$

$Output(f_i(r), h_i(r)\oplus m)$

where $f_i(r)$ is denoted as $c_1$ and $h_i(r)\oplus m$ is the tag $c_2$ .

The decryption function is:

$Dec_{sk}(c_1, c_2)$ :

$r=f_i^{-1}(c_1)$

$m=c_2\oplus h_i(r)$

Validity of the decryption

Proof of the validity of the decryption: Exercise.

Security of the encryption scheme

The encryption scheme is secure under this construction (Trapdoor permutation (TDP), Hardcore bit (HCB)).

Proof

We proceed by contradiction. (Constructing contradiction with definition of hardcore bit.)

Assume that there exists a distinguisher $\mathcal{D}$ that can distinguish the encryption of $0$ and $1$ with non-negligible probability $\mu(n)$ .

\{(pk,sk)\gets Gen(1^n):(pk,Enc_{pk}(0))\} v.s.\{(pk,sk)\gets Gen(1^n):(pk,Enc_{pk}(1))\} \geq \mu(n)

By prediction lemma (the distinguisher can be used to create and adversary that can break the security of the encryption scheme with non-negligible probability $\mu(n)$ ).

P[m\gets \{0,1\}; (pk,sk)\gets Gen(1^n):\mathcal{A}(pk,Enc_{pk}(m))=m]\geq \frac{1}{2}+\mu(n)

We will use this to construct an agent $B$ which can determine the hardcore bit $h_i(r)$ of the trapdoor permutation $f_i(r)$ with non-negligible probability.

$f_i,h_i$ are determined.

$B$ is given $f_i(r)$ and $h_i(r)$ and outputs $b\in \{0,1\}$ .

$r\gets \{0,1\}^n$ is chosen uniformly at random.
$y=f_i(r)$ is given to $B$ .
$b=h_i(r)$ is given to $B$ .
Choose $c_2\gets \{0,1\}= h_i(r)\oplus m$ uniformly at random.
Then use $\mathcal{A}$ with $pk=(f_i, h_i),Enc_{pk}(m)=(f_i(r), h_i(r)\oplus m)$ to determine whether $r$ is $0$ or $1$ .
Let $m'\gets \mathcal{A}(pk,(y,c_2))$ .
Since $c_2=h_i(r)\oplus m$ , we have $m=b\oplus c_2$ , $b=m'\oplus c_2$ .
Output $b=m'\oplus c_2$ .

The probability that $B$ correctly guesses $b$ given $f_i,h_i$ is:

\begin{aligned} &~~~~~P[r\gets \{0,1\}^n: y=f_i(r), b=h_i(r): B(f_i,h_i,y)=b]\\ &=P[r\gets \{0,1\}^n,c_2\gets \{0,1\}: y=f_i(r), b=h_i(r):\mathcal{A}((f_i,h_i),(y,c_2))=(c_2+b)]\\ &=P[r\gets \{0,1\}^n,m\gets \{0,1\}: y=f_i(r), b=h_i(r):\mathcal{A}((f_i,h_i),(y,b\oplus m))=m]\\ &>\frac{1}{2}+\mu(n) \end{aligned}

This contradicts the definition of hardcore bit.

Public key encryption scheme (multi-bit)

Let $m\in \{0,1\}^k$ .

We can choose random $r_i\in \{0,1\}^n$ , $y_i=f_i(r_i)$ , $b_i=h_i(r_i),c_i=m_i\oplus b_i$ .

$Enc_{pk}(m)=((y_1,c_1),\cdots,(y_k,c_k)),c\in \{0,1\}^k$

$Dec_{sk}:r_k=f_i^{-1}(y_k),h_i(r_k)\oplus c_k=m_k$

Special public key cryptosystem: El-Gamal (based on Diffie-Hellman Assumption)

Definition 105.1 Decisional Diffie-Hellman Assumption (DDH)

Define the group of squares mod $p$ as follows:

$p=2q+1$ , $q\in \Pi_{n-1}$ , $g\gets \mathbb{Z}_p^*/\{1\}$ , $y=g^2$

$G=\{y,y^2,\cdots,y^q=1\}\mod p$

These two listed below are indistinguishable.

$\{p\gets \tilde{\Pi_n};y\gets Gen_q;a,b\gets \mathbb{Z}_q:(p,y,y^a,y^b,y^{ab})\}_n$

$\{p\gets \tilde{\Pi_n};y\gets Gen_q;a,b,\bold{z}\gets \mathbb{Z}_q:(p,y,y^a,y^b,y^\bold{z})\}_n$

(Computational) Diffie-Hellman Assumption:

Hard to compute $y^{ab}$ given $p,y,y^a,y^b$ .

So DDH assumption implies discrete logarithm assumption.

Ideas:

If one can find $a,b$ from $y^a,y^b$ , then one can find $ab$ from $y^{ab}$ and compare to $\bold{z}$ to check whether $y^\bold{z}$ is a valid DDH tuple.

El-Gamal encryption scheme (public key cryptosystem)

$Gen(1^n)$ :

$p\gets \tilde{\Pi_n},g\gets \mathbb{Z}_p^*/\{1\},y\gets Gen_q,a\gets \mathbb{Z}_q$

Output:

$pk=(p,y,y^a\mod p)$ (public key)

$sk=(p,y,a)$ (secret key)

Message space: $G_q=\{y,y^2,\cdots,y^q=1\}$

$Enc_{pk}(m)$ :

$b\gets \mathbb{Z}_q$

$c_1=y^b\mod p,c_2=(y^{ab}\cdot m)\mod p$

Output: $(c_1,c_2)$

$Dec_{sk}(c_1,c_2)$ :

Since $c_2=(y^{ab}\cdot m)\mod p$ , we have $m=\frac{c_2}{c_1^a}\mod p$

Output: $m$

Security of El-Gamal encryption scheme

Proof

If not secure, then there exists a distinguisher $\mathcal{D}$ that can distinguish the encryption of $m_1,m_2\in G_q$ with non-negligible probability $\mu(n)$ .

\{(pk,sk)\gets Gen(1^n):D(pk,Enc_{pk}(m_1))\}\text{ vs. }\\ \{(pk,sk)\gets Gen(1^n):D(pk,Enc_{pk}(m_2))\}\geq \mu(n)

And proceed by contradiction. This contradicts the DDH assumption.