We did it! We finally came up with a construction that allows us to build a stateless 128-bit quantum-secure hash-based signature scheme with practical speed and sizes.

The project was independently started by different groups that found together at some point. In my case Peter Schwabe and myself took a trip to Gizeh after Africacrypt 2013. Lying in a pool, looking at the reflection of the pyramids in a window, Peter asked “what about stateless hash-based signatures”. I told him that in theory we can do this, but constructing a practical scheme? I was quite sceptical. However, some people in Eindhoven and of the Tahoe-LAFS project were already starting first attempts on this. So, we came together et voilà.

Although we headed for 128-bit security in the presence of quantum adversaries and made no use of random oracles in the security reductions, SPHINCS-256 has a signature size of 41 kB. Keys are 1kB each. Considering that, for example, the size of an average web page in the Alexa Top 1000000 is 1.8 MB and Debian packages have an average size of 1.2 MB this is definitely practical. And also the speed is not to bad: We can sign hundreds of messages per second on my laptop.

We also did a bunch of additional things: We analyzed the costs of generic quantum attacks on the used hash function properties, we proposed new fixed input size hash functions, using existing building blocks, we give an exact security reduction, and finally we present a high speed implementation and put the code online. See the paper for more details.

So, have a look at the project page: http://sphincs.cr.yp.to/