Lecture 17

Strength through Truth

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

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

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:

This contradicts the definition of hardcore bit.

EOP

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: 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$

Diffie-Hellman Assumption:

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

So DDH assumption implies discrete logarithm assumption.

Idea:

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

And proceed by contradiction. This contradicts the DDH assumption.

EOP