Paper 2023/492

Batch Signatures, Revisited

Carlos Aguilar-Melchor, SandboxAQ
Martin R. Albrecht, SandboxAQ
Thomas Bailleux, SandboxAQ
Nina Bindel, SandboxAQ
James Howe, SandboxAQ
Andreas Hülsing, Eindhoven University of Technology
David Joseph, SandboxAQ
Marc Manzano, SandboxAQ

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. For the example of Falcon-512 in TLS, we can increase the amount of connections per second by a factor 3.2x, at the cost of an increase in the signature size by ~14% and the median latency by ~25%, where both are ran on the same 30 core server. We also discuss applications where batch signatures allow us to increase throughput and to save bandwidth. For example, again for Falcon-512, once one batch signature is available, the additional bandwidth for each of the remaining N-1 is only 82 bytes.

Available format(s)
Cryptographic protocols
Publication info
Batch signaturespost-quantum cryptographyPQCTLSHSMPQTLS
Contact author(s)
carlos aguilar @ sandboxaq com
martin albrecht @ sandboxaq com
thomas bailleux @ sandboxaq com
nina bindel @ sandboxaq com
james howe @ sandboxaq com
andreas @ huelsing net
david joseph @ sandboxaq com
marc manzano @ sandboxaq com
2023-04-05: approved
2023-04-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carlos Aguilar-Melchor and Martin R. Albrecht and Thomas Bailleux and Nina Bindel and James Howe and Andreas Hülsing and David Joseph and Marc Manzano},
      title = {Batch Signatures, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2023/492},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.