Hash-Based Cryptosystems

Overview

Hash-based cryptography makes use of cryptographic hash functions in order to provide digital signatures whose security relies on the collision resistance of the underlying hash function. The major advantage of these kinds of signature schemes is their flexibility since they can be constructed on any secure hash function. The most fundamental approaches are one-time signature (OTS) schemes, such as Lamport-Diffie signatures (LD-OTS) (Leslie Lamport (1979)Leslie Lamport. Constructing digital signatures from a one-way function. Menlo Park, California. Oct 1979.) or Winternitz signature (W-OTS) schemes, that can’t be used more than once to sign and verify a document securely.

This means that each key can only be used once to sign one single message, thus a new public key must be published for each message to be signed. However, this disadvantage can be circumvented by applying Merkle authentication trees to one-time signature schemes. Its construction combines OTS with a binary hash tree structure that is applied to many OTS verification keys and publishing the root of the hash tree as a public key instead, thus transforming an OTS into a multi-signature scheme. We introduce the basics of these schemes in the next sections to get a first understanding of the basic construction of hash-based cryptosystems.

However, the original schemes are highly inefficient, but further enhancements to the basic algorithms brought significant improvements in key and signature sizes and optimized signature generation time. Recently, Buchmann et al. (2011)Johannes Buchmann, Erik Dahmen, and Andreas Hülsing. XMSS - a practical forward secure signature scheme based on minimal security assumptions. In Proceedings of the 4th International Conference on Post-Quantum Cryptography, PQCrypto’11, pages 117-29, Berlin, Heidelberg, 2011. Springer-Verlag. introduced the efficient hash-based signature scheme XMSS (eXtended Merkle Signature Scheme) that is based on Merkle’s initial scheme. XMSS was standardized in 2018 as the first post-quantum signature scheme, which is specified in the Internet Standard RFC 8391. The Quantum Resistant Ledger (QRL)Peter Waterland. Quantum resistant ledger (qrl). https://github.com/theQRL/ Whitepaper, 2016. https://github.com/theQRL/Whitepaper. is the first hash-based post-quantum blockchain that makes use of XMSS and whose security is achieved by a Proof-of-Stake algorithm.

Lamport-Diffie one-time signatures

The Lamport-Diffie one-time signature scheme (LD-OTS) was introduced in this paperLeslie Lamport. Constructing digital signatures from a one-way function. Menlo Park, California. Oct 1979.. Its security strength relies on the irreversibility of an arbitrary one-way function

$$\varphi:\{0,1\}^{n} \rightarrow\{0,1\}^{n}.$$

In practice, $\varphi$ is usually realized by a dedicated hash function, although the LD-OTS is secure even if $\varphi$ is not a collision-resistant function.

Key generation, signature generation, and verification

A Lamport-Diffie signature consists of a one-way function

$$\varphi:\{0,1\}^{n} \rightarrow\{0,1\}^{n}$$

together with a cryptographic hash function

$$H:\{0,1\}^{*} \rightarrow\{0,1\}^{n}.$$

According to Buchmann (2013Johannes Buchmann. Introduction to Cryptography. Undergraduate Texts in Mathematics. New York, 2013. Springer., 2016Johannes Buchmann. Einführung in die Kryptographie. Springer-Lehrbuch. Berlin Heidelberg, 2016. Springer), the LD-OTS key pair generation, signature generation, and verification process for a message $m$ of bit-length $n$ is given as follows: