Lecture 16

Continue on PRG

PRG exists $\implies$ Pseudorandom function family exists.

Multi-message secure encryption

$Gen(1^n):$ Output $f_i:\{0,1\}^n\to \{0,1\}^n$ from PRF family

$Enc_i(m):$ Random $r\gets \{0,1\}^n$ Ouput $(r,m\oplus f_i(r))$

$Dec_i(r,c):$ Output $c\oplus f_i(r)$

Proof of security:

Suppose $D$ distinguishes, for infinitly many $n$.

The encryption of $a$ pair of lists

(1) $\{i\gets Gen(1^n):(r_1,m_1\oplus f_i(r_1)),(r_2,m_2\oplus f_i(r_2)),(r_3,m_3\oplus f_i(r_3)),\ldots,(r_q,m_q\oplus f_i(r_q)), \}$

(2) $\{F\gets RF_n: (r_1,m_1\oplus F(r_1))\ldots\}$

(3) One-time pad $\{(r_1,m_1\oplus s_1)\}$

(4) One-time pad $\{(r_1,m_1'\oplus s_1)\}$

If (1) (2) distinguished,

$(r_1,f_i(r_1)),\ldots,(r_q,f_i(r_q))$ is distinguished from

$(r_1,F(r_1)),\ldots, (r_q,F(r_q))$

So $D$ distinguishing output of $r_1,\ldots, r_q$ of PRF from the RF, this contradicts with definition of PRF.

EOP

Noe we have

(RSA assumption and Discrete log assumption for one-way function exists.)

One-way function exists $\implies$

Pseudo random generator exists $\implies$

Pseudo random function familiy exists $\implies$

Mult-message secure encryption exists.

Public key cryptography

1970s.

The goal was to agree/share a key without meeting in advance

Diffie-Helmann Key exchange

A and B create a secret key together without meeting.

Rely on discrete log assumption.

They pulicly agree on modulus $p$ and generator $g$.

Alice picks random exponent $a$ and computes $g^a\mod p$

Bob picks random exponent $b$ and computes $g^b\mod p$

and they send result to each other.

And Alice do $(g^b)^a$ where Bob do $(g^a)^b$.

Diffie-Helmann assumption

With $g^a,g^b$ no one can compute $g^{ab}$.

Public key encryption scheme

Idea: The recipient Bob distributes opened Bob-locks

• Once closed, only Bob can open it.

Public-key encryption scheme:

1. $Gen(1^n):$ Outputs $(pk,sk)$
2. $Enc_{pk}(m):$ Efficient for all $m,pk$
3. $Dec_{sk}(c):$ Efficient for all $c,sk$
4. $P[(pk,sk)\gets Gen(1^n):Dec_{sk}(Enc_{pk}(m))=m]=1$

Let $A, E$ knows $pk$ not $sk$ and $B$ knows $pk,sk$.

Adversary can now encypt any message $m$ with the public key.

• Perfect secrecy impossible
• Randomness necessary

Security of public key

$\forall n.u.p.p.t D,\exists \epsilon(n)$ such that $\forall n,m_0,m_1\in \{0,1\}^n$

are distinguished by at most $\epsilon (n)$

This "single" message security implies multi-message security!

Left as exercise

We will achieve security in sending a single bit $0,1$

Time for trapdoor permutation. (EX. RSA)

Encryption Scheme: Given family of trapdoor permutation $\{f_i\}$ with hardcore bit $h(i)$

$Gen(1^n):(f_i,f_i^{-1})$, where $f_i^{-1}$ uses trapdoor permutation of $t$

$Output ((f_i,h_i),f_i^{-1})$

$m=0$ or $1$.

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

$Output (f_i(r),h_i(r)+m)$

$Dec_{sk}(c_1,c_2)$

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

$m=c_2+h_1(r)$