Any data encrypted using public key cryptography will not remain confidential once a nation-state adversary obtains a large-scale quantum computer.
In their Report on Post-Quantum Cryptography, the US National Institute of Standards and Technology (NIST) states that “researchers working on building a quantum computer have estimated that it is likely that a quantum computer capable of breaking 2000-bit RSA in a matter of hours could be built by 2030 for a budget of about a billion dollars.”
For governments expecting to achieve long-term confidentiality of 20 or more years, it may already be too late. Data encrypted today can be harvested and stored by nation-state adversaries with the intention of decrypting it at a later date using a quantum computer. We call this type of quantum-enabled attack: “harvest & decrypt.”
Although replacing current authentication algorithms is less urgent than key establishment, upgrading current Public Key Infrastructures (PKIs) that provide authentication for much of the sensitive data in the world will take much longer. The most significant challenge is that, whereas key establishment algorithms can be rolled out in phases, authentication algorithms in PKIs have to be rolled out in parallel. The classic algorithms need to remain available until every possible reliant system is updated and new roots of trust installed. A decade is not an unreasonable estimate for large enterprises to change over, such as federal governments.
Check out this blog post by Mark Pecen, Chief Operating Officer, for an answer to this question.
Quantum computers are being developed today in large research and academic settings. Today, an early-stage quantum computer is likely to be a massive machine that requires a lot of space and infrastructure – similar to the way early computers took up entire rooms or buildings in the mid-20th Century. By some estimates, we are about a decade away from the point when a quantum computer will be able to crack current public key cryptography. In 2015, Dr. Michele Mosca of the Institute for Quantum Computing at the University of Waterloo published a report stating that he estimates a that there is a “1/7 chance of breaking RSA-2048 by 2026.” In 2017, he updated this estimate to a 1/6 chance. In NIST’s “Report on Post-Quantum Cryptography“, stated that “researchers working on building a quantum computer have estimated that it is likely that a quantum computer capable of breaking 2000-bit RSA in a matter of hours could be built by 2030 for a budget of about a billion dollars”.
It is important to understand that the timeline for quantum computing continues to shrink as more resources are focused on it. A decade ago, there were doubts whether quantum computers could be developed. Today, many experts believe that we will have operational quantum computers within the next decade.
Similar to the Y2K crisis, the technology industry is now facing a ‘Y2Q’ (years to quantum) challenge that has a limited timeline and requires significant work to ensure systems and information are properly protected. The power of quantum computers will break public key cryptography, primarily RSA and ECC, the foundation of cybersecurity. Quantum-safe cryptographic algorithms can be used to create security solutions that will protect classical computers against quantum attack.
“Quantum-safe” as defined by ETSI means: algorithms that are resistant to attacks by both classical and quantum computers, to keep information assets secure even after a large-scale quantum computer has been built.
Quantum-safe is interchangeable with quantum-resistant or post-quantum.
Quantum-safe is not typically applied to physical quantum technologies, such as quantum key distribution (QKD). More often, “quantum cryptography” is used to describe physical quantum technologies.
We all know that certain computational tasks are intractable for traditional computers, yet they admit efficient solutions on a quantum computer. Examples of such tasks include factoring large integers, or computing discrete logarithms. Unfortunately, the security of all our contemporary cryptography rests upon the intractability of these tasks, and so all our contemporary cryptography is vulnerable to an attacker armed with a quantum computer.
However, there are other tasks that are believed to be intractable even for quantum computers. Examples of such tasks include finding isogenies between elliptic curves, or finding short vectors in a lattice. Cryptosystems whose security rests upon these intractable tasks are therefore believed to be secure, even against an attacker armed with a quantum computer.
Our contemporary cryptography is believed to be safe against an attacker armed only with a traditional computer because 40 years of intense study by the world’s best cryptographers has not produced any significant weakness in these systems. Some quantum-safe cryptosystems, such as hash-based signatures and codes-based encryption, have been exposed to similar scrutiny; our trust in those systems is as iron-clad as it gets.
However, the field of quantum-safe cryptography is still young. As such, some quantum-safe cryptosystems have not yet had the opportunity to stand the test of time endured by older cryptosystems. ISARA believes it is important to take a diversified approach to quantum-safe cryptography. Our strategy is to support as many post-quantum cryptosystems as we can so that, in the unlikely event that a future theoretical breakthrough leads to an attack on one quantum-safe cryptosystem, other quantum-safe cryptosystems will be available to take up the slack.
Pen-and-paper analyses of traditional attacks against contemporary cryptography provide a rough estimate of the resources needed to launch these attacks. These estimates are further refined by careful study of optimized implementations on an actual computer, leading to very precise estimates of the security of our contemporary cryptography.
By analogy, pen-and-paper analyses of quantum attacks against quantum-safe cryptography provide a rough estimate of the security of these systems. No one yet has a quantum computer capable of launching such an attack and so we cannot yet produce highly accurate security estimates. Fortunately, the estimates of pen-and-paper analysis are accurate enough to allow us to proceed with the design and implementation of post-quantum cryptography even in the absence of a working quantum computer. Furthermore, we can compensate for potential inaccuracy in our estimates with conservative parameter choices that leave us with a safety buffer in the event of unforeseen improvements on quantum attacks.
No, ISARA does not introduce new cryptographic assumptions upon which to base security. Our experts can and do investigate new approaches to quantum-safe cryptography that do not require new assumptions, and they occasionally suggest improvements to existing quantum-safe proposals.
The security of contemporary public key cryptography rests upon the intractability of certain computational tasks such as factoring integers or computing discrete logarithms. These tasks become tractable on a quantum computer running Shor’s algorithm, enabling an attacker to recover secret keys using only public information. An attacker armed with these secret keys could (i) convincingly impersonate any other individual or organization on the Internet, and (ii) read any Internet traffic protected by public key cryptography.
There is also Grover’s algorithm, another quantum algorithm which offers what’s known as ‘quantum speedup’ through quadratic improvement to unordered search. Grover’s could be used to attack symmetric cryptography like AES by cutting the bit length in half. Doubling the key size is considered a reasonable measure to mitigate quantum attacks that use Grover’s algorithm.
To our knowledge, ISARA is the largest organization in the world focused solely on developing quantum-safe cryptographic solutions for integration into commercial products to protect against quantum attack. The depth of our technical experience and expertise means we are prepared to overcome the technical challenges to build a quantum-safe toolkit and develop a portfolio of products that meet new security challenges. ISARA Radiate™ offers the most security-conscious customers, such as governments and large enterprises, the opportunity to begin testing and deploying quantum-safe technology in a variety of commercial solutions today. Via drop-in algorithm replacements, you can build quantum-safe products with an emphasis on quality assurance and efficient integration today.
The ISARA Radiate™ Security Solution Suite is a production-ready quantum-safe toolkit, a result of years of research and development by an experienced team of cryptographers, researchers, developers and accomplished security industry leaders.
The Suite includes:
1. A complete quantum-safe algorithm toolkit – a library of speed-optimized, quantum-safe, open-source algorithms for digital signatures and key establishment.
2. Vital integration tools such as an OpenSSL Connector to simplify development and accelerate integration into new or existing products.
Learn more about ISARA Radiate™ here.
NIST estimates that the first large-scale, fault-tolerant quantum computer capable of breaking public key cryptography could be built by 2030 for a budget of $1 billion. It is reasonable to speculate that the first adversary to use a quantum computer for malicious purposes is likely to be a nation-state actor and not a single individual or non-governmental group.