Costruzione

• Gen: $\mathcal G (1^n) \to (G,q,g)$, sceglie $x \in \Z_q$ uniforme e pone $h:= g^x$; $H: G \to \{0,1\}^{l(n)}$, $pk = <G,q,g,h,H>$, $sk= <G,q,g,x>$
• Encaps: su input $pk$, sceglie $y \in \Z_q$ uniforme e restituisce $g^y$ e $H(h^y)$
• Decaps: con input $sk$ e $c \in G$ dà in output $H(c^x)$

Teorema

CDH difficile relativamente a $\mathcal G$ + $H$ ROM $\Rightarrow$ El Gamal KEM CPA-sicuro

Dimostrazione

Consideriamo $KEM_{A, \Pi}^{cpa}$ in cui la chiave pubblica è $<G,q,g,h>$ e il cifrato è $c= g^y$

Sia $Query$ l’evento in cui $A$ chiede l’hash di $h^y$ ad $H$

Abbiamo $Pr[KEM_{A, \Pi}^{cpa}(n)=1] = Pr[KEM_{A, \Pi}^{cpa}(n)=1 \land \overline{Query}] + Pr[KEM_{A, \Pi}^{cpa}(n)=1 \land Query] \leq Pr[KEM_{A, \Pi}^{cpa}(n)=1 | \overline {Query}] + Pr[Query]$

Nell’esperimento $KEM_{A, \Pi}^{cpa}(n)$, $A$ dispone di $<pk,c,\hat k>$ dove $\hat k$ è o $H(h^y)$ oppure un valore casuale

Se l’evento $Query$ non si verifica, per le proprietà del ROM $H(h^y)$ è uniformemente distribuita e quindi per $A$ è completamente indistinguibile da un valore casuale → $Pr[KEM_{A, \Pi}^{cpa}(n)=1|\overline{Query}] = \frac{1}2$ $\Rightarrow$ $Pr[KEM_{A, \Pi}^{cpa}(n)=1] \leq \frac{1}2 + Pr[Query]$

Sia $t$ un limite superiore polinomiale sul numero di query che $A$ effettua ad $H$

<aside> 💡

Algoritmo $A'$

• pone $pk := <G,q,g,h>$ e sceglie $k \in \{0,1\}^l$ uniforme
• esegue $A(pk,c,k)$ e quando $A$ fa una query ad $H$ risponde scegliendo una stringa uniforme di $l$ bit
• al termine dell’esecuzione di $A$, siano $w_1,..,w_t$ le query che $A$ ha fatto ad $H$ $A'$ sceglie $i \in \{1,..,t\}$ e dà in output $w_i$ </aside>

L’evento $Query$ nella simulazione che $A'$ realizza si verifica con la stessa probabilità con cui si verifica nell’esperimento $KEM_{A, \Pi}^{cpa}$ → vista di $A$ come subroutine di $A' \equiv$ vista di $A$ in $KEM_{A, \Pi}^{cpa}(n)$

Pertanto se l’evento $Query$ si verifica allora $h^y \in \{w_1,..,w_t\}$ → $A'$ dà in output il valore corretto con probabilità $\frac{1}t$

Pertanto $Pr[A'(G,q,g,h,c) = h^y] \geq \frac{Pr[Query]}t$

Ma se CDH è difficile relativamente a $\mathcal G$, $\exist$ $negl(n)$ tale che $Pr[A'(G,q,g,h,c)= h^y] \leq negl(n)$

$\Rightarrow$ $Pr[Query] \leq t\cdot negl(n) = negl'(n)$