Lecture 14

Recap

$\exists$ one-way functions $\implies$ $\exists$ PRG expand by any polynomial amount

$\exists G:\{0,1\}^n \to \{0,1\}^{l(n)}$ s.t. $G$ is efficiently computable, $l(n) > n$, and $G$ is pseudorandom

Back to the experiment we did long time ago:

So Group 1 is human, Group 2 is computer.

New material

Computationally secure encryption

Recall with perfect security,

for all $m_1,m_2\in M$ and $c\in C$.

$(Gen,Enc,Dec)$ is single message secure if $\forall n.u.p.p.t \mathcal{D}$ and for all $n\in \mathbb{N}$, $\forall m_1,m_2\gets \{0,1\}^n \in M^n$, $\mathcal{D}$ distinguishes $Enc_k(m_1)$ and $Enc_k(m_2)$ with at most negligble probability.

By the prediction lemma, ($\mathcal{A}$ is a ppt, you can also name it as $\mathcal{D}$)

and the above equation is $\frac{1}{2}$ for perfect secrecy.

Construction of single message secure cryptosystem

cryptosystem with shorter keys. Mimic OTP(one time pad) with shorter keys with pseudorandom randomness.

$K=\{0,1\}^n$, $\mathcal{M}=\{0,1\}^{l(n)}$, $G:K \to \mathcal{M}$ is a PRG.

$Gen(1^n)$: $k\gets \{0,1\}^n$; output $k$.

$Enc_k(m)$: $r\gets \{0,1\}^{l(n)}$; output $G(k)\oplus m$.

$Dec_k(c)$: output $G(k)\oplus c$.

Proof of security:

Let $m_0,m_1\in \mathcal{M}$ be two messages, and $\mathcal{D}$ is a n.u.p.p.t distinguisher.

Suppose $\{K\gets Gen(1^n):Enc_k(m_i)\}$ is distinguished for $i=0,1$ by $\mathcal{D}$ and by $\mu(n)\geq\frac{1}{poly(n)}$.

Strategy: Move to OTP, then flip message.

By hybrid argument, 2 neighboring messages are indistinguishable.

However, $H_0$ and $H_1$ are indistinguishable since $G(U_n)$ and $U_{l(n)}$ are indistinguishable.

$H_1$ and $H_2$ are indistinguishable by perfect secrecy of OTP.

$H_2$ and $H_3$ are indistinguishable since $G(U_n)$ and $U_{l(n)}$ are indistinguishable.

Which leads to a contradiction.

Multi-message secure encryption

$(Gen,Enc,Dec)$ is multi-message secure if $\forall n.u.p.p.t \mathcal{D}$ and for all $n\in \mathbb{N}$, and $q(n)\in poly(n)$.

are list of $q(n)$ messages in $\{0,1\}^n$.

$\mathcal{D}$ distinguishes $Enc_k(\overline{m})$ and $Enc_k(\overline{m}')$ with at most negligble probability.

THIS IS NOT MULTI-MESSAGE SECURE.

We can take $\overline{m}=(0^n,0^n)\to (G(k),G(k))$ and $\overline{m}'=(0^n,1^n)\to (G(k),G(k)+1^n)$ the distinguisher can easily distinguish if some message was sent twice.

What we need is that the distinguisher cannot distinguish if some message was sent twice. To achieve multi-message security, we need our encryption function to use randomness (or change states) for each message, otherwise $Enc_k(0^n)$ will return the same on consecutive messages.

Our fix is, if we can agree on a random function $F:\{0,1\}^n\to \{0,1\}^n$ satisfied that: for each input $x\in\{0,1\}^n$, $F(x)$ is chosen uniformly at random.

$Gen(1^n):$ Choose random function $F:\{0,1\}^n\to \{0,1\}^n$.

$Enc_F(m):$ let $r\gets U_n$; output $(r,F(r)\oplus m)$.

$Dec_F(m):$ Given $(r,c)$, output $m=F(r)\oplus c$.

Idea: Adversary sees $r$ but has no idea about $F(r)$. (we choose all outputs at random)

If we could do this, this is MMS (multi-message secure).

Proof:

Suppose $m_1,m_2,\dots,m_{q(n)}$, $m_1',\dots,m_{q(n)}'$ are sent to the encryption oracle.

Suppose the encryption are distinguished by $\mathcal{D}$ with probability $\frac{1}{2}+\epsilon(n)$.

Strategy: move to OTP with hybrid argument.

Suppose we choose a random function

and

$r_i,u_i\in U_n$.

By hybrid argument, $H_0$ and $H_1$ are indistinguishable if $r_1,\dots,r_{q(n)}$ are different, these are the same.

$F(r_1),\dots,F(r_{q(n)})$ are chosen uniformly and independently at random.

only possible problem is $r_i=r_j$ for some $i\neq j$, and $P[r_i=r_j]=\frac{1}{2^n}$.

And the probability that at least one pair are equal

which is negligible.

Unfortunately, we cannot do this in practice.

How many random functions are there?

The length of description of $F$ is $n 2^n$.

For each $x\in \{0,1\}^n$, there are $2^n$ possible values for $F(x)$.

So the total number of random functions is $(2^n)^{2^n}=2^{n2^n}$.