Batch Signatures, Revisited

We revisit batch signatures (previously considered in a draft RFC and used in multiple recent works), where a single, potentially expensive, “inner” digital signature authenticates a Merkle tree constructed from many messages. We formalise a construction and prove its unforgeability and privacy properties. We also show that batch signing allows us to scale slow signing algorithms, such as those recently selected for standardisation as part of NIST’s post-quantum project, to high throughput, with a mild increase in latency and demonstrate the practical efficiency of batch signing in the context of TLS. For the example of Falcon-512 in TLS, we can increase the amount of connections per second by a factor 3.2, at the cost of an increase in the signature size by 14% and the median latency by 25%; both run on the same 30 core server. For SPHINCS \(^+\) -128, throughput improves by a factor 4.6, with a negligible impact on signature size and an 11% impact on median latency. We also discuss applications where batch signatures allow us to increase throughput and to save bandwidth. For example, again for 16 Falcon-512 signatures, once one batch signature is available, the additional bandwidth for each of the remaining is only 82 bytes.