Building a fully functional quantum computer is one of today’s most exciting scientific and engineering challenges. Accomplishing this long-sought-after goal could have a very positive effect on such areas of science as artificial intelligence and bioinformatics, which benefit from having access to vast computational resources.

Information security, on the other hand, will be very negatively impacted by this technological breakthrough. If a quantum computer with sufficiently many qubits were to appear today, virtually all electronic communication would become insecure. And even if such a device only appears several years from now, it will be able to compromise all secret communications currently stored.

Our research activities are focused on developing practical cryptographic solutions that are resistant to the threats posed by quantum computers. In particular, we focus on lattice-based cryptographic solutions.

card_4

Preparing for the next era of com­put­ing with quantum-safe cryptography

The effort to build a fully functional quantum computer is one of today’s most exciting engineering challenges.

Lattice-based cryptography

“Lattice-based cryptography” is an approach for constructing security primitives. It is based on problems from an area of mathematics called “geometry of numbers.”

Suppose that one is given a square, full-rank matrix A and a value b = Ax mod p, where x is a vector with 0/1 coefficients and p is a small (e.g. 13-bit) prime. One is then tasked with finding x. This problem has a unique solution x, which is actually quite easy to find by using Gaussian elimination.

On the other hand, if one is given a slightly “noisy” version of Ax, that is Ax+e mod p, where e is some random vector with 0/1 coefficients, then for matrices of large-enough dimension (say, around 512), this problem becomes surprisingly difficult.

This type of problem is related to both the subset sum and the learning parity with noise problems that have been widely studied since the 1980s and have not succumbed to any algorithmic attacks, either classical or quantum.

Quantum cryptography questions

When will quantum computers become available that are able to break today’s cryptographic schemes?

This is a difficult question. It has been suggested that millions of physical qubits will be required to create a sufficient number of logical qubits to attack today’s cryptography. The actual number of qubits required will depend on the quantum error rates achieved and the optimization of algorithm design. Significant innovations in these fields may radically reduce the number of physical qubits required, but they are very difficult to predict. A further consideration is that different cryptographic schemes have different vulnerabilities. Elliptic curve cryptography that use short keys, for example 192 bit ECDSA, will be at risk earlier than older schemes using longer keys (3072 bit RSA).

Which cryptographic schemes will be impacted?

Many of today’s public key-based cryptographic schemes are based two fundamental problems — the difficulty of factorizing integers and the difficulty of solving discrete logarithms. Public key algorithms based on these problems include RSA, DSA and ECDSA. There is a quantum algorithm called Shor’s algorithm that can solve these problems very efficiently, making algorithms based on these assumptions insecure. A second quantum algorithm called Grover’s algorithm reduces the security of some symmetric encryption schemes, but does not fundamentally break them.

What does this mean for security?

We use public key cryptographic schemes to protect the keys used for encrypting data and for authenticating things such as transactions, code and data. Public key-based schemes used today will be vulnerable to future quantum computers and therefore need to be changed.

Why is this a problem today and not in 10 years?

Data and code that we secure today has a certain time value. This ranges from a few seconds to a few decades, depending on the application. Encrypted data harvested today may contain sensitive data that will still be valuable in 30 years. Digital signatures used to protect electronic mortgage records may need to be secure for 30 years. Blockchain-based solutions protected with digital signatures have already been in existence for almost 10 years, and they will need to remain valid for many more. Computer systems that rely on digital signatures for code updates and patch validation may be in the field for decades. Digital passports and identity cards have lifetimes of 10 years. This means that we need to be applying schemes today that will be secure for decades into the future.

Are there cryptographic schemes available today that protect against quantum computers?

Yes, there are a number of cryptographic schemes that are currently thought to be quantum-safe. They are based on a different set of difficult problems that are not known to have efficient quantum solutions. These schemes include lattice-based cryptography, hash trees, multivariate equations, and super-singular isogeny elliptic curves.

Do I need a quantum computer scheme to run these new quantum-resistant schemes?

No. These schemes are designed to run on today’s computer architectures. In general, the terms quantum-safe cryptography and quantum-resistant cryptography refer to schemes that run on today’s classical computer architectures. There is often some confusion with quantum key distribution and quantum cryptography. Quantum key distribution is available today. It uses special hardware components and quantum mechanics that enables two parties to produce a shared random secret key, which is subsequently used in classical cryptographic protocols. Quantum cryptography refers to cryptographic schemes that run only on quantum computers.

Are quantum-resistant schemes a new field of research?

No, some of these schemes have been researched for many decades.

Are these quantum-resistant schemes standardized?

There are a number of efforts currently underway to standardize quantum-safe cryptography. The most notable of these is the NIST PQC process. IBM has submitted a number of algorithms to the NIST PQC process. Other standards organizations ramping up post-quantum efforts include ETSI, ISO and ANSI.

Which cryptographic primitives are being standardized?

New primitives will be standardized for key exchange, encryption and digital signatures.

When will standards be available?

The NIST PQC process is expected to take around 5–7 years due to the complexity in evaluating a wide range of cryptographic schemes.

Will a single technology be selected as a standard?

Probably not. It is possible that a number of schemes may be selected because no single scheme may be optimal for all cryptographic primitives.

What does this mean for me?

An enterprise or government needs to understand the implications for the data and systems that they operate. This typically involves a risk assessment that evaluates the time value of data currently being protected and the security systems used to provide that protection. Such a risk assessment would drive the development of a quantum-resistant readiness strategy and roadmap.

Vadim Lyubashevsky
Vadim Lyubashevsky
IBM Research scientist

Jonathan Bootle
Jonathan Bootle
Post-doctoral researcher

Cecilia Boschini
Cecilia Boschini
PhD student

Ngoc Khanh Nguyen
Ngoc Khanh Nguyen
PhD student

Gregor Seiler
Gregor Seiler
PhD student