Paper 2022/1730

Merkle Tree Ladder Mode: Reducing the Size Impact of NIST PQC Signature Algorithms in Practice

Andrew Fregly, Verisign Labs
Joseph Harvey, Verisign Labs
Burton S. Kaliski Jr., Verisign Labs
Swapneel Sheth, Verisign Labs

We introduce the Merkle Tree Ladder (MTL) mode of operation for signature schemes. MTL mode signs messages using an underlying signature scheme in such a way that the resulting signatures are condensable: a set of MTL mode signatures can be conveyed from a signer to a verifier in fewer bits than if the MTL mode signatures were sent individually. In MTL mode, the signer sends a shorter condensed signature for each message of interest and occasionally provides a longer reference value that helps the verifier process the condensed signatures. We show that in a practical scenario involving random access to an initial series of 10,000 signatures that expands gradually over time, MTL mode can reduce the size impact of the NIST PQC signature algorithms, which have signature sizes of 666 to 7856 bytes with example parameter sets, to a condensed signature size of 472 bytes per message. Even adding the overhead of the reference values, MTL mode signatures still reduce the overall signature size impact under a range of operational assumptions. Because MTL mode itself is quantum-safe, the mode can support long-term cryptographic resiliency in applications where signature size impact is a concern without limiting cryptographic diversity only to algorithms whose signatures are naturally short.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Topics in Cryptology – CT-RSA 2023
Post-Quantum CryptographyDigital SignaturesMerkle TreesModes of Operation
Contact author(s)
afregly @ verisign com
bkaliski @ verisign com
2023-05-01: revised
2022-12-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andrew Fregly and Joseph Harvey and Burton S. Kaliski Jr. and Swapneel Sheth},
      title = {Merkle Tree Ladder Mode: Reducing the Size Impact of NIST PQC Signature Algorithms in Practice},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1730},
      year = {2022},
      doi = {10.1007/978-3-031-30872-7_16},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.