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 è resistente alle collisioni se è computazionalmente difficile trovare una collisione, ovvero due input distinti e tali che [1].
Definizione
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 .
Resistenza alla preimmagine secondaria
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].
Note
- ^ 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.
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Ambox_padlock_green.svg/25px-Ambox_padlock_green.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Gnome-system-lock-screen.svg/25px-Gnome-system-lock-screen.svg.png)