Introduction

Overview

Public-key cryptography is essential for any blockchain in a permissionless setting in order to guarantee secure transactions in purely peer-to-peer systems. Although the development of quantum computers today is still in its infancy, the advances in quantum computing represent a threat to the current cryptographic schemes. The security of applications of public-key cryptography, in particular of practical digital signature algorithms such as RSA, DSA, and ECDSA, relies on the assumption that specific number-theoretic problems, namely the difficulty of prime factorization and the discrete logarithm problem, are hard in classical computation models, i.e., are intractable for current conventional computers.

However, these schemes will be broken once large-scale quantum computers become a reality since efficient quantum algorithms for their underlying problems are known. More precisely, Shor (1997)Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484-509, October 1997 . introduced algorithms for composite integer factorization and computing discrete logarithms, which was subsequently further developed for implementation by Proos and Zalka (2003)John Proos and Christof Zalka. Shor’s discrete logarithm quantum algorithm for elliptic curves. Quantum Info. Comput., 3(4):317-44, July 2003 for elliptic curves, which work in polynomial-time and thus effectively break RSA, DSA, and ECDSA. Furthermore, Grover (1996)Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC’96, pages 212-19, New York, NY, USA, 1996. ACM. presented a quantum search algorithm that provides a quadratic speed-up over classical algorithms and hence is weakening the security level of hash functions.

Cryptocurrencies such as Bitcoin use classical public-key schemes to sign and validate their transactions in the network. Since these schemes are considered to be vulnerable to quantum attacks, quantum computers are a serious threat to financial applications that are based on blockchains since an adversary might hijack transactions, get access to the accounts in order to steal the funds, or gain an unfair advantage over the Proof-of-Work process, which allows them to launch a double-spending attack and thus to undermine the integrity of the ledger, resulting in a total compromise of the security of the whole system. The demand for quantum-resistant signature and consensus algorithms opened up a new field of research that’s widely referred to as postquantum cryptography, which deals with the search for cryptosystems that remain secure under the assumption that an adversary is in possession of a large-scale quantum computer.

Fortunately, there are existing quantum-safe primitives that open the possibility to construct quantum-resistant signature schemes around them. A milestone was the first standardization of the post-quantum signature scheme XMSS in 2018, which is specified in the Internet Standard RFC 8391. The first blockchains that apply post-quantum approaches were recently launched, such as the Quantum Resistant Ledger (QRL)Peter Waterland. Quantum resistant ledger (qrl). https://github.com/theQRL/ Whitepaper, 2016. https://github.com/theQRL/Whitepaper. which is based on XMSS, and IOTASerguei Popov. The tangle. https://www.iota.org/research/academic-papers, apr 2018. https://www.iota.org/research/academic-papers., which makes use of Winternitz OTS.

In this chapter

In this section, we’ll introduce the major cryptographic primitives that are considered to be quantum-safe and compare their efficiency and usability for blockchain networks. Finally, we’ll introduce the basics of hash-based signature schemes, an approach that’s already implemented in the first quantum-proof blockchain applications.

Chapter structure