In crittografia, la resistenza alle collisioni (in inglese collision resistance) è una proprietà delle funzioni hash crittografiche. In modo informale, una funzione hash
è resistente alle collisioni se è computazionalmente difficile trovare una collisione, ovvero due input distinti
e
tali che
[1].
Sia
un parametro statistico di sicurezza e sia
un insieme di indici. Una famiglia di funzioni hash
è resistente alle collisioni se sono soddisfatte le seguenti condizioni:
, ovvero
comprime la stringa in input
- Per ogni algoritmo casuale PPT
, ogni polinomio
e per valori di
sufficientemente grandi si ha che:
dove la probabilità è sulla scelta dell'indice
da una distribuzione discreta uniforme su
e sulla casualità di
.
Una proprietà più debole di resistenza alle collisioni prevede che, per ogni messaggio m sia computazionalmente difficile per un algoritmo
trovare un altro messaggio
tale che
. Per questo motivo, questa proprietà viene chiamata anche resistenza alle collisioni debole[2][3].
- ^ Venturi, p. 83.
- ^ (EN) Ralph Merkle, One Way Hash Functions and DES (PDF), CRYPTO 1989, Springer, 1990, pp. 428-446, DOI:10.1007/0-387-34805-0_40.
- ^ (EN) Phillip Rogaway e Thomas Shrimpton, Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance (PDF), FSE 2004, pp. 371-388, DOI:10.1007/978-3-540-25937-4_24.