Anatoly Stojko |
Quantum Computing Promo

What is Post-Quantum Cryptography?

Nov. 5, 2020
Quantum computing could substantially raise the bar in terms of security, especially when it comes to cracking crypto codes.

This article is part of the Library Series: Dealing with Post-Quantum Cryptography Issues.

What you’ll learn:

  • The basics of post-quantum cryptography.
  • Why we need post-quantum cryptography (PQC).
  • What’s being done to develop it before quantum computers arrive.

The term quantum computing brings images of futuristic super computers along the lines of Star Trek. Quantum computing is still in its infancy, but it’s growing rapidly and the implications of its capabilities is significant especially in the realm of security.

To get more insight to this space, I talked with Helena Handschuh, a Fellow at Rambus Security.

What is quantum computing?

Today’s computers run on bits of data: either a 1 or a 0. Quantum computers use qubits, which can be in a quantum superposition of both states—meaning they can simultaneously be both a 1 and a 0. Quantum computers have many entangled qubits, and these lead to massive, exponential leaps in processing power, depending on how many qubits are in the computer. What this boils down to is that the encryption that once took computers over a human lifetime to break will be broken in mere days by quantum computers, due to the vast increase in processing speed.

So, will quantum computing defeat all current cryptography?

Not exactly. There are two main types of cryptography. Symmetric key cryptography, such as AES (Advanced Encryption Standard), will be able to resist quantum attack, but this type of cryptography has limitations. It requires that both endpoints share a key ahead of time. This isn’t the case when a user needs a secure connection from their browser to an e-commerce site, for example.

Public key cryptography, such as RSA (Rivest-Shamir-Adleman) and ECC (elliptic-curve cryptography), is built on “hard to solve” mathematical problems. For context, conventional computing needs hundreds or thousands of years to solve these problems, rendering them effectively “unbreakable.” But these will not be sufficient to protect data and devices in the quantum age. When quantum computers are fully developed, a computer using Shor’s algorithm, a polynomial-time quantum-computer algorithm for integer factorization, will be capable of cracking a 2048-bit RSA implementation in perhaps as little as a few days.

We expect quantum computing to reach its fully developed state within the next decade, by 2030. Since there are none in the field today, it’s difficult to predict what a quantum computer’s capabilities will be, so it’s important to develop a variety of post-quantum cryptography standards so that if one fails, the industry has additional standards to use.

What is post-quantum cryptography (PQC) and why is it important?

Post-quantum cryptography is centered around the algorithms that are designed to secure data in the age of quantum computing and beyond. It’s key that we develop these cryptography algorithms and purpose-built hardware cryptographic engines, as processing these algorithms in software may be too slow for certain high-throughput networking equipment. The new algorithms could be much more computationally intensive than our existing standards, including RSA and ECC, specifically if their implementations need to be protected against side-channel attacks.

What are some of the challenges being faced in developing post-quantum security algorithms?

These post-quantum cryptography algorithms are more complex than our current algorithms, and we at Rambus believe a revolution, rather than an evolution, of these existing algorithms is needed.

One of the main challenges is the size of the keys themselves. Current encryption and signature algorithms have keys that are a few hundred or thousand bits long. Some of the proposed post-quantum algorithms have key sizes of several tens of kilobytes up to a megabyte sometimes. This means we need to be able to store these keys efficiently.

When the public keys are used in public key infrastructure certificates (PKIs) and need to be communicated or stored locally on the end device, this will cost more bandwidth and memory, too. And bandwidth requirements will likely increase when using those schemes that have large size ciphertexts.

Another major challenge is going to be seen in IoT, where endpoint devices already have limited compute and processing power. As edge computing and the IoT continue to become more ubiquitous, it’ll be important that these devices are protected against quantum attacks. Rambus believes that the onus of processing encryption algorithms will fall on the hardware, as the software may not have the capacity to do so and is less secure by nature.

Another major challenge is to be able to assess the security of these new algorithms against both classical and quantum attacks. The underlying new mathematical primitives are not all that well-studied yet, and it’s an open problem to know exactly how secure these proposed algorithms are at this time.

What work is being done to ensure that our devices and data remain secured?

The National Institute of Standards and Technology (NIST) is sponsoring a competition to find, evaluate, and standardize a public-key cryptographic algorithm (or algorithms) that will stand up to the challenges posed by quantum computers. The second round of 26 contestants was narrowed down in the recent announcement of the third-round finalists and alternates, and the final portfolio is expected to be announced sometime in 2022.

We were very proud that Rambus had an entry called “Three Bears,” in the second round, which was developed by Mike Hamburg, one of our top security engineers. Sadly, “Three Bears” did not continue onto the third round, but we were delighted to have been a part of this consortium of technology innovation.

If we’re still so far away from quantum computers being a reality, why is there such a sense of urgency to get moving on this now?

It takes time to test and determine whether an algorithm will be able to withstand the force of a quantum-computer attack. Additionally, designers need time to implement the chosen algorithm standard(s) into their products, and this lead time can be as much as a couple of years for new products and up to 10 years for networking infrastructures and networking protocols.

It will also take many years to upgrade and deploy existing computing and network hardware on a broad scale. Secure endpoints (everything with a network connection) will require upgrading, which in some cases may mean new hardware, as software will not be fast or secure enough to process these new algorithms.

The impact on network architecture and infrastructure will be significant, due to the larger keys and cypher text, so these may also require upgrades or replacements.

With quantum computing being so new, how can we predict what a secure algorithm should be in order to protect against attacks by quantum computers?

The NIST competition includes rigorous testing processes to weed out those algorithms that will not be able to withstand a quantum-computer attack. This is why the contest spans such a long period of time, as each round includes an evaluation period for the cryptography community to analyze each candidate’s performance. This allows for the committee to collect data on how each algorithm may perform in the real world.

NIST notes that because quantum computers’ design relies on different scientific concepts than our current, conventional computers, post-quantum algorithms must also be based on different mathematical tools to resist against conventional and quantum attacks. It’s a green field for everyone, designers and analysts alike.

When will these algorithms be ready for deployment?

We expect that a winner(s) will be determined and standardized by 2022, after which designers can begin to implement the selected winning algorithms into their devices. These algorithms will be available to just about anyone, as they are public algorithms, but some countries may choose to create variants on it to keep their algorithms unique.

However, these variants on the standard will need to interconnect with others, so that each country will potentially submit their own version to the governing standards body, for example, to ETSI, the European telecommunication industry standards body. In turn, it will become part of the portfolio of available algorithms.

What other measures can be taken now to strengthen our current devices’ security?

At Rambus, we recommend building security into devices’ hardware with secure root of trust and other embedded security solutions to safeguard against software attacks. Devices can also utilize secure provisioning and cloud-based device key management solutions to protect their data against attacks.

Sponsored Recommendations


To join the conversation, and become an exclusive member of Electronic Design, create an account today!