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. Google In March 2018, unveiled the world’s largest quantum computer processor to date. Dubbed Bristlecone, it’s a 72-qubit gate-based superconducting system, beating IBM which had developed 50-qubit processor. The Mountain View company’s Research at Google team created the 72-qubit processor by scaling its previous 9-qubit system. It’s estimated that a single 50-qubit quantum computer would outperform today’s most powerful mainframes.
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. 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. Experts like Michele Mosca, co-founder of the Institute of Quantum Computing at the University of Waterloo (Canada), sees a chance of 50% that by 2031 quantum computers will be able of breaking RSA-2048 encryption—a scheme today regarded as secure.
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.
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.
A new report from the US National Academies of Sciences, Engineering, and Medicine says we need to speed up preparations for the time when super-powerful quantum computers can crack conventional cryptographic defenses. The experts who produced the report, which was released today, say widespread adoption of quantum-resistant cryptography “will be a long and difficult process” that “probably cannot be completed in less than 20 years.” It’s possible that highly capable quantum machines will appear before then, and if hackers get their hands on them, the result could be a security and privacy nightmare. Considering the fact that data needs to be kept confidential for 10 to 50 years, organisations should start planning to switch now.
The first step is to create these new algorithms, integrate them into protocols, then integrate the protocols into products, said Bill Becker, vice president of product management at SafeNet AT, a provider of information assurance to government customers. 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.
The most significant competition in terms of developing post-quantum or quantum-resistant algorithms is the one being run by the US National Institute of Standards and Technology (NIST), which should be completed around 2024. “So, while organisations can start preparing for post-quantum cryptography now, they will have to wait at least six years to know which algorithm to adopt once Nist has chosen the best submissions for incorporation into a standard,” said Preneel.
Vulnerability of public key cryptography
Bikash Koley, CTO for Juniper Networks, explains cryptography’s basic premise as data which is secured using a combination of public and private keys; while the public key is widely distributed, private keys are computed using mathematical algorithms. “The algorithms are designed in a way that acquiring the private keys from the public keys is nearly impossible,” he said. “For traditional computers, for example, it would take thousands—to millions—of years, depending on how many bits there are in the keys. Quantum computers are very good at number crunching, especially for a specific type of problem.”
As quantum computers begin to crack this encryption, guessing the right private key may only take days or hours. At that point, he said, encryption, as we currently know it, is seriously vulnerable.
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.
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.
“To factor [crack] a 1,024 bit number [encryption key], you need only 2,048 ideal qubits,” said Bart Preneel, professor of cryptography at KU Leuven University in Belgium. “So you would think we are getting close, but the qubits announced are physical qubits and there are errors, so they need about 1,000 physical qubits to make one logical [ideal] qubit. Qubits’ delicate quantum state can be disrupted by things like tiny changes in temperature or very slight vibrations, so it can require thousands of linked qubits to produce a single logical one that can be reliably used for computation. So to scale this up, you need 1.5 million physical qubits. This means quantum computers will not be a threat to cryptography any time soon.
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.”
The argument is that the role of law enforcement is to protect society – they have always had warrants to get access to information, and technology should not change this. “This means they want to be able to intercept voice calls even if it is voice-over-IP, they want to read all your messages and collect all the metadata including location, they want access to stored data including the cloud, and they want access to confiscated devices as well as remote access to suspects’ devices,” said Preneel.
Post Quantum Cryptography
“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.
The good news here, said Preneel, is that the impact for symmetric cryptography is not so bad. “You just have larger encryption keys and then you are done,” he said.
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.
Cyber security firms DigiCert, Gemalto and ISARA partner to ensure a secure future for IoT
Encryption firm DigiCert Inc., digital security company Gemalto, and ISARA Corp , provider of quantum-safe security solutions, have partnered to develop advanced quantum-safe digital certificates and secure key management for connected devices commonly referred to as the Internet of Things (IoT). Currently, most of the IoT devices leverage RSA and ECC cryptography for protecting confidentiality, integrity and authenticity of electronic communication. However, the security community predicts that large-scale quantum computing will break RSA and ECC public key cryptography within next ten years. Together, these companies will develop advanced quantum-safe digital certificates and secure key management to secure the future of IoT.
“The work we’re doing today ensures that a fundamental element of the security stack, root certificates, is secure by embedding quantum-safe cryptography. This means that IoT manufacturers and other large organizations will have the solutions and tools they need to prepare for the quantum threat well in advance of that date, keeping confidential information and high-value assets safe.”
“Gemalto’s SafeNet Hardware Security Modules act as the root of trust to secure the most sensitive data and applications and protect billions of the digital transactions every day around the world,” said Todd Moore, Senior Vice President for Encryption Products at Gemalto. “This partnership with DigiCert and ISARA will help organizations build secure and future-proof cryptographic operations that can guard against the potential security threats of quantum computing and ensure a more secure world for connected automobiles, devices, machines, smart cities and mission-critical infrastructure.”
To advance the use of reliable quantum-proof certificates, DigiCert, Gemalto and ISARA are collaborating with industry standards bodies that also are pursuing the advancement of post-quantum cryptography such as the Internet Engineering Task Force (IETF). Efforts to address quantum computing security today will support connected device manufacturers and users well into the future.
Consider the automobile industry, which is producing more vehicles with semi- and fully-autonomous driving capabilities. A car should last for 20 years or more, and manufacturers will need to ensure that the IoT devices they install will be secure and continue to function even if there is a breakage in the RSA algorithms that would render today’s digital certificates ineffective.
The automotive industry is very focused on long-term and sustainable security management that covers the lifecycle of our vehicles,” said SAE Hardware Security Sub-Committee Chair Bill Mazzara. “Crypto agility is one of the key areas we consider and that includes quantum-resistant technology.”
Infineon Preparing Post-Quantum Cryptography for Cars, Infrastructure
Thus, the cars that today are under development, will be for sure affected by the code breaking capabilities of tomorrow’s quantum computers, Andreas Fuchs, deputy department head for Cyber Physical System Security at the Fraunhofer Institute for Security in the Information Technology (SIT) said. This is owed to the relatively long design cycle of cars (today some 5 to 7 years), their relatively long production cycle of 5 to 10 years and more, and their subsequent life as consumer durables, with an additional lifetime of up to twelve years.
The relevance to identify new encryption schemes that can withstand even the superior code cracker capability of quantum computers results from the variety of communication applications in the connected car that must not be compromised: From value added services (for instance, charge point reservation for e-cars) to novel business models (such as, for instance, “pay-as-you-drive” insurance tariffs) or OEM services such as quality control, product improvement and the like.
The expert suggested automotive electronics developers should incorporate “cryptographic agility” into all networking and local protocols. This means that all crypto-based routines and devices must be exchangeable and upgradeable – which in turn could mean that today’s developers will already leave generous space to accommodate larger keys (much larger keys, actually) and more complex data processing. This also will require that future cars can be updated across the air – a feature the auto industry has currently under development. Under the aspect of data structures, cars will be “long-lived identities”, Fuchs puts it. These identities are required, among other, to establish backend connections, or to retrieve short-lived but safety-critical identities like those that exchange data in a V2X context. Given the longevity of cars and their data identity, it will be very likely that they need to be updated several times over their lifetime – and towards this end, standards are needed, Fuchs added.
Plus, the company is actively pursuing intensive research on post-quantum cryptography, explained Thomas Pöppelmann, who oversees these areas at Infineon. Post-quantum cryptography does not require quantum computers but instead can run on basically conventional hardware, Pöppelmann explained.
Basically five approaches out of several dozens of techniques and are algorithms regarded as promising, Pöppelmann explained. One of them is the “New Hope” approach, based on the research of a quartet of scientists—Erdem Alkim, Léo Ducas, Peter Schwabe—and Infineon’s Thomas Pöppelmann. The chipmaker has implemented the New Hope approach on a commercially available contactless safety chip. This proves that PQC can also be implemented on systems with little memory and contactless power supply—and is therefore practicable, Pöppelmann said.
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.”
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.”
According to “Post-Quantum Cryptography: A Ten-Year Market and Technology Forecast,” a new report from Inside Quantum Technology (www.insidequantumtechnology.com), the market for post-quantum cryptography (PQC) software and devices will ramp up dramatically as quantum computers become capable of breaking popular public-key encryption algorithms. PQC refers to techniques using software algorithms to encrypt messages on a classical computer in a manner that is resistant to being broken by quantum computers.
Revenues from PQC products will reach $145 million by 2014 jumping to $3.8 billion by 2028 as the quantum threat becomes more apparent. Inside Quantum Technology is the only industry analyst firm that specializes in tracking and forecasting the quantum technology market.
Although quantum computers capable of easily breaking common encryption schemes may take a decade to arrive, IT managers are already counting down to Y2Q (Years to Quantum). Some are already implementing PQC for highly valuable data that must last until well after the arrival of quantum computers. Medical records and aircraft designs are two examples of such data. In 2018 the Cloud Security Alliance conducted a survey to better understand how aware IT managers were of quantum risks. They discovered that 86 percent of such managers were aware, at least to some degree, of such risks and almost 20 percent believed that PQC will be required in the next 12 months.
Early adopters of PQC will be those IT managers who have identified a specific need to protect high-value, long shelf-life data. For the rest of the IT community, the conversion will begin when PQC standards are finalized by NIST and other standardization groups.
The largest market for PQC will eventually be standard web browsers, simply because there are so many browsers in cell phones and personal computers. Here PQC will replace the current RSA and Diffie-Hellman algorithms in use today and will be easy to upgrade. By 2026 PQC revenues generated by browsers will reach almost $650 million. However, early PQC revenues in the browser segment will use hybrid classical/PQC algorithms and browsers will be able to select the appropriate encryption algorithm to use depending on the site.
The financial sector is particularly vulnerable to attack, since large sums of money are obtained in a successful hack. Cryptocurrencies — Bitcoin, Ethereum and the others – use classical public key algorithms and will need to convert to PQC to stay safe. Already, two quantum resistant cryptocurrencies — Mochimo and QRL have been released and others are in development. By 2026 revenues from PQC products sold into the financial services industry will reach almost $300 million.
While PQC is mostly implemented in software, for certain embedded systems, a hardware approach may be preferable because these applications do not typically have available a powerful main processor that can implement the full algorithm in software. Some organizations are working to implement the algorithms either using a dedicated ASIC chip or else using an FPGA. Infineon has developed a contactless smart card chip that implements the NewHope algorithm. By 2026, chip-level PQC solutions will generate $120 million.
Among the firms whose strategies are analyzed in this report are AMD, ARM, Blackberry, Cambridge Quantum Computing, Cisco, Envieta, evolutionQ, Google, IBM Research, Infineon, Intel, Isara, Microsoft Research, OnBoard Security, PQAT, Rambus and Thales/Gemalto. Also included is a description of current standardization efforts by government and industry groups such as NIST, the IETF, ETSI, the Cloud Security Alliance and ITU-T.
Applications for PQC covered in this report include civilian government; military, intelligence and domestic security; financial services; telecommunications; data centers and disaster recovery; Internet-of-Things; healthcare and medical records; consumer browsers and general business applications.