Resistenza alle collisioni

In crittografia, la resistenza alle collisioni (in inglese collision resistance) è una proprietà delle funzioni hash crittografiche. In modo informale, una funzione hash $H$ è resistente alle collisioni se è computazionalmente difficile trovare una collisione, ovvero due input distinti $m$ e $m^{\prime }$ tali che $H(m^{\prime })=H(m)$.

Definizione

Sia $n\in \mathbb{N}$ un parametro statistico di sicurezza e sia $𝒦$ un insieme di indici. Una famiglia di funzioni hash $H=\{H_k:\{0,1{\}}^{m(k)}\to \{0,1{\}}^{l(k)}{\}}_{k\in 𝒦}$ è resistente alle collisioni se sono soddisfatte le seguenti condizioni:

1. $\mathrm{\forall }k:m(k)>l(k)$, ovvero $H_k$ comprime la stringa in input
2. Per ogni algoritmo casuale PPT $A$, ogni polinomio $p(\cdot )$ e per valori di $n$ sufficientemente grandi si ha che:

   $\mathrm{P}\mathrm{r}[(m,m^{\prime })\leftarrow (A(k,1^n)):m\ne m^{\prime }\wedge H_k(m)=H_k(m^{\prime })]<\frac{1}{p(n)}$ dove la probabilità è sulla scelta dell'indice $k$ da una distribuzione discreta uniforme su $𝒦$ e sulla casualità di $A$.

Resistenza alla preimmagine secondaria

Una proprietà più debole di resistenza alle collisioni prevede che, per ogni messaggio m sia computazionalmente difficile per un algoritmo $A$ trovare un altro messaggio $m^{\prime }$ tale che $H(m^{\prime })=H(m)$. Per questo motivo, questa proprietà viene chiamata anche resistenza alle collisioni debole.

Bibliografia

• Template:Cita libro