Hacker News new | ask | show | jobs
by EthanHeilman 2993 days ago
Rogaway and Shrimpton specifically used collision resistance not implying preimage resistance as an example of the importance of definition and assumptions:

>Informal treatments of cryptographic hash functions can lead to a lot of ambiguity, with informal notions that might be formalized in very different ways and claims that might correspondingly be true or false. Consider, for example, the following quotes, taken from our favorite reference on cryptography [..] "collision resistance does not guarantee preimage resistance" - [0]

They go on to show the definitions under which collision resistance does and does not imply preimage resistance.

[0]: http://web.cs.ucdavis.edu/~rogaway/papers/relates.pdf
2 comments
dsacco 2993 days ago
The paper you cite is a good one, but it's actually demonstrating that the person you're responding to is correct (and you two are agreeing). In fact, Rogaway and Shrimpton specifically state that their constructions may appear somewhat contrived; this is because collision resistance does imply provisional preimage resistance, and in the real world it's quite difficult to construct (useful) collision resistance without preimage resistance.

So to answer your original question succinctly: collision resistance implies provisional preimage resistance, which is the setting for most real world hash functions, including post-quantum hash-based signatures.

link
a785236 2993 days ago
You're certainly right that formal definitions are important. However, on this forum, I think informality can be appropriate. Though there are variations and inconsistencies, in the theoretical cryptography community, second preimage resistance is most often formalized as "universal one-wayness" and preimage resistance is formalized as "one-wayness."

I did however was careless when I claimed that shrinking by 1 bit suffices for preimage resistance. The hash function needs to shrink by at least log(n) bits to rule out computationally-bounded adversaries finding preimages.

Also, apologies for the formatting of my OP - I don't post here often.

link