An update on quantum resistance

With advice from the QRC team —

Hcash
Hcash
Nov 30, 2017 · 5 min read

Many might have heard recent buzz around the threat of quantum computing to cryptocurrencies, namely — in the wrong hands. Many, however, might not have truly taken in the weight of the detriment it would cause to the industry.

Lucky for us, there are already a number of brilliant minds working on a solution.

Dr. Miklos Santha (Left), Associate Professor Troy Lee (Right) - Source: OpenGov

In a world of technology as new as Blockchain, long hours of research, trial and error, myriads of issues, and learning curves, are all a part of the process. In instituting quantum resistance, a key to successful development and execution of technology, is having a dedicated team of experts focusing on providing research and advice to developers, by which the process is greatly improved in terms of efficiency, and ultimately, speed and effectiveness. Ongoing improvements and movements forward can be pushed, and developers can work effectively.

The QRC (Quantum Resistant Coin) team, made up of Prof. Gavin K. Brennen, Prof. Troy Lee, Dr. Miklos Santha and Dr. Marco Tomamichel, from 4 respected universities worldwide, are leading research to implement quantum resistance in Hcash. The four have recently provided Hcash with a document outlining the following risks and countermeasures, in terms of attacks from quantum computers. The QRC team advises as follows.


Risks to cryptocurrencies due to the advent of quantum computing

We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. This is illustrated below. The dashed blue lines and uncertainty area give our estimate of how the total Bitcoin network hash rate will develop over the next two decades. (The vertical axis gives the number of hashes per second.) For comparison, the black dotted line indicates the hash rate of a state-of-the art ASIC miner available as of August 2017. Finally, the dashed red lines and uncertainty area gives our estimate of the effective hash rate of a single quantum computer. There is a clear gap in the performance of single quantum computer and the network (even at its current hash rate) that persists for at least the next two decades. We therefore do not think that quantum computers will dominate the Bitcoin proof-of-work anytime soon.

Hashes per second vs. time in years | Bitcoin Network (Blue), single quantum computer (Red)

We find that 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, by the most optimistic estimates. Illustrated below is the expected time in seconds (on the vertical axis) it will take a quantum computer running Shor’s algorithm to break the elliptic curve signature scheme used in bitcoin. Our most optimistic model suggests that already in 2027 quantum computers will be able to break the signature scheme in less than 10 minutes, the block time of Bitcoin. This would enable an attacker to intercept a transaction, crack the sender’s secret key, and forge the sender’s signature to send the bitcoin to the attacker’s address, all before the initial transaction can be processed into a block. Bitcoin addresses that are reused are also at risk as the public key corresponding to these addresses is visible on the blockchain. These addresses could be attacked even earlier as there is no time pressure to compute the secret key from the public key.

Time in seconds vs. time in years | Less optimistic (left), more optimistic (right)

Recommendations for Hcash

- A Bitcoin-style proof of work is robust in terms of quantum security for at least the next two decades.

- We strongly recommend the use of a so-called post-quantum signature scheme. These schemes are believed to be secure against attacks by both classical and quantum computers. They are currently an active topic of research in cryptography. Many presumably quantum-safe public key signature schemes have been proposed in the literature.

The key challenge to a quantum-safe digital ledger is to provide for fast transaction speeds and high security. The main categories of quantum-safe signature schemes that have been proposed are hash-based schemes (for example XMSS as used by the Quantum Resistant Ledger), lattice-based schemes, code-based schemes, and schemes based on multivariate polynomials. A major concern with using quantumsafe signature schemes for blockchain applications is the size of the public key and signature produced, which is typically at least 10 times larger than that of the elliptic curve scheme used by Bitcoin. Short keys and signatures are important to reduce the size of transactions and the amount of memory needed to store the blockchain. Long public keys or signatures immediately rules out using code-based schemes or schemes based on multivariate polynomials. Hash-based schemes can be attacked by a quantum computer using Grover’s algorithm. The result is that the quantum security of a hash-based scheme is only half that of its classical security: to achieve 128 bits of quantum security one would need to use a hash-based scheme with 256 bits of classical security. On the other hand, for the lattice-based DILITHIUM scheme, the quantum attacks are not much better than the classical ones. Using DILITHIUM with 138 bits of classical security also gives 125 bits of quantum security. The result is that, for a given level of quantum security, DILITHIUM has the shortest public key + signature size of any practical signature scheme in the literature. The security of DILITHIUM is based on the Ring-LWE and Ring-SIS problems, both of which have been extensively studied in the literature and are widely believed to be hard. More detailed recommendations for the implementation of DILITHIUM will be elaborated in co-operation with the Hcash technical team.

We are most grateful to the QRC team for their knowledge, and ongoing guidance. Quantum resistance, being an essential part of our suite of technologies, is closer to being perfected and applied thanks to them.

With uncertainties in the market, the advancement of Hcash, and becoming more robust as a technology, is of utmost importance. We are working tirelessly towards its completion, which we are aiming to have done by the end of 2017.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade