Building a fully-functioning 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.

Ask the experts

Vadim Lyubashevsky

Vadim Lyubashevsky

IBM Research scientist

Gregory Neven

Gregory Neven

IBM Research scientist