Introducing SPHINCS: Practical stateless hash-based signatures

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/

Literature on hash-based signatures

I started to collect all the literature related to hash-based signature schemes here. The list is based on the list by Dan Bernstein from http://pqcrypto.org/hash.html. I re-read all the articles and added small summaries of the content that in my eyes is important for hash-based signatures. I also added several articles that I think belong to this list. It is actually interesting what you find if you go through all the old papers. Some problems and ideas I thought about were already solved / proposed in those papers. I also added all patents that I am aware of. Most of them are expired, only one patent covering some ideas that could be used to improve hash-based signature schemes in the random oracle model is not expired, yet. But this one has no connection to XMSS or Sphincs.

If you are interested in hash-based signatures — please have a look. I appreciate any comments or additions.

How to manipulate curve standards: a white paper for the black hat

We know how hard it is for agencies to do their work these days. The Snowden revelations and all the related mistrust… Then researchers finally killed Dual EC. So how should they break encrypted Internet traffic to protect the people from all the various dangers out there?

We present a solution to make life easier for overworked agents. In our paper How to manipulate curve standards: a white paper for the black hat.”  we explain how to manipulate elliptic curve standardization to propose a curve that admits an exclusively known vulnerability. We show that this even works for the most restrictive curve generation procedures (i.e. Brainpool)  found in standards today. 

For more details see the paper or our project page.

XMSS code online

Finally! I managed to clean up the XMSS implementation we used for our benchmarks and put it online. I have to admit it took quite a while but the code also includes an implementation of XMSS^MT, i.e. XMSS with tree chaining and an improved algorithm for distributed signature generation. You find the implementation on the code page.

Blogging

So I decided to start blogging now about new projects, results, papers, and other news; or simply about stuff that I decided not to be important enough to write a whole paper.