Cifratura CPA-sicura da funzioni pseudocasuali

Teorema

<aside> 💡

Se $F$ è pseudocasuale allora la costruzione realizza uno schema di cifratura CPA-sicuro per messaggi di lunghezza $n$

</aside>

Dimostrazione

Sia $\tilde{\Pi}= (\tilde{Gen}, \tilde{Enc}, \tilde{Dec})$ costruito a partire da $\Pi$ tale che

• $\tilde{\Pi}$ usa $f \in Func_n$ scelta unif a caso
• $\Pi$ usa $F_k$ dove $k$ è scelta unif a caso

$\forall$ Adv $A$ PPT sia il polinomio $q(n)$ lim sup al num di query che $A(1^n)$ rivolge al suo oracolo per la cifratura

<aside> 💡

Distinguisher $D$

1. Esegue $A(1^n)$, quando $A$ interroga il suo oracolo di cifratura su un $m \in \{0,1\}^n$ risponde così:
   1. sceglie $r \in \{0,1\}^n$ uniforme
   2. interroga $O(r)$ e ottiene $y$
   3. restituisce $<r,y \oplus m>$ ad $A$
2. Quando $A$ dà in output $m_0,m_1 \in \{0,1\}^n$, sceglie $b \in \{0,1\}$ uniforme e poi:
   1. sceglie $r \in \{0,1\}^n$ uniforme
   2. interroga $O(r)$ e ottiene $y$
   3. restituisce $<r,y \oplus m_b>$ ad $A$
3. Continua a rispondere alle query finché $A$ restituisce $b'$: se $b'=b$ dà in output $1$, altrimenti $0$ </aside>

Analisi

$D$ computa in tempo polinomiale poiché $A$ computa in tempo polinomiale, inoltre:

1. se l’oracolo di $D$ contiene al suo interno una funzione pseudocasuale

   Vista di $A$ come subroutine di $D=$ Vista di $A$ in $PrivK_{A,\Pi}^{cpa}(n)$

   $\Rightarrow$ $Pr_{k \leftarrow \{0,1\}^n} [D^{F_k(\cdot)}(1^n)=1]=Pr[PrivK_{A,\Pi}^{cpa}(n)=1]$

2. se l’oracolo di $D$ contiene al suo interno una funzione casuale

   Vista di $A$ come subroutine di $D=$ Vista di $A$ in $PrivK_{A,\tilde{\Pi}}^{cpa}(n)$

   $\Rightarrow$ $Pr_{f \leftarrow Func_n} [D^{f(\cdot)}(1^n)=1]=Pr[PrivK_{A,\tilde\Pi}^{cpa}(n)=1]$

Ma $F$ è PRF quindi $\exist$ $negl(n)$ tale che: $|Pr_{k \leftarrow \{0,1\}^n} [D^{F_k(\cdot)}(1^n)=1]-Pr_{f \leftarrow Func_n} [D^{f(\cdot)}(1^n)=1]| \leq negl(n)$ $\iff$ $|Pr[PrivK_{A,\Pi}^{cpa}(n)=1]- Pr[PrivK_{A,\tilde\Pi}^{cpa}(n)=1]| \leq negl(n)$

Pertanto possiamo analizzare lo schema ipotetico

Successo di $A$ nello schema ipotetico

Ogni volta che un messaggio $m$ viene cifrato in $PrivK_{A,\tilde\Pi}^{cpa}(n)$ viene scelto un $r \in \{0,1\}^n$ uniforme ed il cifrato risulta $<r,f(r) \oplus m>$

Sia $r^$ la stringa usata per produrre il cifrato di sfida, cioè $c^:= <r^,f(r^) \oplus m_b >$

Possono verificarsi due casi: