[a785236]

It's true as long as the function f is sufficiently "shrinking." The domain of the function (where the x's live) must be sufficiently larger than its range (where the f(x)'s live). For example, if the domain is size N, a range of size 0.99N is enough to guarantee that collision resistance implies preimage or second-preimage resistance.

Said another way, if there are many collisions and you still* have a hard time finding them (collision resistance), then you can prove that it's also hard to find preimages or second preimages.

Your example, f(x) = x is not shrinking at all: there are no collisions.

A fundamental property of hash functions is that they're shrinking---so much so that it often goes without mention in informal settings. Hash functions are typically defined in two ways: shrinking arbitrary length inputs to a constant length (e.g., n bits to 256 bits) or shrinking arbitrary length inputs by some constant amount (e.g., n bits to n-1 bits, or n/2 bits). Even shrinking by one bit serves to halve the domain, guaranteeing many collisions and ruling out counter-examples like the one you gave.

[EthanHeilman]

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

[dsacco]

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.

[a785236]

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.