4 ms·

>Since collision resistance is a stronger notion of security than preimage resistance and second preimage resistance, achieving collision resistance achieves al

>Since collision resistance is a stronger notion of security than preimage resistance and second preimage resistance, achieving collision resistance achieves all three. Under what assumptions and definitions is this true? For instance the function f(x) = x is not preimage resistant but is very collision resistant. I've never heard the claim that collision resistance implies preimage resistance, although clearly collision resistance implies second-preimage resistance since a second-preimage is a collision.

a785236 9y ago
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 9y 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 http://web.cs.ucdavis.edu/~rogaway/papers/relates.pdf
  - a785236 9y 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.
  - dsacco 9y 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.
dsacco 9y ago
> Under what assumptions and definitions is this true? For strong collision resistance and provisional preimage resistance. For example, a hash function of the form f: {0, 1}^* -> {0, 1}^n is certainly preimage resistant if the domain is at least twice as large as the range. More generally, collision resistance implies preimage resistance up to 2^(n/2) (the birthday bound). In practice hash functions compress the space of inputs to a significantly smaller space of outputs; in an academic setting we divide between provisional and strong implications of preimage resistance, but for quantum-resistant hash-based signatures the provisional implication is sufficient. That also means we generally are more heavily prioritizing second preimage resistance and indistinguishability. This might also be helpful: https://crypto.stackexchange.com/questions/34689/how-to-construct-a-collision-resistant-hash-function-that-is-not-a-one-way-funct https://crypto.stackexchange.com/questions/34689/how-to-cons...

a785236 9y ago

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 9y 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 http://web.cs.ucdavis.edu/~rogaway/papers/relates.pdf
- a785236 9y 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.
- dsacco 9y 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.

dsacco 9y ago

> Under what assumptions and definitions is this true? For strong collision resistance and provisional preimage resistance. For example, a hash function of the form f: {0, 1}^* -> {0, 1}^n is certainly preimage resistant if the domain is at least twice as large as the range. More generally, collision resistance implies preimage resistance up to 2^(n/2) (the birthday bound). In practice hash functions compress the space of inputs to a significantly smaller space of outputs; in an academic setting we divide between provisional and strong implications of preimage resistance, but for quantum-resistant hash-based signatures the provisional implication is sufficient. That also means we generally are more heavily prioritizing second preimage resistance and indistinguishability. This might also be helpful: https://crypto.stackexchange.com/questions/34689/how-to-construct-a-collision-resistant-hash-function-that-is-not-a-one-way-funct https://crypto.stackexchange.com/questions/34689/how-to-cons...