Using AI to find post-quantum cryptography’s vulnerabilities

Research in cryptography, the science of securing information, must stay ahead of attacks in order to protect everyone’s data. Since current standards for public key cryptography may one day be vulnerable to attacks by large-scale quantum computers, researchers are proposing and testing new post-quantum cryptographic proposals based on hard problems in mathematics.

Today, Meta AI is sharing new research showing how one of the most promising proposals for a post-quantum cryptographic system may be vulnerable to attacks using transformers, a widely used AI architecture. That proposal, lattice-based cryptography, is based on a hard problem called learning with errors (LWE), which assumes that it is hard to learn a secret vector, given only noisy inner products with random vectors.

However, since machine learning (ML) is good at learning under noisy conditions, our research demonstrates how AI can be used to attack toy versions of these problems, opening a new approach to explore further. We used state-of-the-art AI techniques to test the resiliency of lattice-based cryptography and discovered that AI can defeat small- and medium-scale lattice-based cryptography applications. By uncovering these potential weaknesses now, we hope to help the research community develop more robust ways to safeguard information in the future.

Public key cryptography and the post-quantum era

Today’s widely deployed public key cryptographic systems are mostly based on two hard problems — the factorization of integers into primes, and the discrete logarithm problem on elliptic curves. If you want to share a secret with three friends, you could just tell them. But what if you want to securely share that secret with anyone, even a stranger? Traditional cryptography enables correspondents to securely share a secret key that they can use to encode and decode their messages. The communications between them are protected because only they have that key.

Once quantum computers have been developed at a large enough scale, they can be used to efficiently attack the hard problems used in public key cryptographic systems deployed today. That is why we need new problems for protecting secrets. The U.S. National Institute of Standards and Technology (NIST) has been running a multiyear competition to select new post-quantum cryptosystems (PQC), involving researchers from industry, government, and universities around the world. This month, NIST announced that it will recommend three lattice-based schemes for standardization. Lattice-based cryptography, based on the difficulty of learning secrets with errors added to the computations (LWE), has been a leading candidate for PQC. Meta AI is contributing to this initiative by exploring potential AI-related weaknesses in LWE.

Using AI to recover secrets in lattice-based cryptography

Given a lot of noisy data, ML can still learn patterns. We introduce a technique called SALSA, or secret-recovery attacks on LWE via seq2seq models with attention. SALSA has three modules:

- A transformer model M, which is trained to predict the result of LWE encryption

- A secret recovery algorithm, which tries to guess the secret from the transformer

- A secret verification procedure, which checks whether the guess is correct

Using examples of LWE messages, we train a language model to mimic the encoder (i.e., to produce the ciphertext given only the randomness, not the secret). Then, we use the trained model to design a distinguisher to recover the secret. SALSA evaluates the guesses by verifying that residues computed from LWE samples have a small standard deviation. If they do, the secret has been recovered and SALSA stops. If they don’t, SALSA continues its attempts to recover the secret.

To make this method work, we needed to first demonstrate that transformers can learn to perform modular arithmetic on integers and vectors, a challenging task that had not yet been accomplished successfully. Our research also shows how these techniques yield a practical attack on LWE and demonstrates its efficacy in the cryptanalysis of small and midsize LWE instances with sparse binary secrets. A secret is a vector of integers. A binary vector has entries equal to 0 or 1; a sparse binary vector, however, has most of its coordinates equal to zero. Industrial implementations of LWE-based homomorphic encryption would have dimensions ranging from 1,024 to 2,048 or larger and a sparsity of a few percent. Right now, SALSA doesn’t yet succeed against that large dimension, but it can fully recover secrets up to n=128 and densities between 2 percent and 8 percent.

One key conclusion from these experiments is that transformer models can compromise the security of these cryptosystems even without being trained to high accuracy. In most cases, we only need the model to begin to learn in order for the attack to succeed. This is important because transformers typically need a large number of samples to be trained, since they learn everything from scratch. In real-life situations, an attacker would try to collect examples and use them to train a model. Our research shows that in most cases the model needs very little training to succeed, which would make it easier for would-be attackers.

Charting the future of cryptography

With SALSA, we are attacking lattice-based cryptography in a new way, showing that full-scale cryptosystems may be vulnerable as the power of ML models grows. Currently, SALSA doesn’t break industrial-strength implementations of lattice-based cryptography, but this attack shows that there are chinks in its armor.

"We gain confidence by active research such as this, and new results in the community," said Lily Chen, leader of NIST's Cryptographic Technology Group.

Cryptography has been around since the dawn of civilization. While one of the earliest instances has been traced back to unusual symbols mixed with hieroglyphics in ancient Egypt, the practice has evolved over thousands of years, moving from coded messages in a Polybius square, in which each number corresponds to a letter, to the sophisticated systems we use today to safeguard our digital lives, from passwords to e-commerce purchases. But doing this well requires the entire industry to stay steps ahead of emerging threats by developing new methods for cryptography and conducting extensive research on hard problems at the start.

Establishing quantum-resistant cryptographic solutions will be an ongoing process for researchers and practitioners over the next few decades. A lattice-based cryptographic system depends on a lot of parameters, including the dimension of the keys, whether the secret is binary or sparse, the size of the error values, and some computational factors. We still believe a lattice-based approach is a viable way forward to protect data and privacy. But we need to continue to explore the vulnerabilities to protect against them and to recommend wise parameter choices. Our work demonstrates a new type of vulnerability, which the community of researchers will continue to explore in future work. We look forward to continuing to work with the community to ensure that the next cryptography standard will reliably safeguard data well into the future.

We'd like to acknowledge the contributions of Emily Wenger and Mingjie Chen to this research.

Learn more about SALSA by reading our paper