What kind of signature for a post-Quantum world? posted December 2015

What kind of signature should we choose for the future ?

PQCrypto's initial recommendation, published 3 months ago, recommend using hash-based signatures.

Hash-based signatures, or Merkle signatures

The Merkle signature scheme is a digital signature scheme based on hash trees (also called Merkle trees) and one-time signatures such as the Lamport signature scheme. It was developed by Ralph Merkle in the late 1970s and is an alternative to traditional digital signatures such as the Digital Signature Algorithm or RSA.

Reading the SPHINCS whitepaper (a hash-based signature), we can understand a bit more why hash-based signatures were considered by PQCrypto to replace our current quantum weak signatures.

– RSA and ECC are perceived today as being small and fast, but they are broken in polynomial time by Shor’s algorithm. The polynomial is so small that scaling up to secure parameters seems impossible.
– Lattice-based signature schemes are reasonably fast and provide reasonably small signatures and keys for proposed parameters. However, their quanti- tative security levels are highly unclear. It is unsurprising for a lattice-based scheme to promise “100-bit” security for a parameter set in 2012 and to correct this promise to only “75-80 bits” in 2013. Fur- thermore, both of these promises are only against pre-quantum attacks, and it seems likely that the same parameters will be breakable in practice by quantum computers.
– Multivariate-quadratic signature schemes have extremely short signatures, are reasonably fast, and in some cases have public keys short enough for typical applications. However, the long-term security of these schemes is even less clear than the security of lattice-based schemes.
– Code-based signature schemes provide short signatures, and in some cases have been studied enough to support quantitative security conjectures. How- ever, the schemes that have attracted the most security analysis have keys of many megabytes, and would need even larger keys to be secure against quantum computers.

A series of post on hash-based signatures is available here