In crittografia, la resistenza alle collisioni () è 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 ..
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.
Note
Bibliografia
Categoria:Hash crittografici