Hash-based digital signatures (almost) from scratch

https://medium.com/@georgwiese/hash-based-digital-signatures-almost-from-scratch-da57e54dd774

by georgwiese • 4 years ago

69 6 4 years ago

gtrevorjay• 4 years ago

I was part of a project that knew this siren song well. Here's our Swift implementation:

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.

refset• 4 years ago

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.

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

snissn• 4 years ago

I’m lost early in the article - it reads like you’re publishing your private key?

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.

dandanua• 4 years ago

1. You publish two pairs (0, h(x0)), (1, h(x1)). It's your public key.

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.

quesomaster9000• 4 years ago

Somewhat, refer to https://en.wikipedia.org/wiki/Lamport_signature as a starting point.

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.

JanisErdmanis• 4 years ago

A big problem seems to be that the signatures are growing as the public key ages. After Merkle tree leaves are full, the remaining one would be used to sign the next Merkle tree, and when that is full, the next one. Thus verifying an aged public key signature would require verifying the signature chain, which authenticates the current Merkle root.

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?

Hash-based digital signatures (almost) from scratch

Related Stories