Welcome to the resource topic for 2002/066
Title:
Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV
Authors: John Black, Phillip Rogaway, Thomas Shrimpton
Abstract:Preneel, Govaerts, and Vandewalle
considered the 64 most basic ways
to construct a hash function
H:\{0,1\}^*\rightarrow\{0,1\}^n from a block cipher
E:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}^n.
They regarded 12 of these 64 schemes as secure,
though no proofs or formal claims were given.
The remaining 52 schemes were shown to be subject to
various attacks.
Here we provide a formal and quantitative treatment of
the 64 constructions considered by PGV.
We prove that, in a black-box model, the 12
schemes that PGV singled out as secure really \textit{are} secure: we
give tight upper and lower bounds
on their collision resistance.
Furthermore, by stepping outside of
the Merkle-Damgard approach to analysis,
we show that an additional 8 of the 64 schemes
are just as collision resistant (up to a small constant) as the first group
of schemes.
Nonetheless, we are able to differentiate among the 20
collision-resistant
schemes by bounding their security as one-way functions.
We suggest that proving black-box bounds,
of the style given here, is a feasible and useful step
for understanding the security of any
block-cipher-based hash-function construction.
ePrint: https://eprint.iacr.org/2002/066
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .