In recent years, there has been a substantial amount of research on quantum computers – machines that exploit quantum mechanical phenomena to solve mathematical problems that are difficult or intractable for conventional computers. If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems currently in use. “An attacker needs about the same time to break the system as it takes the user to run it,” says Dr Tanja Lange, chair of the Coding Theory and Cryptology group at Technische Universiteit Eindhoven
This would seriously compromise the confidentiality and integrity of digital communications on the Internet and elsewhere. Since last three decades, the public key cryptography has been ensuring the security of our global communication digital infrastructure including securing our internet payments, banking transactions, emails and even phone conversations.
The goal of post-quantum cryptography (also called quantum-resistant cryptography) is to develop cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks. NIST has initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms.
“The question of when a large-scale quantum computer will be built is a complicated one. While in the past it was less clear that large quantum computers are a physical possibility, many scientists now believe it to be merely a significant engineering challenge,” says NIST. Some engineers even predict that within the next twenty or so years sufficiently large quantum computers will be built to break essentially all public key schemes currently in use.
Historically, it has taken almost two decades to deploy our modern public key cryptography infrastructure. “The whole process to study algorithms, standardise them and get them deployed, can take 15 years or longer,” says Dr Dustin Moody, a mathematician in the computer division at NIST. Therefore, regardless of whether we can estimate the exact time of the arrival of the quantum computing era, we must begin now to prepare our information security systems to be able to resist quantum computing. NIST will play a leading role in the effort to develop a widely accepted, standardized set of quantum resistant algorithms.
Organizations are now working on post-quantum cryptography (also called quantum-resistant cryptography), whose aim is to develop cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks. NSA, whose mission is to protect vital US national security information and systems from theft or damage, is also advising US agencies and businesses to prepare for a time in the not too-distant future when the cryptography protecting virtually all e-mail, medical and financial records, and online transactions is rendered obsolete by quantum computing.
On the other hand, NSA and other spy agencies are also providing thrust to development of quantum computers to be able to break the encryption of their adversaries and terrorists. Former CIA Deputy Director Michael Morell said in an interview on CBS’, “I think what we’re going to learn is that these guys are communicating via these encrypted apps, this commercial encryption which is very difficult or nearly impossible for governments to break, and the producers of which don’t produce the keys necessary for law enforcement to read the encrypted messages.”
Google testing “Post quantum cryptography”
To stave off that secret-less future, Google has revealed that it is testing new “post quantum crypto” in few Chrome desktop installations that would be resistant to not only modern crypto cracking methods but also future quantum attacks when quantum computer becomes available. “The reason we’re doing this experiment is because the possibility that large quantum computers could be built in the future is not zero. We shouldn’t panic about it, but it could happen,” says Google security engineer Adam Langley.
Google is trying a two-year experiment: It’s switching the TLS web encryption in a test portion of Chrome installations and Google services from elliptic curve cryptography—a common form of encryption that can be practically unbreakable for normal computers—to a protocol that bolsters elliptic curves by adding in a new type of encryption known as Ring Learning With Errors or Ring-LWE.
No one can be sure yet of Ring-LWE’s immunity to quantum cracking techniques, points out Johns Hopkins cryptography professor Matthew Green. But he argues it’s still an important a step in the right direction. “It’s much better to use an algorithm where we don’t know of any quantum attacks versus the ones we know today to be broken by them,” says Green. “This is research stuff, not what you’d expect to be out there in the world. But it’s interesting that Google’s trying it anyway, even on a small percentage of browsers.”
Vulnerability of public key cryptography
By harnessing quantum super-positioning to represent multiple states simultaneously, quantum-based computers promise exponential leaps in performance over today’s traditional computers. Quantum algorithms can break current security by reverse computing private keys faster than a conventional computer. Quantum computers shall bring power of massive parallel computing i.e. equivalent of supercomputer to a single chip. They shall also be invaluable in cryptology and rapid searches of unstructured databases.
Many of our most crucial communication protocols rely principally on three core cryptographic functionalities: public key encryption, digital signatures, and key exchange. Currently, these functionalities are primarily implemented using Diffie-Hellman key exchange, the RSA (RivestShamir-Adleman) cryptosystem, and elliptic curve cryptosystems. The security of these depends on the difficulty of certain number theoretic problems such as Integer Factorization or the Discrete Log Problem over various groups.
In 1994, Peter Shor of Bell Laboratories showed that quantum computers, a new technology leveraging the physical properties of matter and energy to perform calculations, can efficiently solve each of these problems, thereby rendering all public key cryptosystems based on such assumptions impotent. Thus a sufficiently powerful quantum computer will put many forms of modern communication—from key exchange to encryption to digital authentication—in peril.
In the twenty years since Shor’s discovery, the theory of quantum algorithms has developed significantly. Quantum algorithms achieving exponential speedup have been discovered for several problems relating to physics simulation, number theory, and topology.
Quantum computing is also believed to be capable of tackling other mathematical problems classical computers can’t solve quickly, including computing discrete logarithm mod primes and discrete logs over elliptic curves.
Progress in Quantum Computers
IBM has made 5 qubit Quantum Computer Available on IBM Cloud called IBM Quantum Experience, will allow users to run algorithms and experiments on IBM’s quantum processor, work with the individual quantum bits (qubits), and explore tutorials and simulations around what might be possible with quantum computing.
The quantum processor is composed of five superconducting qubits and is housed at the IBM T.J. Watson Research Center in New York. The five-qubit processor represents the latest advancement in IBM’s quantum architecture that can scale to larger quantum systems. It is the leading approach towards building a universal quantum computer. IBM plans to scale their quantum computer between 50 and 100 qubits within the next decade.
Some experts even predict that within the next 20 or so years, sufficiently large quantum computers will be built to break essentially all public key schemes currently in use. 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.
“Therefore, regardless of whether we can estimate the exact time of the arrival of the quantum computing era, we must begin now to prepare our information security systems to be able to resist quantum computing,” says NIST. Consequently, the search for algorithms believed to be resistant to attacks from both classical and quantum computers has focused on public key algorithms.
Enhancing security by increasing key length
In contrast to the threat quantum computing poses to current public key algorithms, most current symmetric cryptographic algorithms (symmetric ciphers and hash functions) are considered to be relatively secure from attacks by quantum computers. While the quantum Grover’s algorithm does speed up attacks against symmetric ciphers, doubling the key size can effectively block these attacks. Thus post-quantum symmetric cryptography does not need to differ significantly from current symmetric cryptography
NSA guidance advises using the same regimen of algorithms and key sizes that have been recommended for years. Those include 256-bit keys with the Advanced Encryption Standard, Curve P-384 with Elliptic Curve Diffie-Hellman key exchange and Elliptic Curve Digital Signature Algorithm, and 3072-bit keys with RSA encryption.
But for those who have not yet incorporated one of the NSA’s publicly recommended cryptographic algorithms—known as Suite B in NSA parlance—last week’s advisory recommends holding off while officials plot a new move to crypto algorithms that will survive a postquantum world.
“Our ultimate goal is to provide cost effective security against a potential quantum computer,” officials wrote in a statement posted online. “We are working with partners across the USG, vendors, and standards bodies to ensure there is a clear plan for getting a new suite of algorithms that are developed in an open and transparent manner that will form the foundation of our next Suite of cryptographic algorithms.”
Quantum Resistant Algorithms
NIST has identified main families for which post-quantum primitives have been proposed include those based on lattices, codes, and multivariate polynomials, as well as a handful of others.
Lattice-based cryptography – Cryptosystems based on lattice problems have received renewed interest, for a few reasons. Exciting new applications (such as fully homomorphic encryption, code obfuscation, and attribute-based encryption) have been made possible using lattice-based cryptography. Most lattice-based key establishment algorithms are relatively simple, efficient, and highly parallelizable. Also, the security of some lattice-based systems are provably secure under a worst-case hardness assumption, rather than on the average case. On the other hand, it has proven difficult to give precise estimates of the security of lattice schemes against even known cryptanalysis techniques.
Code-based cryptography – In 1978, the McEliece cryptosystem was first proposed, and has not been broken since. Since that time, other systems based on error-correcting codes have been proposed. While quite fast, most code-based primitives suffer from having very large key sizes. Newer variants have introduced more structure into the codes in an attempt to reduce the key sizes, however the added structure has also led to successful attacks on some proposals. While there have been some proposals for code-based signatures, code-based cryptography has seen more success with encryption schemes.
Multivariate polynomial cryptography – These schemes are based on the difficulty of solving systems of multivariate polynomials over finite fields. Several multivariate cryptosystems have been proposed over the past few decades, with many having been broken. While there have been some proposals for multivariate encryption schemes, multivariate cryptography has historically been more successful as an approach to signatures.
Hash-based signatures – Hash-based signatures are digital signatures constructed using hash functions. Their security, even against quantum attacks, is well understood. Many of the more efficient hash-based signature schemes have the drawback that the signer must keep a record of the exact number of previously signed messages, and any error in this record will result in insecurity. Another drawback is that they can produce only a limited number of signatures. The number of signatures can be increased, even to the point of being effectively unlimited, but this also increases the signature size.
Other – A variety of systems have been proposed which do not fall into the above families. One such proposal is based on evaluating isogenies on supersingular elliptic curves. While the discrete log problem on elliptic curves can be efficiently solved by Shor’s algorithm on a quantum computer, the isogeny problem on supersingular curves has no similar quantum attack known. Like some other proposals, for example those based on the conjugacy search problem and related problems in braid groups, there has not been enough analysis to have much confidence in their security
This post-quantum transition raises many fundamental challenges, says NIST
It’s going to be a huge amount of effort to develop, standardize, and deploy entirely new classes of algorithms.
Previous transitions from weaker to stronger cryptography have been based on the bits-of security paradigm, which measures the security of an algorithm based on the time-complexity of attacking it with a classical computer (e.g. an algorithm is said to have 128 bits of security if the difficulty of attacking it with a classical computer is comparable to the time and resources required to brute-force search for a 128-bit cryptographic key.)
“Unfortunately, the bits-of-security paradigm does not take into account the security of algorithms against quantum cryptanalysis, so it is inadequate to guide our transition to quantum-resistant cryptography. There is not yet a consensus view on what key lengths will provide acceptable levels of security against quantum attacks,”
“At the same time, this recommendation does not take into account the possibility of more sophisticated quantum attacks, our understanding of quantum cryptanalysis remains rather limited, and more research in this area is urgently needed, says NIST.”