Hash-based digital signatures (almost) from scratch
medium.com
medium.com
Now, let's build a one-time signature scheme that allows you to sign a one-bit message: Choose two random inputs, % and %,. These make up our secret key. • Publish h(%) and h(x). This is our public key. To sign bit o, publish %; to sign bit 1, publish x.
2. You publish h(x0) if you want to sign 0.
3. You publish x0 if you want to verify it. Your public key is unusable after that.
The extension using Merkle trees shows that you can open all of the on-bits in a message, where your public key is the Merkle tree root and your signature is the N authentication paths for all the 1s in the message bitstream, the average signature size will be `n/2 * log2(n) * n` bits. Of course this is fragile and the same public key (merkle tree root) cannot be used to open multiple messages - hence each signature includes the next public key and thus requires knowledge of the sequence/state of the signer which is not ideal and why Lamport signatures aren't really practical.
Winternitz signatures are fascinating because they're secure while still being within the reach of most programmers and--as the article points out--they're quantum safe.
We never got around to implementing the Merkle tree portion because while it saved space it added more complication and still didn't quite solve the "one time" issue. Instead, we implemented a simple blockchain. Users would sign a block containing the signature of the content they wanted to sign and their next key. Again, within the capabilities of most coders to verify themselves, which was the goal.
Absolutely agreed, Winternitz is very approachable!
At one point ~10 years ago I was particular enamoured by this "Dahmen-Krauß Hash-Chain Signature Scheme" (DKSS) built on top of Winternitz. It is a stateful scheme optimised for signing small messages...appropriate for things like lightweight sensor networks (e.g. 8-bit sensor readings), but I was imagining possibly also for quantum-proof p2p systems based on replicating event logs :)
https://web.archive.org/web/20110401080052/https://www.cdc.i...
...and from there I learned about "hash chain traversal" algorithms which are slightly trickier to reason about, but still within reach of a casual programmer.
At the time this really felt orders of magnitude less intimidating than any other options for adding post-quantum signatures to my JavaScript app :P
I wonder if this would be the only signature primitive, how the internet infrastructure could have worked out. Having a large number of leaves for a Merkle tree seems a prerequisite. But then, to limit verifying aged keys, some form of key renewal authorities would be needed, which would be trusted by verifiers. But at that point, would it be better to use MACs?