About the Course

Why cryptocurrencies?

In the age of the Internet, electronic commerce (e-commerce) has become a common method in today’s society. E-commerce includes online purchases, i.e., the electronic transfer of funds to pay for goods and/or services. Since most online payments are based solely on electronic information, difficulties arise when an electronic monetary unit can be used more than once for payment. This is widely known as the double-spending problem. To overcome this problem, many financial transactions are verified, processed, and secured by a financial institution, which acts as a trusted third party.

However, processing fees are unavoidable under this approach, making small transfers expensive. At the same time, it’s impossible to act anonymously because online payments require a bank account that must be registered with a bank, and the account holder may be the registered customer. In 2008, a pseudonym, Satoshi Nakamoto, came up with the idea of an online cash system that would allow transactions without a financial institution. Nakamoto argues as follows:

What is needed is an electronic payment system based on cryptographic proof instead of trust, allowing any two willing parties to transact directly with each other without the need for a trusted third party.

Main idea

The main idea is a cash system that allows irreversible online payments without having to be registered with any financial institution. To implement this, he proposed a version of electronic cash, which is solely based on a peer-to-peer network, allowing a payment system that acts in a fully decentralized manner. An electronic coin is represented by a chain of digital signatures, and the double-spending problem is solved by documenting the transactions usually unencrypted in a public ledger, which is secured by a so-called Proof-of-Work (PoW) mechanism.

PoW ensures that the main ledger is supported by a majority of the participants, and hence a majority of users agree on this version of the truth about the state of the ledger, preventing fraud among participants. This approach is now widely known as blockchain technology.

With the introduction of blockchain technology, Nakamoto’s groundbreaking paper “BitcoinA peer-to-peer electronic cash system. Decentralized Business Review, p.21260. Vancouver : A Peer-to-Peer Electronic Cash System” opened up new possibilities for financial applications. As a result, more and more decentralized systems are following this approach.

Public awareness has not yet allowed for the vulnerability of these systems, regardless of the published academic papers.

In particular, quantum computers could pose a serious threat to blockchain-based systems in the future, as they are known for quantum algorithms that could break present signature schemes, which leads to a loss of corresponding funds. In order to keep blockchain systems secure in the future, new digital signature schemes are required and need to be resistant to quantum computers. Such schemes are said to be quantum-secure or quantum-proof. The introduction of such schemes is essential to maintain security in blockchain technologies in a post-quantum era.

Course objectives

The purpose of this course is to provide a basic introduction to the functionality of blockchain technologies in order to assess their safety. For this, we introduce the relevant mathematical concepts, which are needed to describe the cryptographic primitives used in blockchain technologies. Based on the example of Bitcoin, we’ll show how the system is affected if a cryptographic primitive is broken. We’ll estimate the consequences and outline possible countermeasures in order to keep the system secure.

Course structure

The remainder of this course is structured as follows:

Chapter: Preliminaries gives a general introduction to the mathematical foundations, which are needed to describe the cryptographic primitives used in blockchain-based systems. We will provide the basic number-theoretic and algebraic concepts. This includes a rigorous introduction to group, ring, and field theory, the main result being the properties of finite fields. Finally, we give a short introduction to computational complexity theory, which is later needed to describe the efficiency of algorithms.

In the following Chapter: Cryptographic Primitives, we’ll introduce the cryptographic primitives that are based on number-theoretic concepts. We’ll discuss the major approaches of public-key cryptography, which rely on one-way functions. Such systems are needed in order to provide digital signatures. Furthermore, we’ll introduce hash functions, which are very important for blockchain approaches.

In Chapter: Elliptic Curve Cryptography, we’ll give a general introduction to elliptic curve cryptography in order to describe the Elliptic Curve Discrete Logarithm Problem (ECDLP), on whose hardness the security of elliptic curve cryptosystems is based. We’ll then outline the most common attacks against elliptic curves in order to determine which conditions must be met in order to construct cryptographically secure elliptic curve schemes. Subsequently, we’ll then apply this knowledge to the curve secp256k1, which is used in Bitcoin. In the last step, we’ll show the Elliptic Curve Digital Signature Algorithm (ECDSA), which is used to sign transactions.

We’ll then move to Chapter: Information Security in Software Systems, which gives a general introduction to information security in software systems. We’ll introduce the common technical terms with respect to information security, which includes the classical CIA triad (confidentiality, integrity, availability), and give the standardized definitions of these terms. Furthermore, we’ll introduce the classic attacks against distributed systems, which are the Denial-of-Service (DoS) attack and the Sybil attack. We’ll then explain popular countermeasures against such attacks, which are based on so-called Proof-of-Work mechanisms.

In Chapter: Distributed Systems, distributed systems will be discussed, as common blockchain-based applications rely on such networks in order to achieve decentralized software solutions. For this, we’ll classify the software systems and show their specific properties.

The main result is that decentralized systems need fault tolerance in order to reach a consensus about a common state, which is a nontrivial task because any entity of the system could independently fail in an arbitrary manner. This problem is referred to as the Byzantine Generals Problem, which can’t be solved deterministically, if the system operates in an asynchronous environment, such as the Internet. We’ll summarize the known solutions to this problem and show their complexity.

The following Chapter: Introduction to Blockchain Technology will contain an introduction to blockchain technology in general, based on the knowledge of the previous chapters. In particular, we’ll outline the most important attacks against a blockchain-running system in order to launch a double-spending attack.

Chapter: Bitcoin will then deal with a specific blockchain, namely the Bitcoin ledger. We’ll show the details of the Bitcoin protocol concluding how a Bitcoin transaction works in detail.

In the subsequent chapters, we’ll eventually move into the main part of this course, namely the appearance of quantum computers and their impact on blockchain-based systems.

Chapter: “Introduction to Quantum Computing” chapter will include an introduction to quantum computing, the main result being Shor’s quantum algorithm which will break the present public-key schemes. Additionally, this chapter includes a summary of the impact of quantum computing on present-day cryptography. The major result is that a large-scale quantum computer would be able to break all present public-key schemes.

However, symmetric schemes and hash functions aren’t so vulnerable since they’re not affected by Shor’s algorithm, but are affected by Grover’s algorithm, which only allows a quadratic speed-up over conventional algorithms. Therefore, Grover’s attack can be prevented by simply doubling the key sizes.

In Chapter: Bitcoin Under Broken Crypto Primitives, we’ll then determine the consequences if any cryptographic part of the protocol will be broken by a quantum computer. The main result is that funds can be stolen in this case because breaking the signature automatically yields the private key to the attacker. However, the system’s security functions, which are based on hash functions, will not have a significant effect.

Finally, Chapter: Post-Quantum Blockchain will introduce solutions to quantum attacks, presenting possible post-quantum approaches as code-based, lattice-based, hash-based, and multivariate cryptography. We’ll compare the efficiency and the key sizes of these quantum-safe schemes to classical public-key algorithms, based on the assumption that every scheme achieves a security level of 128 bits. As we can conclude, post-quantum approaches are as efficient as conventional algorithms, but suffer from larger key sizes. We’ll then introduce hash-based signature schemes as an alternative to traditional methods.

The closing chapter, Chapter: In Closing, contains a summary of the results and suggestions for future work.