Score:3

# What hash based digital signature algorithms exist that have reasonably small signature sizes?

What hash based digital signature algorithms exist that have reasonably small signature sizes?

• By reasonably small, I mean not much bigger than what you would get with a 256-bit ECDSA (which I believe has a signature of about 64 bytes). If nothing close exists, then what's the smallest signature size I can get?

• I want 128 bit security or better (although its not a hard requirement).

• I will be signing blocks of data that are 128 bytes or smaller.

• Efficiency of computing the keys or signature is not a major factor, just as long as it doesn't take more than say a minute or two to do either for a 128 byte block.

• The signature scheme doesn't need to be widely-used, standardized by any authoritative body, or compatible with any other systems. I only require that copies of my own code to be able to generate and verify the signatures. So for example, something from a peer reviewed research paper is acceptable.

• Lets assume that I only want to issue around 10~20 signatures and then throw away the private key forever.

Schemes based on Merkle trees would seem to be excluded because one has to include a lot of hashes for the authorization nodes. And that tends to make the signature much larger (many thousands of bits).

A Merkle tree supporting 16 signatures (so withing your range) would only have height 4. So if the signature scheme can be stateful it shouldn't be that bad.
@Maeher The plan would be for one person to click a button and sign a whole batch of items at once to prove they all came from the same source. After that the private key gets thrown out. So there shouldn't be a need to track state for longer that it takes the program to run after the button press.
Score:3

Well, I figure that if you really trim things down [1], you could get the signature down to just under 100 bytes. Here are how I adjusted your requirements:

• I want 128 bit security or better (although its not a hard requirement).

Since you said it wasn't a hard requirement, I reset that to 80 bits security (if you do this with 128 bit security, you get a signature of about 200 bytes). By targeting 80 bits security, we can use 80 bit hashes (for example, SHA-256 truncated to 80 bits - we could try to use a faster hash function with a lesser security level, however that speeds things up by only a modest factor, so I don't expect that buys us much).

• I will be signing blocks of data that are 128 bytes or smaller.

Not an issue

• The signature scheme doesn't need to be widely-used, standardized by any authoritative body, or compatible with any other systems.

Nobody is insane enough to standardize this approach

• Efficiency of computing the keys or signature is not a major factor, just as long as it doesn't take more than say a minute or two to do either for a 128 byte block.

Well, computing the public key is the long pole here, so I'll take a 2 minute limit on that. However, you didn't say what the hardware was, so I'll assume decently aggressive hardware there - 8 fast cores with AVX512 hardware (actually, we could go more aggressive with dedicated hardware, however that wouldn't allow us to shrink the signature that much)

• Lets assume that I only want to issue around 10~20 signatures and then throw away the private key forever.

I'll assume that 20 signatures is the max (a max of 16 would allow us to reduce the signature size by another 10 bytes).

Ok, here's what we do: we start with an LMS/XMSS design (either modifying LMS to allow a larger W factor, or removing the bitmasking of XMSS and stir in the location another way); then:

• We have a target of 20 signatures; this implies a Merkle height of 5 (which we would be able to trim back to 4 if we could assume a maximum of 16 signatures)

• A measurement on my Xeon processor shows that a single core can, with its AVX2 instructions, compute 6.6M hashes per second; if we were to use a faster processor with AVX512 instructions, we could probably get that up to 20M hashes per second. We have 8 cores, and we have 120 seconds to compute keys, so we have time to compute not quite 20 billion hashes.

• Now, we need to generate 20 one-time-signature public keys [2] (and everything else is comparatively trivial) - so, we have time for almost 1 billion hashes per one-time-signature

• If we use a Winternitz value of $$W \approx 200,000,000$$, that would allow us to encode about 27 bits. Now, the hash that the one-time signature signs is 80 bits; that means that, with constant sum encoding, we should easily generate 4 base-200,000,000 digits (method; feed the value being signed into SHAKE; generate 3 base-200,000,000 digits; see if there is a fourth digit such that the sum is the target; if not, then go back and generate more digits)

• Actually, because computing individual winternitz chains is not parallelizable, the timing taken (with the given hardware estimates) would actually be about 2 minutes 40 seconds. I feel that's still within the "[no] more than a minute or two" requirement (and if not, get slightly faster hardware...)

So, the signature would consist of:

• The one-time signature of the hash; 4 hashes of 10 bytes each = 40 bytes

• The authentication path; 5 hashes of 10 bytes each = 50 bytes

• Hash randomizer (which you need to prevent possible collision attacks; this is randomness you stir into the message when you hash it); 40 bits = 5 bytes

• The index (actually, you could drop this, and just have the verifier check all possible indices; I didn't think that a 1 byte savings was worth it); 1 byte

Total: 96 bytes (with a possibility of 86 bytes if you only need to generate 16 signatures)

[1]: Have you seen the movie "The Martian" (or better yet, read the book - it goes into more details)? If so, what I'm doing feels a lot like what Mark Watney did to the MAV...

[2]: For those Merkle leaf nodes that we'll never use, we don't actually have to compute those one-time public keys - instead, we can just put in dummy values. We won't be able to sign with them - we never intend to