Comment by dsacco | Hacker News Reader

Comment by dsacco | Hacker News Reader

Parent Full thread

This is a pretty good primer, and I think Matt Green is generally good at tutorials that reduce the technical complexity to make material more accessible.

I'll add a couple of notes:

1. Hash-based cryptography is not capable of providing public-key encryption, so unfortunately these are only useful for quantum-resistant digital signature schemes. But they're still very good at that.

2. Since collision resistance is a stronger notion of security than preimage resistance and second preimage resistance, achieving collision resistance achieves all three. I just wanted to make this point explicit. Likewise, indistinguishability is an even stronger notion and subsumes all three.

3. The current state of the art in quantum-resistant hash-based signatures is the SPHINCS family and its variants, including SPHINCS+ and Gravity-SPHINCS [1,2,3]. One of the really interesting innovations here is a transition to trees with few-time signatures instead of one-time signatures underlying them.

A good, reasonably up to date source for a technical overview of the current research landscape is the PQCrypto Conference's 2017 Summer School, specifically the two "Hash-based signatures" videos/slides [4].

____________________

1. https://sphincs.cr.yp.to/papers.html

2. https://sphincs.org/

3. https://research.kudelskisecurity.com/2017/12/01/our-submiss...

4. https://2017.pqcrypto.org/school/schedule.html

>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.

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.

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

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.

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.

> 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-cons...

Unforunately I came back to this long after the edit window, but it occurs to me to clarify #1. One of the reasons we like hash-based signatures despite the fact that hash functions are not versatile for PKE/KEM is because they're very simple and performant.

Hash-based signatures don't require advanced mathematics to understand; an elementary knowledge of discrete probability theory and general complexity theory is sufficient. Contrast this with most proposals for quantum resistant schemes, which require a significant understanding of linear algebra and {group,ring,Galois} theory. In the case of isogeny-based systems, add more number theory and algebraic geometry to that list.

Do you have a citation for number one? I suspect it's true but haven't been able to prove it, and it's been bugging me since it feels like there should be some way of stitching RNGs and mutilated lamport signatures together to achieve encryption or key agreement primitive, even if it is even more unweildy than regular lamport signatures.

Impagliazzo and Rudich proved that one can't build PKE from one-way functions:

https://www.researchgate.net/profile/Russell_Impagliazzo/pub...

Reply on news.ycombinator.com