Vi bevisar existensen av ett orakel relativt som det finns seveial välkända kryptografiska primitiver, inklusive enkelriktade permutationer, men utesluter (för en lämpligt stark definition) kollision-indragbara hash funktioner. Således alla bevis för att sådana funktioner kan härledas från dessa svagare primitiva är nödvändigtvis icke-relativiserande; i synnerhet, ingen bevisbar konstruktion av en kollision-indragbar hash funktion kan existera endast baserat på en "svart låda" enkelriktad permutation. Detta resultat kan ses som ett partiellt rättfärdigande av den vanliga praxisen att behandla den kollisionsindragbara hashfunktionen som en kryptografisk primitiv, snarare än att försöka härleda den från en svagare primitiv (t.ex. en enkelriktad permutation).
Simon REF visar att kollisionssäkra hashfunktioner inte kan konstrueras genom enkelriktade funktioner via en reduktion av svarta lådor.
Finding Collisions on a One-Way Street: Can Secure Hash Functions be Based on General Assumptions
{'venue': 'EUROCRYPT', 'journal': None, 'mag_field_of_study': ['Computer Science']}