Cifratura sicura con un PRG per messaggi di lunghezza fissa

Teorema

<aside> 💡

Se $G$ è un PRG la costruzione realizza uno schema di cifratura a chiave privata per messaggi di lunghezza fissa che ha cifrati indistinguibili in presenza di un eavesdropper

</aside>

Dimostrazione

Facciamo vedere che per ogni Adv $A$ PPT esiste una funzione trascurabile $negl(n)$ tale che $Pr[PrivK_{A, \Pi}^{eav} (n) = 1] \leq \frac{1}2 + negl(n)$

Costruiamo $D$ che distingue $G(k)$ da $r$ utilizzando $A$ e la sua abilità nel capire quale messaggio tra $m_0$ ed $m_1$ è stato cifrato

<aside> 💡

Distinguisher $D$

Input $\omega \in \{0,1\}^{l(n)}$

1. esegue $A(1^n)$ per ottenere $m_0,m_1 \in \{0,1\}^{l(n)}$
2. sceglie uniformemente $b \in \{0,1\}$ e pone $c:=m_b\oplus \omega$
3. dà $c$ ad $A$ ed ottiene da $A$ il bit $b'$
4. se $b'=b$ dà in output $1$, altrimenti dà in output $0$ </aside>

• Osservazioni

Al fine di analizzare $D$ definiamo lo schema $\tilde{\Pi} = (\tilde{Gen}, \tilde{Enc}, \tilde{Dec})$ → è esattamente OTP: $\tilde{Gen}(1^n)$ riceve in input il parametro di sicurezza $n$ e dà in output una chiave uniforme $k \in \{0,1\}^{l(n)}$

La segretezza perfetta di $\tilde{\Pi} \Rightarrow Pr[PrivK_{A, \tilde{\Pi}}^{eav}(n) = 1] = \frac{1}2$

Ora segue che:

1. se $\omega$ è una stringa uniforme in $\{0,1\}^{l(n)}$ allora
   • la vista di $A$ quando eseguito come subroutine da $D=$ la vista di $A$ in $PrivK_{A, \tilde{\Pi}}^{eav}(n)$
   • poiché $D$ dà in output $1$ quando $A$ ha successo risulta $Pr_{\omega \leftarrow \{0,1\}^{l(n)}}[D(\omega) = 1]= Pr[PrivK_{A, \tilde\Pi}^{eav}(n) = 1] = \frac{1}2$
2. se invece $\omega = G(k)$, dove $k$ è una stringa uniforme in $\{0,1\}^n$ allora
   • la vista di $A$ quando eseguito come subroutine da $D=$ la vista di $A$ in $PrivK_{A, \Pi}^{eav}(n)$
   • poiché $D$ dà in output $1$ quando $A$ ha successo risulta $Pr_{k \leftarrow \{0,1\}^{n}}[D(G(k)) = 1]= Pr[PrivK_{A, \Pi}^{eav}(n) = 1]$

Se risultasse $Pr[PrivK_{A, \Pi}^{eav}(n)=1] = \frac{1}2 + non\text{-}negl(n)$ allora $|Pr[PrivK_{A,\tilde \Pi}^{eav}(n) = 1]-Pr[PrivK_{A, {\Pi}}^{eav}(n) = 1]|$ $= |\frac{1}2 -(\frac{1}2 + non\text{-}negl(n))| = non\text{-}negl(n)$, cioè $|Pr_{\omega \leftarrow \{0,1\}^{l(n)}}[D(\omega) = 1]-Pr_{k \leftarrow \{0,1\}^{n}}[D(G(k)) = 1]| = non \text{-}negl(n)$

Dunque $D$ è PPT e distingue con probabilità $non\text{-}negl(n)$, ma $G$ per ipotesi è un PRG, pertanto non può essere

Deve esistere $negl(n)$ tale che $|Pr_{\omega \leftarrow \{0,1\}^{l(n)}}[D(\omega) = 1]-Pr_{k \leftarrow \{0,1\}^{n}}[D(G(k)) = 1]| \leq negl(n)$ che implica $Pr[PrivK_{A, \Pi}^{eav}(n) = 1]\leq \frac{1}2 + negl(n)$