# Stateless hash based public key cryptography?

Merkle-Winternitz signatures based on fractal hash trees are an attractive alternative to other post-quantum cryptographic schemes, in particular since they are conceptually simple, the security properties are easily understood and they are easy to implement correctly.

However, all schemes based on Merkle trees appear to be stateful, in the sense that the signer must keep track of the number of signatures already generated, and because some optimizations make it significantly impractical to generate several signatures in parallel. This is a huge minus e.g. for server authentication, where the same key might have to be used for several connections in parallel.

Furthermore, stateful private keys are vulnerable to server crashes if the private key state is not immediately persisted (which further increases stalls from serialized signing). Randomized schemes (such as DSA/ECDSA), or schemes based on trap door functions rather than one way functions (such as RSA) do not have these problems.

Does there exist any public key scheme based solely on hash function that does not require a stateful private key?

• [tahoe-dev] Hash based Signatures for Tahoe LAFS. Seems to contain a working implementation of one of those unlimited tree signature schemes. If you like Merkle Trees you should talk to the TahoeLAFS people. – CodesInChaos Apr 22 '14 at 9:36
• The tahoe-LAFS construction was refined and resulted in the following paper: eprint.iacr.org/2014/795 – mephisto Nov 25 '14 at 10:57
• I bet you´re already aware of its existence, but since it hasn´t been mentioned around here yet… there´s also “SPHINCS: practical stateless hash-based signatures” – with a construction that allows building a stateless quantum-secure hash-based signature scheme with practical speed and sizes. It has been designed to provide long-term $2^{128}$ security. If my brain doesn´t fail me, it was introduced Oktober 2014 and part of the presentations at EUROCRYPT 2015. Here´s the related paper (PDF). – e-sushi Apr 23 '15 at 13:26

You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say). Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message. As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a collision is unlikely.

It takes some extra work to make this work. In particular, if your tree used only hash functions, then to precompute the public key, you'd have to do $2^{80}$ work to populate the entire tree -- no good. So, in fact we do a multi-level tree where the entries at one level are used to sign a subtree the next level down (signed, using Merkle-Winternitz signatures).

For more details on how to make this work, you can see, e.g., https://www.imperialviolet.org/2013/07/18/hashsig.html or https://www.cdc.informatik.tu-darmstadt.de/reports/reports/BDKOV07.pdf.

This does increase the size of signatures and the amount of computation needed a bit, but if you want a stateless scheme, it might be viable.

• Could you please expand a bit on the details? Clearly, with this approach you would still have to save all sub-trees in your fractal, because you can't rule out the possibility you might have to revisit them later. (If you could rule out that possibility, you would only need the top level tree, but then you would still have to save all nodes of that tree.) – Henrick Hellström Apr 21 '14 at 18:15
• @HenrickHellström, the blog post (the first URL) has some more details. We save only the first level -- that's generated during key generation and treated as part of the private key. We regenerate the subtrees on the fly as needed. How are they generated? They can be generated via a GGM construction from a seed (e.g., computed as a PRF of some master key that's part of the private key, plus an identifier that identifies which subtree we're looking at). There's no need to save the subtrees, since they can be generated deterministically on demand as needed. Does that answer your questions? – D.W. Apr 21 '14 at 20:03
• Indeed, thanks. Using a seeded deterministic PRF for the private keys will make it possible to recreate everything. I think it requires careful balancing of the parameters to get acceptable performance, though. Using a ten level fractal of hash trees with $2^8$ leaf nodes seems feasible. – Henrick Hellström Apr 21 '14 at 23:33

Yes, a stateless hashbased signature method called Sphincs was recently proposed. It works by having a moderately large Merkle tree (similar to what D.W. suggested), but instead of using Lamport or Winternitz one time signatures at the bottom, it uses a hash based few-time signature method; this allows an occasional collision at the very bottom of the tree. This allows them to pick indices randomly, but not have the tree so huge that collisions never happen; they just need to be rare enough.

The one downside to Sphincs is the signature size, which is about 40k.

Here's something similar but completely different: a “one-way” cryptographic hash function which is regressible when combined with the function's parsed trapdoor index. That is to say, the hash function is the file and the trapdoor table file is the key! The trapdoor table generated is approximately 60% larger than the original file but eminently compressible.