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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Topics in Cryptology – CT-RSA 2023
DOI
10.1007/978-3-031-30872-7_16
Keywords
Post-Quantum CryptographyDigital SignaturesMerkle TreesModes of Operation
Contact author(s)
afregly @ verisign com
bkaliski @ verisign com
History
2023-05-01: revised
2022-12-15: received
See all versions
Short URL
https://ia.cr/2022/1730
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1730,
      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{https://eprint.iacr.org/2022/1730}},
      url = {https://eprint.iacr.org/2022/1730}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.