Saw this on Twitter. Skimread the paper already. First thoughts: This is a <i>nice</i> little construct. 41KB signatures, 1K public keys and 1K private keys, and still <i>relatively</i> speedy - and <i>no state</i>! Glory hallelujah! I thought the notes at CFRG for hash-based signatures were fun but the state of a Merkle signature makes them a pain in the arse to deal with. The possibility to not have to carry around state baggage in a vaguely <i>practical</i> system has really brightened up my evening. I'm going to sit here with some rum and mull over the details.<p>Not sure I'd pick it above Ed25519 or EdDSA over E-521 today, as it's still kind of big and slow by comparison - but compared to its peers, this looks pretty damn good. (Maybe if quantum-security is important to you, you could also use an NTRUSign variant or another lattice-based technique? But ideal lattice schemes, especially signatures, are still relatively unproven and I'm not particularly comfortable with them right now.)<p>If I was looking for a signature scheme I needed to last a few decades, I'd at least give this some careful thought to see if it met my needs. (Some time <i>after</i> the rum, of course.)<p>- - -<p>No, you can't use this to encrypt anything: signatures only. If you don't know the basic theory, a <i>very</i> quick and dirty primer. (Please correct me if I've flubbed a detail, I've already started on the rum. <g>)<p>Hash-based signature, all the way back from Lamport [1979]: Alice makes a secret list of b <i>pairs</i> of random numbers (=private key); publishes hashes of <i>each and every</i> number in that list (=public key). Then (perhaps later) Alice hashes message she wants to sign, then for each bit in the hash of the message, proves which bit it is by publishing either the first or second number out of those pairs <i>and throwing the other one away</i> (important). Done. Bob verifies by following the same process but checking, for each bit, that the hash of the number for that bit matches the <i>correct</i> bit (0 or 1) in Alice's public key. Great! Bob can't forge signatures because he's only got the random numbers which form the hashes for the <i>correct</i> signature. Unless someone can second-preimage the hash, this is quantum-secure.<p>What's the problem with Lamport? Alice only gets to use the key <i>once</i>. If she uses her Lamport key twice or more, she's giving Bob enough information to start having a chance (<i>very quickly</i> an overwhelming chance, especially if Bob gets to choose the messages with an adaptive partial hash preimage attack - i.e. massaging the plaintext to contain partial second-preimage collisions of manageably few bits at a time which are the inverse of Alice's published message hash, which is pretty much the worst-case scenario) to forge her signatures. But if she uses it only once and then throws the others away, that can't happen.<p>Still, a signature scheme you can only use once is pretty, but irritating. One solution? Bung a Merkle hash tree underneath, very broadly speaking: between the root and the leaves, use that to stretch "one time" into "quite a lot of times". The problem? It's stateful, we need to know where in the tree we are. (Also, we can run out of tree.) The concept of needing to count the <i>x</i>th signature and only being able to sign a maximum of <i>y</i> signatures is counterintuitive for those used to other schemes, such as factoring/discrete-log-based signatures. There has been lots of work since the '70s on extending all that however, and a lot of variations, especially since quantum computers started to be able to count to 16, and maybe one day possibly even as high as 20, or even higher - but so far, all the published relatively-practical hash-based signature schemes <i>I've</i> seen are stateful.<p>What's good about this new SPHINCS construct? It's stateless. Also the public and private keys, as well as the signatures are both remarkably small for a hash-based signature, and it's also pretty fast considering, thanks to some nice tuning choices and, it seems, using ChaCha12 as a sponge function?