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 49,856 bytes with example parameters at various security levels, to a condensed signature size of 248 to 472 bytes depending on the selected security level. 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.

Note: This article is an expanded version of a contribution to CT-RSA 2023. The changes from the contribution include (a) incorporating the appendices from the prior version of this ePrint, updated for consistency; (b) referencing additional related work; and (c) minor editorial changes. The Version of Record of this contribution was first published in Topics in Cryptology – CT-RSA 2023, Lecture Notes in Computer Science, vol 13871, pp 415-441, 2023 by Springer Nature, and is available online at https://doi.org/10.1007/978-3-031-30872-7_16