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 ${\displaystyle H}$ è resistente alle collisioni se è computazionalmente difficile trovare una collisione, ovvero due input distinti ${\displaystyle m}$ e ${\displaystyle m'}$ tali che ${\displaystyle H(m')=H(m)}$^[1].

Sia ${\displaystyle n\in \mathbb {N} }$ un parametro statistico di sicurezza e sia ${\displaystyle {\mathcal {K}}}$ un insieme di indici. Una famiglia di funzioni hash ${\displaystyle 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. ${\displaystyle \forall k:m(k)>l(k)}$, ovvero ${\displaystyle H_{k}}$ comprime la stringa in input
2. Per ogni algoritmo casuale PPT ${\displaystyle A}$, ogni polinomio ${\displaystyle p(\cdot )}$ e per valori di ${\displaystyle n}$ sufficientemente grandi si ha che:

   ${\displaystyle \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 ${\displaystyle k}$ da una distribuzione discreta uniforme su ${\displaystyle {\mathcal {K}}}$ e sulla casualità di ${\displaystyle A}$.

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

• 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.

Portale Crittografia

Portale Sicurezza informatica