Costruzione

• Gen: $\mathcal G(1^n) \to (G,q,g)$, sceglie $h \in G$ uniforme e dà in output $s= (G,q,g,h)$
• H: dati $s$ e $(x_1,x_2) \in \Z_q \times \Z_q$ dà in output $H^s(x_1,x_2):= g^{x_1}h^{x_2} \in G$

Nota

Il gruppo deve essere scelto in modo tale che gli elementi del gruppo possano essere rappresentati con $l < 2(n-1)$ bit

Teorema

DL difficile relativamente a $\mathcal G$ $\Rightarrow$ $H$ funzione hash resistente a collisioni di lunghezza fissata

Dimostrazione

Sia $\Pi = (Gen, H)$ e sia $A$ PPT con $Pr[Hash\text{-}coll_{A,\Pi}(n)=1]= \epsilon(n)$

Possiamo usare $A$ per costruire $A'$ che risolve il problema DL con probabilità di successo $\epsilon(n)$

<aside> 💡

Algoritmo $A'$

1. sia $s:= <G,q,g,h>$ seme per $H$, esegue $A(s)$ per cercare collisioni e ottiene $x$ e $x'$
2. se $x \neq x'$ e $H^s(x)=H^s(x')$
   • se $h = 1$ return $0$
   • se $h \neq 1$ interpreta $x$ come $(x_1,x_2)$ e $x'$ come $(x_1', x_2')$ con $x_1,x_2,x_1',x_2' \in \Z_q$ e return $[(x_1-x_1')(x_2'-x_2)^{-1} \text{ mod } q]$ </aside>

Il valore $s$ dato ad $A$ è distribuito esattamente come nell’esperimento $Hash\text{-}coll_{A,\Pi} (n)$, per lo stesso valore del parametro di sicurezza $n$ $\Rightarrow$ con probabilità $\epsilon(n)$ viene prodotta una collisione

$H^s(x_1,x_2) = H^s(x_1', x_2') \iff g^{x_1}h^{x_2}= g^{x_1'}h^{x_2'} \iff(g^{x_1}h^{x_2})g^{-x_1'}h^{-x_2}= (g^{x_1'}h^{x_2'})g^{-x_1'}h^{-x_2} \iff g^{x_1-x_1'} = h^{x_2'-x_2}$

Poiché $q$ è primo, esiste $(x_2'-x_2)^{-1} \text{ mod }q$ $\Rightarrow g^{(x_1-x_1')(x_2'-x_2)^{-1}} = h^{(x_2'-x_2)(x_2'-x_2)^{-1}} = h^1 = h$ $\Rightarrow log_gh= (x_1-x_1')(x_2'-x_2)^{-1}$

Pertanto $A'$ risolve il problema DL con probabilità $\epsilon (n)$, e poiché per ipotesi il problema DL è difficile relativamente a $\mathcal G$, allora $\epsilon(n)$ è trascurabile $\Rightarrow$ $H$ è collision-resistant