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'$ tali che $H(m')=H(m)$.

Definizione

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

1. $\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 {Pr} [(m,m')\gets (A(k,1^{n})):m\neq m'\land H_{k}(m)=H_{k}(m')]<{\frac {1}{p(n)}}$ dove la probabilità è sulla scelta dell'indice $k$ da una distribuzione discreta uniforme su ${\mathcal {K}}$ 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'$ tale che $H(m')=H(m)$. Per questo motivo, questa proprietà viene chiamata anche resistenza alle collisioni debole.

Bibliografia

• Daniele Venturi, Crittografia nel Paese delle Meraviglie, collana UNITEXT, Springer Milan, 2012, DOI:10.1007/978-88-470-2481-6, ISBN 978-88-470-2480-9.