Paper 2022/1730
Merkle Tree Ladder Mode: Reducing the Size Impact of NIST PQC Signature Algorithms in Practice
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
-
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} }