Quantum Computing – Blockchain Threat?
One of the most well-known applications of quantum computers is breaking the mathematical difficulty underlying most of currently used cryptography. As cryptography is fundamental to blockchains, we discuss how/if this poses a risk.
Before we begin, it is important to understand some of the types of encryption:
Symmetric Encryption
In symmetric cryptography data is encrypted and decrypted using a single secret cryptography key. This is one of the oldest and widely used encryption techniques. With regard to the encryption of the data, the process is conceptually very simple. If an individual wishes to send an encrypted message they would simply use a secret key to encrypt the file prior to sending. The same key would then be required to decrypt the file on the receiver’s end. Anyone who is in possession of the secret key will also be able to decrypt the message. Note that the message could be encrypted by different means, some examples being one byte at a time (steam cypher) or in units (block cypher). Below are some common types of symmetric encryption:
- Advanced Encryption Standard (AES)
- Data Encryption Standard (DES)
- Triple Data Encryption Stnadard (Triple DES)
The advantages of symmetric encryption is that it can encrypt and decrypt large amounts of data quickly and is easy to implement. The biggest disadvantage is that it is based upon the use of a single secret key.
Asymmetric Encryption
This technique uses mathematically linked public and private key pairs to encrypt and decrypt data. The public-private key pair is generated based on a mathematical principle called a “one-way function”. This principle dictates that the public key can be easily derived from the private key but not the other way around. All known (classical) algorithms used to derive the private key from the public key require an astronomical amount of time to perform such a computation and are therefore not practical.
If two individuals wish to communicate via asymmetric encryption, they will use the recipient’s public key to first encrypt the message and send. The recipient will then use their own ‘private’ key to decrypt the message. Note that in this scenario, the recipient is the only individual who has access to the private key. You can see that for asymmetric encryption, there is no sharing of ‘private’ keys and therefore no risk of any interception of the decryption keys when in transit. The only key which is shared is the public key. Some examples of asymmetric encryption:
- Elliptical Curve Cryptography (ECC)
- Rivest Shamir Adleman (RSA)
The advantage of asymmetric encryption as noted above is the exchange of private keys is not necessary. Additionally, asymmetric encryption also allows individuals to produce a digital signature (using their private key) that can be verified by anyone who has the corresponding public key.
Quantum Computing
Before discussing quantum computing, I shall first touch upon how traditional computing works. Traditional computing is based around binary ‘bits’, i.e. 0’s and 1’s. In quantum computers however, the basic unit of memory is a quantum bit or qubit. I will not delve too deep into the theory of quantum computing as I do not wish to detract from the purpose of this article, however; Qubits are made using physical systems such as the spin of an electron or the orientation of a photon.
- They have a property known as superposition meaning these systems can be in many different arrangements all at once.
- In addition qubits can be linked in such a way that it is impossible to separate, this phenomena is called quantum entanglement.
The results of these properties mean that a series of qubits can represent many different things simultaneously.
The implication of this with regard to computation and storage can be highlighted by the fact that a standard computer can use 8 bits to represent numbers between 0-255. However 8 qubits can be used to represent the same set of numbers (0-255) simultaneously! A few hundred entangled qubits would be enough to represent more numbers than there are atoms in the universe.
Implications of Quantum Computing on Blockchains
Blockchains use the principal of asymmetric cryptography (as defined above). We have learnt that the ‘one-way-function’ dictates that it is appropriately difficult to derive the private key from the public key as this will require astronomical amounts of computing power. However since the publication of the quantum algorithm by Peter Shor in 1994, sufficient quantum computing power will in fact break down this difficulty and thus enable falsifying of digital signatures. With a focus on Bitcoin, we shall assess the types of addresses and the vulnerabilities of each to the quantum computing threat:
- Public key is accessible via the recipient address. This is from a ‘pay to public key’ (p2pk) transaction. This was the dominant address type in the early days of Bitcoin. As the public key can be directly accessed from the address and since all transactions in Bitcoin are public, anyone can obtain the public key from any p2pk address. This exposes all these addresses to attacks from a quantum computer.
- Address is a hash of the public key. As a hash is a one-way cryptographic function, the public key is not directly revealed by the address – ‘pay to public key hash’ (p2pkh). The public key is only revealed the moment the owner wishes to initiate a transaction. This means that as long as funds have never been transferred from a p2pkh address, the public key is not known and the private key cannot be derived using a quantum computer.
One interesting point to note was that the implementation of p2pkh was not as a result of the threat of attack, but more linked to resolving some inherent problems with p2pk, namely:
- Very long addresses which result in a larger transaction file and therefore longer processing time.
- Lack of a mechanisms to detect mistyping of addresses.
Summary
So to conclude we can state there is a very real risk of quantum computing attacks but these are solely isolated to addresses where the private key is accessible (i.e. early Bitcoin addresses). The implications are that a large amount of early Bitcoin which was thought to be lost forever due to misplaced keys, could in fact be brought back into circulation.
Disclaimer: This article is written for the purposes of research and does not constitute financial advice or a recommendation to buy.