Preneel, Govaerts och Vandewalle [7] ansåg de 64 mest grundläggande sätten att konstruera en hashfunktion H: {0, 1} * → {0, 1} n från ett block chiffer E: {0, 1} n × {0, 1} n → {0, 1} n. De betraktade 12 av dessa 64 system som säkra, även om inga bevis eller formella anspråk gavs. De återstående 52 planerna visade sig utsättas för olika angrepp. Här ger vi en formell och kvantitativ behandling av de 64 konstruktioner som PGV överväger. Vi bevisar att i en svart låda modell är de 12 system som PGV valt ut som säkra verkligen säkra: vi ger snäva övre och nedre gränser på deras kollisionsmotstånd. Genom att gå utanför Merkle-Damgårds strategi för analys visar vi dessutom att ytterligare 8 av de 64 systemen är lika kollisionsresistenta (upp till en liten konstant) som den första gruppen system. Trots detta kan vi skilja mellan de 20 kollisionssäkra systemen genom att begränsa deras säkerhet som enkelriktade funktioner. Vi föreslår att bevisa svart-box gränser, av den stil som anges här, är ett genomförbart och användbart steg för att förstå säkerheten i alla block-chiffer-baserade hash-funktionskonstruktion.
Svart, Rogaway och Shrimpton REF gav en formell och kvantitativ behandling av alla PGV-komprimeringsfunktioner.
Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV
{'venue': 'CRYPTO', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}