Threshold Lamport signatures can survive with much lower size by compromising on per-signature security level


#1

Consider a Lamport signature scheme where there are 256 participants, and each participant is required to reveal one of eight values that they have committed to (ie. 128 bytes total for a Merkle branch). Given a value with hash H (assume a 768 bit hash), take 3 bits of H and assign them to each user. That user is required to provide the specific value that’s assigned to by the 3 hash bits. Any signature containing at least 170 valid preimages+Merkle branches passes as valid.

If you actually have 170 honest participants, then it’s easy to see how the scheme can succeed. What if one signature is made (with all 256 participants) and you want to forge it? Then, in expectation, only 32 fitting values will be available, so to make a valid signature for a given random specified H’ half the time you need ~158 participants to be colluding (of the ~98 non-colluding, ~12 will on average be available, getting you to 170). If you have 96 colluding participants, then you will only be able to make a signature for ~1 in 2^80 of possible values (ie. cryptographically infeasible, especially if a few rounds of PoW are done on H before using it as a source of query bits).

Hence, the size of a quantum-secure threshold signature is only ~96 bytes per participant for a committee of size 256, if we are willing to accept the ~1/3 slippage in safety (slippage reduces to ~1/5 if we increase from 96 bytes to 128 bytes, and to ~1/7 if we go up to 160 bytes per participant).