Algorithms

Quantum Computing and Crypto Risks, How can crypto survive in the Quantum realm?

January 9, 2021

As we see record highs and interest in the cryptocurrency marketplace, could now be a time to consider whether investing in the any of the crypto currencies is effectively safe – especially in shadow of possible attacks from Quantum Computing?

As we round the first few days of 2021, crypto currencies such as Bitcoin and Ethereum are making headlines for their rapid price increases. The price of a single Bitcoin has hit over $40,000 and Ethereum over $1,200. The last year has seen a massive increase in the valuation of these crypto currencies. Earlier in 2020, Ethereum was trading below $200 and bitcoin was largely below $10,000 for much of 2020. So prices have come as sudden impact especially over the Christmas and New Year festivities. For sure, price rises will likely spur more interest in these crypto currencies and other “Alt” (alternative) coins as speculators clamour for new coins which might “Moon” into making them wealthy beyond belief.

Quantum Computing, Science Fiction, Fantasy or Reality?

Quantum Computers exist. Just as in the early days of classical computing, these are devices that have limited use cases. Researchers around the world are busy making these machines more useful by increasing the number of physical qubits – that is loosely analogous to the classical number of transistors in an existing processor (classical). Current machines have only a few tens of qubits – but this number is climbing all the time. IBM have published their roadmap to get to thousands of qubits in just a few years, but currently allow low tens on their public quantum cloud.

Labs around the world are improving the technology that underpin any future Quantum Computing effort. Companies such as IBM, Microsoft, Google, Amazon, Honeywell are busy building the technology platforms that others can then exploit. Companies such as JP Morgan and Goldman Sachs are figuring out how to use quantum computing in the finance sector for tasks such as portfolio optimisation and pricing optimization. Pharmaceutical firms are looking at Drug Discovery employing facets of Quantum Computing. VW is looking at routing and materials.

Don’t believe these machines exist? Go to IBM and get a free IBM account and start programming a Quantum Computer – or simply go to to our book section to read how to program one. Not only can you use one, program one, perform some basic algorithms and run on real quantum hardware. IBM have reported billions of Quantum circuits that have been run by their users on their public quantum cloud: IBM Q.

IBM made it’s quantum service available on the cloud over 4 years ago. The number of qubits available has been steadily increasing and now billions of circuits have been run on IBM Q.

Quantum Use Cases: The Shor Algorithm

One of the driving interests behind Quantum algorithms has been one well known use case. That emerged from Peter Shor: The Shor Algorithm. The premise is that the algorithm allows number to be factored more quickly than classical computers. If this sounds rather pointless – consider that much of the worlds security protocols are based on the principle that it is hard to factorize a number, but easy to check those factors.

Take two large prime numbers and multiply them. If I give you that number and ask you to find the original two numbers, you might struggle. For easy cases like say 15, you can say, 5 and 3 immediately, but what about a number with 256 digits? There is the basis of cryptography in one paragraph and is the essence of the security protocols that much of the world relies on.

Shor’s Algorithm promises to be able to radically beat the classical ways that we can compute factors of large numbers. The algorithm can run on a quantum computer and uses the advantages of quantum superposition and entanglement to be more efficient computationally compared to a classical machine. Researchers are worried that if large enough Quantum computers can be built that can handle these large numbers, then the security protocols that we rely on will be broken.

Right now only small numbers can be factorized. These are numbers that are so trivially solved even a computer is not required. However the fear is that if technology continues apace in Quantum, then eventually larger numbers will be possible to factorize. If you want to run a circuit, there are some tutorials on Shor’s with some example code that you can run to do the factorization yourself.

Both Bitcoin and Ethereum employ Elliptic Curve Digital Signature Algorithm at their core, or ECDSA for short. This protocol has become the standard for generating cryptographic keys utilising the Public Key (PK) cryptographic system that is used to electronically and securely sign transactions in blockchains. As demonstrated above, the heart of the security is the ability to be able to check very quickly that two numbers multiply and result in a third, but the process cannot be easily performed in reverse – so called factorization.

The benefits of Public Key cryptography are that sharing keys can be done publicly. That is an algorithm can encode a message with a given public key, but the originator of the public key can only unlock it (with their private key). This innovation has provided much of the backbone of the modern communication networks such as the internet and enabled everything from e-commerce to payments and now the Blockchain.

Quantum threats to the Blockchain

Current Quantum Computing is a long way (so people think) of being able to break the cryptographic protocols behind the blockchain. However that doesn’t mean that the status quo will remain. Certainly more powerful Quantum Computers might provide that threat to current protocols.

Many researchers are busy thinking about how to build the next innovation in Blockchains. One way is to adopt technologies that are inherently secure against quantum computers, perhaps utilising quantum technology themselves. Research is happening quantum-resistant blockchains and even distributed ledger technology deploying Quantum Computers.

Private keys might be cracked as early as 2027

Divesh AggarwalGavin K. BrennenTroy LeeMiklos SanthaMarco Tomamichel

Some researchers think it is simply a matter of time before quantum computers catch up with the realities of the present day blockchains. We briefly investigate the risk of Bitcoin, and other cryptocurrencies, to attacks by quantum computers. Prof Divesh Aggarwal et al. find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years (paper was released in 2017). However they suggest biggest potential risk is the elliptic curve signature scheme.

The elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027

Prof Divesh Aggarwal et aL

Quantum Proof Blockchain

Quantum proof schemes are therefore the order of the day. Future and current developers of crypto currencies and blockchains must find ways to mitigate potential risk from Quantum computers. A number of these Post Quantum schemes are being proposed as ‘Version 2.0‘ of the blockchain.

One of the biggest questions of all is whether Quantum computing will advance to be a significant threat or advance rapidly enough to impact the crypto world. The moment that advances in quantum look sufficient we could see massive changes in the crypto currency market as investors dump vulnerable protocols. Of course that means blockchain technology may need continually adapt to advancing quantum developments to remain secure.

There are alternatives (so called ‘Alt coins’) of Bitcoin and Ethereum which aim to obviate the problem of quantum computing right from the start. Quantum Resistant Ledgers are one way. There are a few schemes and projects being trialled, such as those at QRL (which stands for Quantum Resistant Ledger) which embody a blockchain platform secured by XMSS. XMSS (Extended Merkle Signature Scheme) is a NIST-approved post-quantum secure digital signature scheme. Schemes such as XMSS and a similar hash-based signature scheme called Leighton-Micali (LMS) are thought to be much more impervious to quantum attacks.

The QRL project has a number of followers and own token: The Quanta. Just as miners for Bitcoin and other coins can earn tokens for doing useful work for the network, miners can earn Quanta by performing verification for the network. QRL is head-quartered in Switzerland, which seems to be the epicentre of the crypto world.

Crypto Predictions

We don’t have a Crystal ball. However there is no doubt that Shor’s algorithm is valid and works. It’s been put under the microscope by many researchers since Peter Shor developed the algorithm in 1997. Complexity theorists have confirmed that the algorithm does work in theory and practice and therefore it is likely to provide the much anticipated speed-up in factorisation. You can even run the Shor algorithm yourself on an IBM computer – but don’t expect anything amazing – just double digits can be handled (factorized) with the low number of qubits available.

What is unknown is the speed and scale of the Quantum computers that will arrive. But investors in Crypto currencies must be aware of the downside risk of rapid advances beyond the scope of predictions or sudden breakthroughs that could mean protocols become suddenly at risk. Another issue is that data taken or stolen now could be stored and later broken – not such an issue for the blockchain – but other data sources such as medical records for example or data with a historic value.

Luckily many researchers are working on new schemes and way to deal with the current blockchains and keep them as secure as possible. Whether we will see any threat to Bitcoin remains to be seen as prices have been predicted to rise to several hundred thousand dollars per Bitcoin. Some are suggesting that Bitcoin is akin to a reserve currency.