In this article, we address a concern about blockchain security, namely, Quantum computers and the potential of an “attack” on Bitcoin’s cryptography encryption. Quantum Computing started in the early 1980s when Richard Feynman and Yuri Manin expressed the idea that a quantum computer had the potential to simulate things that a classical computer could not. This extraordinary computing power comes for Quantum bits or Qubits, which are analogous of the bit in the classic computers. Bits have the value of 1 or 0, but the Qubit, thanks to superposition can be both, depending on their quantum state.
To better understand where the danger is for Bitcoin, let’s have a look at its core cryptography.
Anyone with a cryptocurrency wallet has a private key and a public key. These keys are linked through a specific cryptographic relationship. There are two categories of cryptographic algorithms used within Bitcoin: the hashing algorithm (SHA-256) RIPEMD160 and the digital signature algorithm (ECDSA). In Bitcoin, private keys produce a public key via an Elliptical Curve Digital Signature Algorithm or ECDSA.
This algorithm operates one way only, meaning you can create the public key from the private key, but not the other way around. The security of the ECDSA comes from the fact that as of now it is extremely difficult to factor a large integer composed of two or more large prime factors. In Bitcoin, a private key is a single unsigned 256-bit integer (32 bytes); for a traditional computer, it takes in the order of 2128 basic operations to get the Bitcoin private key associated with a Bitcoin public key. That takes an incredible amount of time; for a traditional everyday computer, it could take millions of years.
As for the SHA-256 algorithm, currently, there are no known attacks that are feasible, and therefore, it is considered secure. However, ECDSA could be vulnerable to a sufficiently large universal quantum computer. Shor’s algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization, formulated in 1994. Without going into all the math behind it, this algorithm (given you have enough qubits) can factor a very large number into 2 prime numbers and then guess your private key from the public key.
IBM was the record holder of a quantum computing chip with 50 qubits, but last year, Google announced Bristlecone, a quantum computing chip with 72 qubits.D-Wave recently announced a 2000-qubit processor optimized for quantum annealing metaheuristics. However, there are reports that D-Wave’s quantum speedup analysis is debatable. Google and IBM have universal quantum computers, meaning they are developed to perform any given task. D-Wave’s 2000-qubit processor is a non-universal quantum computer that was developed for only one given purpose. At present, D-Wave’s systems are only suitable for solving so-called optimization problems. A 2000-qubit non-universal quantum computer is a great achievement, and D-Wave should be kept an eye on. However, it is not within the scope of this article since its not a universal quantum processor.
ECRYPT-CSA (European Network of Excellence in Cryptology-Coordination & Support Action) states in a document issued in 2018 that attacking 256-bit Elliptic Curve Cryptography, like Bitcoin’s keys, 2330 qubits and 1.26 * 1011 Toffoli gate operations are required. It’s exceptionally challenging to keep increasing the number of new qubits because of their instability. For every logical qubit, there is a need for error-correcting qubits. Therefore, it’s remarkably difficult to scale and have a fully functional universal quantum computer.
Another approach to scaling a universal quantum computer is attempted by Stanford University physicist Zhang Shoucheng’s team. They discovered the Majorana fermion, also known as the “Angel Particle”, where there is no need for error-correcting qubits. This is a recent discovery, done only a couple of years ago, and the research still has to mature before we can expect to see any results. We don’t know when universal quantum computers of significant scale will be available; however, cryptography standards such as NIST tend to say that 256-bit ECDSA keys are secure until at least 2030.
Quantum computing might be dangerous for all current cryptographic encryptions out there and not just Bitcoin. Bank keys, government agencies, nuclear launch codes, and similarly sensitive structures would be at risk. However, this doesn’t mean that quantum computers will be powerful enough to actually crack all encryptions. In part because Quantum computing also brings quantum cryptographic opportunities. It would result in potentially better encryption and faster decryption, together with faster computers. As for Bitcoin, there are already some cryptographic algorithms considered to be secure against a potential attack by a quantum computer. Currently, post-quantum cryptography research mostly focuses on four different approaches:
– Hash-based cryptography. A classic example is Merkle’s hash-tree public-key signature system;
– Code-based cryptography. A classic example is McEliece’s hidden Goppa-code public-key encryption system;
– Lattice-based cryptography. The most famous example is the Hoffstein– Pipher–Silverman “NTRU” public-key-encryption system;
– Multivariate-quadratic-equations cryptography. One of the many interesting examples is Patarin’s “HFEv−” public-key-signature system.
However, since high-level quantum computing isn’t available yet it can’t be tested. There are government institutions and open source C libraries, already working on quantum-resistant public-key cryptographic algorithms. NIST (National Institute of Standards and Technology) has started a process to select a set of secure potential post-quantum systems, which will run for the next few years. So far, this is a solution to a problem that is yet to appear.
What does this mean for cryptocurrency? The quantum resistance protection layers can be integrated into cryptocurrency wallets. Some altcoin projects already put quantum-proof development in their roadmap, although it holds low priority with most projects. The cryptography of our active wallets could be upgraded by sending coins to another wallet with quantum-proof cryptography protection. The problem is, some wallets can’t be accessed any more for various reasons. e.g., loss of private keys, and thus can’t change the signing algorithm. So, it is essential to keep a close eye on the developments in quantum computing, and for companies and cryptocurrencies to work on quantum protection sooner rather than later.
—
Written and researched by Erald Cipi from the EMI R&D department