Quantum resistant blockchain and cryptocurrency, the full analysis in seven parts. Part 3.
By QR Collector on ALTCOIN MAGAZINE
In part 1 and 2, I get into the blockchain basics that are very usefull to understand all the following articles. You can read part 1 here, and part 2 here
Quantum resistant blockchains explained.
1. The fact that whatever is registered on a blockchain can’t be tampered with is one of the great reasons for the success of blockchain. But what if the rules change and there is a possibility to break one of the defense lines of blockchain? Eventually, quantum computers will be able to break some of the mathematics that secure blockchain. Looking ahead, awareness is growing in the blockchain ecosystem that quantum computers might cause the need for some changes in the cryptography that is used by blockchains to prevent hackers from forging transactions.
2. How would quantum computers pose a threat to blockchain? First, let’s get a misconception out of the way. When talking about the risk quantum computers could pose for blockchain, some people think about the risk of quantum computers out-hashing classical computers. This, however, is not expected to pose a real threat when the time comes.
3. This paper explains why: https://arxiv.org/pdf/1710.10377.pdf “In this section, we investigate the advantage a quantum computer would have in performing the hashcash PoW used by Bitcoin. Our findings can be summarized as follows: Using Grover search, a quantum computer can perform the hashcash PoW by performing quadratically fewer hashes than is needed by a classical computer. However, the extreme speed of current specialized ASIC hardware for performing the hashcash PoW, coupled with much slower projected gate speeds for current quantum architectures, essentially negates this quadratic speedup, at the current difficulty level, giving quantum computers no advantage. Future improvements to quantum technology allowing gate speeds up to 100GHz could allow quantum computers to solve the PoW about 100 times faster than current technology.
4. However, such a development is unlikely in the next decade, at which point classical hardware may be much faster, and quantum technology might be so widespread that no single quantum enabled agent could dominate the PoW problem.”
5. The real point of vulnerability is this: attacks on signatures wherein the private key is derived from the public key. That means that if someone has your public key, they can also calculate your private key, which is unthinkable using even today’s most powerful classical computers. But in the days of quantum computers, the public-private keypair will be the weak link. Quantum computers have the potential to perform specific kinds of calculations significantly faster than any normal computer. Besides that, quantum computers can run algorithms that take fewer steps to get to an outcome, taking advantage of quantum phenomena like quantum entanglement and quantum superposition. So quantum computers can run these certain algorithms that could be used to make calculations that can crack cryptography used today. See for reference here and here.
6. Most blockchains use Elliptic Curve Digital Signature Algorithm (ECDSA) cryptography. Using a quantum computer, Shor’s algorithm can be used to break ECDSA. (See for reference: here and for the pdf version here.) In short: one could derive the private key from the public key. So again: if someone has your public key (and a quantum computer), then he has your private key and can create a transaction and empty your wallet.
7. RSA has the same vulnerability while RSA will need a stronger quantum computer to be broken than ECDSA.
8. At this point in time, it is already possible to run Shor’s algorithm on a quantum computer. However, the amount of qubits available right now makes its application limited. Some would even argue that the quantum computers that have been developed so far do not deserve to be named actual quantum computers due to the infant state of it’s development. It might not surprise you, but IBM doesn’t share that opinion and has launched it’s first commercial quantum computer. Promotional video here and article here. Anyway, however you would label the device, Shor’s has been proven to work on a quantum device and we have exited the era of pure theory and entered the era of practical applications:
- 2001: First execution of Shor’s algorithm at IBM’s Almaden Research Center and Stanford University. The paper here: (Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance Lieven M. K. Vandersypen)
- 2009: Researchers at University of Bristol demonstrate Shor’s algorithm on a silicon photonic chip. And the paper here.
- IBM on Shor’s here
9. So far Shor’s algorithm has the most potential, but new algorithms might appear which are more efficient. Algorithms are another area of development that makes progress and pushes quantum computer progress forward. To give an example: a new algorithm called Variational Quantum Factoring is being developed and looks quite promising. “ The advantage of this new approach is that it is much less sensitive to error, does not require massive error correction, and consumes far fewer resources than would be needed with Shor’s algorithm. As such, it may be more amenable for use with the current NISQ (Noisy Intermediate Scale Quantum) computers that will be available in the near and medium term.” See for more information here. It is however still in development, and only works for 18 binary bits at the time of this writing, but it shows new developments that could mean that, rather than a speedup in quantum computing development to be posing the most imminent threat to RSA and ECDSA, instead a speedup in the mathematical developments could be even more consequential. For a paper on VQF, see here.
10. It all comes down to this: when your public key is made public, which is always necessary to make transactions, you are at some point in the future vulnerable to quantum attacks. (This also goes for BTC and other blockchains, that use the hash of the public key as an address instead of the full original public key, but more on that in the following parts of the series.) However, if you would have keypairs based on post-quantum cryptography, you would not have to worry about this issue since in that case not even a quantum computer could derive your private key from your public key.
11. The conclusion is that future blockchains should be quantum resistant, using post-quantum cryptography. It’s very important to realize that post quantum cryptography is not just adding some extra characters to standard signature schemes. It’s the mathematical concept that makes a signature scheme quantum resistant. To become quantum resistant, the algorithm needs to be changed. “The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems can be solved on a sufficiently powerful quantum computer running Shor’s algorithm. Even though current, publicly known, experimental quantum computers lack power to break any real cryptographic algorithm, many cryptographers are designing new algorithms to prepare for a time when quantum computing becomes a threat.” For more about post-quantum cryptography, also known as quantum resistant cryptography, here.
Expectations in the field of quantum computer development.
12. To give you an idea what the expectations of quantum computer development are, expressed by the companies that are working on quantum computers:
13. (Take note of the fact that the type and error rate of the qubits that are mentioned is not specified in these articles. It is not said these will be enough to break ECDSA or RSA, neither is it said these will not be enough. What these articles do show, is that a huge speed up in development is expected.)
- “It should be about 5 years to 1000 qubit chips with superconducting technology. It should be about 10 years to million qubit chips.” (Jim Clarke, Intels Quantum hardware director. (Full interview here)
- “And a million-physical-qubit system, whose general computing applications are still difficult to even fathom? It’s conceivable, says Neven, “on the inside of 10 years.” “ (That is Harmut Neven of Google’s quantum computing effort)
- IBM believes quantum computers will be mainstream in 5 years. (Meaning outside of research labs, but not necessarily in livingrooms of the average Joe. And no amount of qubits mentioned though)
- “Five years from now, we will have a commercial quantum computer,” says Microsoft’s Holmdahl.
- *Eddited and added June 19, 2019: Quantum computing power might move forward faster than More’s law: Neven’s law, a doubly exponential speedup might apply to quantum computing development. “That rapid improvement has led to what’s being called “Neven’s law,” a new kind of rule to describe how quickly quantum computers are gaining on classical ones. The rule began as an in-house observation before Neven mentioned it in May at the Google Quantum Spring Symposium. There, he said that quantum computers are gaining computational power relative to classical ones at a “doubly exponential” rate — a staggeringly fast clip.”
- And those are just the commercial companies. The pentagon sees quantum computing as the next arms race. China is about to pump $10 Billion in a research centre. They won’t be open about their developments as Google etc. It’s not a bad idea to start looking for solutions and new opportunities in blockchain.
- This paper estimates ECDSA being at risk as soon as 2027.
14. The big question is: When will ECDSA be at risk? Estimates are only estimates, there are several estimates to be found, some well founded and more educated than others but there is no fixed date so it’s hard to really tell.
15. The National Academy of Sciences (NAS) has made a very thorough report on the development of quantum computing. The report came out in the end of 2018. They brought together a group of over 70 scientists from different interconnecting fields in quantum computing who, as a group, have come up with a close to 200 pages report on the development, funding, implications and upcoming challenges for quantum computing development. But, even though this report is one of the most thorough up to date, it doesn’t make an estimate on when the risk for ECDSA or RSA would occur. They acknowledge that making an estimate is quite impossible due to the fact there are a lot of unknowns and due to the fact that they have to base any findings only on publicly available information, obviously excluding any non available advancements from commercial companies and national efforts that keep (parts) of their advances secret. So if this group of specialized scientists can’t make an estimate, who can make that assessment? Is there any credible source to make an accurate prediction?
16. The conclusion at this point of time can only be that we do not know the answer to the big question “when”.
17. Now if we don’t have an answer to the question “when”, then why act? Why go for quantum resistant cryptography? If we’re talking about security, most take certainty over uncertainty. To find the answer to the question when the threat materializes, we still need to guess. Whether you guess soon, or you guess not for the next three decades, both are guesses. Going for certain means you’d have to plan for the worst, hope for the best. No matter how sceptical you are, having some sort of a plan ready would be a responsible thing to do. Obviously not if you’re just running a blog about knitting. But for systems that carry a lot of important, private and valuable information, planning and maybe even implementing starts today. The NAS describes it quite well. What they lack in guessing, they make up in advice. They have a very clear advice:
18. “Even if a quantum computer that can decrypt current cryptographic ciphers is more than a decade off, the hazard of such a machine is high enough — and the time frame for transitioning to a new security protocol is sufficiently long and uncertain — that prioritization of the development, standardization, and deployment of post-quantum cryptography is critical for minimizing the chance of a potential security and privacy disaster.”
19. Another organization that looks ahead is the National Security Agency (NSA) They have made a threat assessment in 2015. In August 2015, NSA announced that it is planning to transition “in the not too distant future” (statement of 2015) to a new cipher suite that is resistant to quantum attacks. “Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy.” NSA advised: “For those partners and vendors that have not yet made the transition to Suite B algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.”
20. What these organizations both advise is to start taking action. They don’t say “implement this type of quantum resistant cryptography now”. They don’t say when at all. As said before, the “when” question is one that is a hard one to specify. It depends on the system you have, the value of the data, the consequences of postponing a security upgrade. You just run a blog, or a bank or a cryptocurrency? It’s an individual risk assessment that’s different for every organization and system. Assessments do need to be made now though. What time frame should organizations think about when changing cryptography? How long would it take to go from the current level of security to fully quantum resistant security? What changes does it require to handle bigger signatures and is it possible to use certain types of cryptography that require to keep state? Do your users need to act, or can al work be done behind the user interface? These are important questions that one should start asking. I will elaborate on these challenges specifically for cryptocurrencies in the next articles.
21. Besides the unanswered question on “when”, the question on what type of quantum resistant cryptography to use is unanswered too. This also depends on the type of system you use. The NSA and NAS both point to NIST as the authority on developments and standardization of quantum resistant cryptography. Since 2016, NIST is running a competition right now that should end up with one or more standards for quantum resistant cryptography.
22. “Widely used public key cryptographic systems, which protect electronic banking data and many other kinds of information, use pairs of very large numbers to serve as the keys for decrypting the message. These numbers can be hidden by multiplying them together to produce even larger numbers that a conventional computer cannot easily factor. However, a quantum computer would be able to find the initial two numbers quickly, breaking the encryption.”
23. Federal Register (The daily journal of the United States Government) in 2016:
24. “In particular, quantum computers would completely break many public-key cryptosystems, including those standardized in FIPS 186–4”
25. ECDSA is used by BTC as a signature scheme. ECDSA is a FIPS 186–4 standard: NIST; ECDSA FIPS 186–4
NIST:
26. “We’re looking to replace three NIST cryptographic standards and guidelines that would be the most vulnerable to quantum computers,” Moody said, referring to FIPS 186–4, NIST SP 800–56A and NIST SP 800–56B.”
27. The NIST competition handles criteria that should filter out a type of quantum resistant cryptography that is feasible for a wide range of systems. This takes time though. There are some new algorithms submitted and assessing them must be done thoroughly. They intend to wrap things up around 2022–2024. From a blockchain perspective it is important to notice that, next to NIST’s effort to find replacement for all round implementation signature schemes, they also look at more specialized signature schemes that are excellent, but less suitable for just any type of application: Stateful Hash-Based Signatures. (LMS and XMSS) This is not because these are no good. XMSS is accepted to be provable quantum resistant. It’s due to the fact that implementations will need to be able to securely deal with the requirement to keep state that XMSS is not suitable for just any application.
28. At this moment NIST intends to approve both LMS and XMSS for a specific group of applications that can deal with the stateful properties. The only loose end at this point is an advice for which applications LMS and XMSS will be useful and for what applications it is discouraged. These questions could be answered as soon as april this year. This means that quite likely LMS and XMSS will be the first type of standardized quantum resistant cryptography ever. To give a small hint: keeping state, is pretty much a naturally added property of blockchain. (It does however, require a specific design in the blockchain structure to implement XMSS, so even though blockchain is highly suited for XMSS, it still isn’t just a matter of copy paste. QRL is the only blockchain at this point of time that has a successful and externaly audited implementation of XMSS.
Quantum resistant blockchains
29. “Quantum resistant” is only used to describe networks and cryptography that are secure against any attack by a quantum computer of any size in the sense that there is no algorithm known that makes it possible for a quantum computer to break the applied cryptography and thus that system. So a blockchain would be considered quantum resistant if it exclusively uses a quantum resistant signature scheme.
30. There are a lot of challenges and misconceptions concerning quantum resistant blockchains and the transition towards quantum resistance. I will address these in the following chapters, but first I will elaborate a bit about the special vulnerability of decentralized blockchain compared to centralized systems.
Why is it easier to change cryptography for centralized systems such as banks and websites than for blockchain?
31. A common thing you hear people say when the subject comes up is: “If ECDSA cryptography breaks, the whole internet will be broken. Why even worry about blockchain.” An important distinction to be made is the fact that most systems are centralized. While blockchain is decentralized. This creates three problems:
1. Developers of a centralized system can decide from one day to the other that they make changes and update the system without the need for consensus from the people who are running nodes. The central developers are in charge, and they can dictate the future of the system. But a decentralized system like blockchain will need to reach consensus amongst the nodes to update. Meaning that the majority of the nodes will need to upgrade and thus force the blockchain to only have the new signatures to be valid. We can’t have the old signature scheme to be valid next to the new quantum resistant signature scheme. Because that would mean that the blockchain would still allow the use of vulnerable, old public- and private keys and thus the old vulnerable signatures for transactions. So at least the majority of the nodes need to upgrade to make sure that blocks which are constructed using the old rules and thus the old vulnerable signature scheme, are rejected by the network. This will eventually result in a fully upgraded network which only accepts the new post quantum signature scheme in transactions. So, consensus is needed. There is no central power that can make the hard decisions. The need for consensus is exclusively a problem that decentralized systems like blockchain will face.
2. Another issue that decentralized systems face while wanting to change their signature scheme, is that users of decentralized blockchains will have to manually transfer/ migrate their coins/ tokens to a quantum safe address. The upgraded blockchain will only effect the key pairs of newly generated addresses. The old addresses obviously already exist and have been generated by the old blockchain. So only the new generated addresses would be quantum resistant key pairs. The old addresses, would be unchanged, and thus still be vulnerable key pairs. So only migrating funds from old addresses to new quantum resistant addresses would bring your funds under the protection of the new quantum resistant qualities of the upgraded blockchain. Remember, it is not the coins or tokens that are quantum resistant. It’s the private- public key pair, the address you store your coins or tokens on, that is quantum resistant. So in the decentralized system all users would need manually generate a new address and move their coins to that new address. Users of centralized networks, on the other hand, do not need to do anything, since it would be taken care of by their centralized managed system. As you know, for example, if you forget the password of your online bank account, or some website, they can always send you a link, or secret question, or in the worst case they can send you mail by post to your house address and you would be back in business. So in the centralized system there is a central entity who has access to all the data including all the private accessing data like public- and private keys. Therefore this entity can pull all the strings. It can all be done behind your user interface, and you probably wouldn’t notice a thing. You wouldn’t even have to change your password. In decentralized systems, there is no centralized entity who has your keys. It is you who has your keys, and only you. So in contrast to centralized systems, all users of decentralized systems need to act to fully make that entire system quantum resistant. This means that for you as a user, to secure your value, you depend on the action of all other users. Security wise, you depend on the need for other people to pay attention to developments, understand the necessity, understand the need for personal action after BTC itself has already upgraded to quantum resistance, behave responsible, proactive and fast. This is the human factor. The need for users to act is the second exclusive problem that decentralized systems like blockchain will face.
3. The third issue will be the “lost addresses”. Since no one but you has access to your funds, your funds will become inaccessible once you lose your private key. From that point, an address is lost, and the funds on that address can never be moved. So after an upgrade, those funds will never be moved to a quantum resistant address, and thus will always be vulnerable to a quantum hack. I will get in to this problem more in depth in the next parts, but to put it short: it wil be the sword of damocles hanging over the blockchain until an actual hack takes place. The issue this creates, is a dump in value due to a hack of one or more of those lost addresses. There is no solution to this problem. Blockchain doesn’t know its users, can’t communicate with them and won’t be able to distinguish funds on lost addresses from funds on addresses from users who still have access but somehow have not migrated their coins after a quantum resistant update. So burning “lost coins” will be legally a big issue. The question will be “are they actually lost, or has the owner not migrated them yet?” Since centralized systems have access to all the needed data, they will not face this issue. Lost addresses are the third exclusive problem that decentralized systems like blockchain will face.
32. To summarize: banks and websites are centralized systems. They will face challenges, but decentralized systems like blockchain will face some extra challenges that won’t apply for centralized systems.
- Updating the signature scheme will need consensus in the sense that all nodes need to update after implementation of a quantum resistant signature scheme.
- Users of blockchain will personally need to move their funds from old addresses to new quantum resistant addresses. You won’t need to move your bank funds.
- Lost addresses where people lost access to their funds will never be moved and stay vulnerable to quantum hacks.
33. These are all issues specific for blockchain and not for banks or websites or any other centralized system.
34. And the big companies are already experimenting with quantum resistant cryptography. Take Google for example, they have been experimenting with quantum resistant cryptography since 2016. Here the Google Online Security Blog about their experiment with the New-Hope system in their Chrome browser. And here Cloudflare — Google Chrome.
ABN Amro banks efforts on quantum resistant security. (They won’t be the only one researching and preparing)
Huawei is also starting efforts for adding quantum resistant communication systems to their network.
Barclays demonstrates proof-of-concept quantum clearing algorithm.
Conclusion
35. Bitcoin and all currently running traditional blockchains are not excluded from these problems and challenges. In fact, it will be central to ensuring their continued existence over the coming decades. All cryptocurrencies will need to change their signature schemes somewhere between now and the future. This won’t be an easy transfer. There are some serious challenges to overcome and this will not be done overnight. I will get to this in the next few articles.
You can continue reading here: Part 4, part 5, part 6 and part 7
