Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Security/Efficiency Tradeoffs for Permutation-Based Hashing
verfasst von : Phillip Rogaway, John Steinberger
Erschienen in: Advances in Cryptology – EUROCRYPT 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We provide attacks and analysis that capture a tradeoff, in the ideal-permutation model, between the speed of a permutation-based hash function and its potential security. We show that any 2
n
-bit to
n
-bit compression function will have unacceptable collision resistance it makes fewer than three
n
-bit permutation invocations, and any 3
n
-bit to 2
n
-bit compression function will have unacceptable security if it makes fewer than five
n
-bit permutation invocations. Any rate-
α
hash function built from
n
-bit permutations can be broken, in the sense of finding preimages as well as collisions, in about
N
1 −
α
queries, where
N
= 2
n
. Our results provide guidance when trying to design or analyze a permutation-based hash function about the limits of what can possibly be done.