Cryptography is a vital part of cybersecurity. Security properties like confidentiality, integrity, authentication, non-repudiation rely on strong cryptographic mechanisms, especially in an always connected, always online world. In addition, cryptography’s applications open up new opportunities and markets: digital signatures or online transactions would not be possible without it.
Quantum computers could undermine almost all of the encryption protocols that we use today. Though quantum computers are still quite some way from being practical, usable machines, once they become so, we could be looking at a whole new world when it comes to online privacy — one in which even the strongest encryption can be broken.
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.
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.
By harnessing quantum super-positioning to represent multiple states simultaneously, quantum-based computers promise exponential leaps in performance over today’s traditional computers. 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. Quantum algorithms can break current security by reverse computing private keys may only take days or hours.
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.
The specter of quantum-powered cyberattacks that can break even the most powerful encryption algorithms looms ever-larger and ever-darker. Chances are, nation-state attackers will be equipped with quantum computing long before the average enterprise has rolled it out.
This would seriously compromise the confidentiality and integrity of our global communication digital infrastructure including securing our internet payments, banking transactions, emails and even phone conversations. Similarly, these are also the same schemes allowing us to have digital signatures and designed to implement the Electronic identification (eID) and Trust Services of the eIDAs regulation. Consequently, data or processes protected by those schemes, such as bank transactions, software updates, digitally signed official documents, patient records and more, will instantly cease to be secure.
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.
Post-quantum cryptography is classical cryptography that stands up to the attacks of a large quantum computer. It does not use any quantum properties. It doesn’t need any specialized hardware. It’s based on hard mathematical problems, just like the cryptography we have today. However, post-quantum cryptography avoids using integer factorization and discrete log problems to encrypt data. We already know that these problems are vulnerable to algorithms run on a quantum computer.
All of these post-quantum cryptography algorithms would not need any quantum hardware to encrypt data. They base the encryption on new mathematical problems that are not vulnerable to known quantum computing attacks. And of course, we have to make sure that while it stands up to (known) quantum computing attacks, it also holds against supercomputers.
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.
As JD Kilgallin, KeyFactor’s senior integration engineer, recently wrote for Dark Reading, threats posed by quantum computing will demand that organizations can react quickly. “At the very least, this requires knowing where your digital certificates are, what cryptographic algorithms their keys are using and what quantum computing means for them, and what systems need to trust those certificates and might experience an outage if the certificate and its chain suddenly change,” he wrote. “It also requires the ability to quickly coordinate changes between entity certificates and the trust anchors of other endpoints that rely on those certificates. Administrators should keep a careful inventory of these keys and certificates and employ automated techniques to securely deploy updates en masse.”
NIST competition for post-quantum or 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. In 2016 NIST put out a call for potential postquantum algorithms, and it announced it had winnowed 69 accepted submissions down to 26 leading candidates. The race is long, with the winners set to be announced in 2022, but in August 2020 the organization announced that it had narrowed the initial field of 69 contenders down to just 15.
The plan is to select the final algorithms in the next couple of years and to make them available in draft form by 2024. So, while organisations can start preparing for post-quantum cryptography now, they will have to wait at least four years to know which algorithm to adopt once Nist has chosen the best submissions for incorporation into a standard.
And so far a single approach to “post-quantum cryptography” accounts for the majority of the finalists: lattice-based cryptography. Public-key encryption uses traditional math to encode data, unlocking it only for those who have the key—or can figure it out. Lattice-based cryptography instead uses enormous grids with billions of individual points across thousands of dimensions. Breaking the code means getting from one specific point to another—which is essentially impossible unless you know the route. Even the National Security Agency, the US spy agency that has long sounded alarms over the threat posed by quantum computers, recently expressed confidence in lattice-based approaches.
However, it’s not just how impenetrable or complex the math is that counts. Post-quantum approaches will only work if they can be used in all the places that high-level cryptography will be needed. For example, the size of the key required to decrypt data is important: imagine what will be possible inside a piece of medical equipment that has little memory and severely limited bandwidth. If the math is so complex that opening the lock requires a massive key, the solution may not pass the usability test.
“What NIST thinks is that lattice problems are really hard,” says Elena Kirshanova, a mathematician and cryptanalysis researcher at I.Kant Baltic Federal University in Russia. “Although these problems are hard, they seem quite efficient in terms of time to generate keys, time to construct signatures, and also efficient in terms of memory.”
Researchers recently published a technique for encryption that promises to go beyond perfect secrecy to encryption that is unbreakable, even if quantum computing is brought into the picture. The technique, which takes advantage of chaos and the second law of thermodynamics mixed with the speed of optical chips, doesn’t require quantum power to achieve quantum-proof results. Less-powerful or traditional-architecture devices could therefore, theoretically. protect their secure communications from attacks launched by quantum computers.
A. Di Falco, V. Mazzone, A. Cruz, and A. Fratalocchi, the inventors of the technique and authors of a paper in Nature, describing their findings, use correlated chaotic wavelengths as the basis of both the encryption key and the technique for not transmitting it between the two participants in the communication.
The sender and receiver of the encrypted message will communicate frequently, each time communicating a light pulse that will be unique in amplitude, frequency, and a variety of other qualities. Now, the pulses sent between the systems are never the same; in fact, physics tells us that, with randomization of the start conditions for the pulse, it would be impossible for them to be the same. Those differences are critical for the scheme to work.
The optical chips within the receiving and sending devices build a difference matrix that records the qualities of these light pulses. Those difference matrices will be essentially the same on each end of the transaction, and will be the basis for an encryption key of an arbitrary length. Even if someone could intercept the pulses used to fill the difference matrices, their system would not contain all the starting conditions used to seed the matrix, so illicit decryption would be impossible.
In the context of encryption, “perfect secrecy” is a description of a scheme, not a qualitative judgment. Invented back when the telegraph was the fastest form of communication, The Vernam cipher encrypts a message with a key that has three qualities: The key is as long as the message encrypted, The key is never reused in whole or in part, and The key is kept secret. Since the key is based on the difference in randomly generated light pulses, the second requirement for perfect secrecy is met. And because the key is never transmitted between the two ends of the conversation, the third quality required for perfect secrecy is satisfied.
The researchers who developed the technique present mathematical proof that the encryption is resistant to both time-domain and spectral attacks. More attack resistance comes in the physical implementation of the encryption chip, which turns a fingerprint into a random number seed through a process involving, among many other things, reflective nanodisks, chaotic billiards, and a fully chaotic fingerprint resonator.
IBM Researchers propose CRYSTALS system
In August 2019, IBM company announced its researchers had used its NIST submission, a system dubbed CRYSTALS (short for Cryptographic Suite for Algebraic Lattices) to successfully encrypt a magnetic-tape storage drive.
CRYSTALS generates its public and private keys with a category of equations called “lattice problems.” Although researchers have studied these equations since the 1980s, they have not developed either classical or quantum algorithms capable of defeating them. According to Lyubashevsky, one simple example of such a problem is to add three out of a set of five numbers together, give the sum to a friend and then ask that second party to determine which three numbers were added. “Of course, with five numbers, it’s not hard,” Lyubashevsky says. “But now imagine 1,000 numbers with 1,000 digits each, and I pick 500 of these numbers.”
IBM submitted CRYSTALS to the NIST contest in 2017. Yet it was not until this summer that the company announced it had used the method in a practical application by encrypting the data on a prototype storage drive. Although NIST may not ultimately select CRYSTALS as its new standardized cryptography technique, IBM still hopes to use the system for its own products. Its summer announcement, presented at the Second PQC Standardization Conference at the University of California, Santa Barbara, also included the news of a CRYSTALS modification that should let it encrypt cloud-based data. IBM hopes to use this improvement to render the IBM Cloud quantum-proof by 2020.
Because IBM has also made the system open-source, Lyubashevsky points out, any people interested in protecting their data can try it. “If they really do need their data to be secure 20 years from now, there really are some good options available for the cryptography that they can use,” he says.
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.”
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.”
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.
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.
References and Resources also include: