Lattice Problems

A Class of Trapdoor Problems for Post-Quantum Cryptography

In order to protect information with cryptography, you need what are called ephemeral keys — keys that are only used once. They must be adequately long, and they must be generated with a good source of entropy or randomness. They must appear to be completely random, so any attacker has no information about where to start guessing.

Then you also need two types of cryptographic algorithms:

Selecting the Symmetric Algorithm — Protecting the Data

Short answer: It's 2025. Use AES-256 in an appropriate mode. Unless you prefer an authenticated stream cipher, in which case use ChaCha20-Poly1305.

Use a 256-bit key unless you are using AES with large files and somehow your platform's processor doesn't have AES instructions and you're awfully worried, perhaps overly worried, about speed.

Block ciphers must be used in some specified mode, and this mode must be carefully selected. Yes, there are legitimate uses for Electronic Codebook or ECB mode, but it's very insecure for most purposes. Cipher Block Chaining or CBC, once thought to be a good default choice, is now known to be insecure in some (but not all!) settings. AES-GCM or Galois/Counter Mode is the usual choice for TLS, as with a browser. AES-CCMP is the usual choice for 802.11 or Wi-Fi. And so on.

The Wikipedia page on block cipher modes has a basic overview. For the full details see "Evaluation of Some Blockcipher Modes of Operation" by Phillip Rogaway, University of California, Davis. It's a 159–page evaluation carried out for the Cryptography Research and Evaluation Committees for the Government of Japan.

Selecting the Asymmetric Algorithm — Protecting the Keys

An asymmetric cipher gets its security from a trapdoor function. That's a math problem that is extremely more difficult to solve in one direction than the other.

Remember that computers are extremely fast at arithmetic, especially the integer arithmetic that will be used to encrypt and decrypt binary data.

Addition and subtraction do not provide a trapdoor function. Addition and subtraction run at the same speed. Neither do multiplication and division provide a trapdoor. Long division is harder and slower for us humans to do with pencil and paper, and it may take more machine instructions for a computer to divide numbers, but not enormously more. The difficulty of reversing a trapdoor function needs to increase exponentially with problem size.

Multiplying and factoring, however, do provide a trapdoor function. A computer can pretty quickly multiply two 300-digit prime numbers to get a roughly 600-digit result. But it would take an enormous amount of calculation to start with the 600-digit number and find its two prime factors. That's how RSA gets its security.

Some problems based on elliptic curves also provide a trapdoor function. That's how Elliptic-Curve Cryptography or ECC works. ECC can provide strength roughly equal to RSA while using much shorter keys.

Security level, usually expressed as some number of "bits of security", estimates how much work an attacker would have to expend to discover your key — "n-bit security" means that an attacker would have to perform, on average, 2ⁿ operations to break it.

For AES, the security level is the same as the key length. AES-GCM-256 provides 256-bit security, and so on for shorter keys. NIST Special Publication 800-57. Here's a summary:

However, Quantum Computing Could Break RSA and ECC

We have had Shor's Algorithm since 1994. And it's actually three related algorithms, and collectively they solve the factoring problem (RSA) along with Diffie-Hellman and elliptic-curve algorithms. Shor's Algorithm requires a quantum computer with an adequate number of qubits with adequate stability and noise tolerance to avoid quantum decoherence. We don't yet have the hardware needed for practical problems.

In 2001, a quantum computer was able to factor 15 into 3×5.

In 2012, a quantum computer was able to factor 21 into 3×7.

In 2019, There was an attempt to factor 35, but it failed due to accumulated noise. (Spoiler alert: the answer is 5×7)

We know that Shor's Algorithm would work. It's very challenging math, but other mathematicians have proven that it would solve the problem.

That is, if we ever have an adequately large and stable quantum computer on which to run it.

However, we need to start using algorithms resistant to quantum attack now, just in case an adequately powerful and stable quantum computer appears tomorrow. There's also the fact that intelligence agencies and other threats operate with a "Collect now, decrypt later" approach. All your data and communications protected with RSA or ECC in the past could be exposed when quantum attacks become adequately practical.

We need what are called quantum-safe or post-quantum algorithms. You'll see references to PQC, meaning post-quantum cryptography.

And, good news — we have some quantum-safe algorithms! As far as we know! And, people are working to expand the field. I have a page describing how to set up web service with post-quantum cryptography.

Lattice Problems to the Rescue

A lattice is a mathematical concept.

A lattice in the real coordinate space ℝⁿ is an infinite set of points for which coordinate-wise addition or subtraction of any two points in the lattice produces another lattice point. It's an infinitely large repeating grid of points with arbitrary spacing and alignment.

Geometry and, more importantly here, group theory, have studied several problems based on lattices. Some are thought to be NP-hard, meaning that if P ≠ NP as we suspect, there would be no polynomial-time algorithms to solve them. And in that case, they become so impractically difficult with increased input size or complexity that we can safely rely on them as security mechanisms.

You can think of a lattice as being defined by some basis, a collection of vectors. As many vectors as you have dimensions, but let's keep this in two dimensions so I can show it to you as simple 2-D pictures.

Here is an origin point and two vectors of equal length, red and green, red pointing up and green to the right. And in the second picture, the result of generating a lattice from that. The origin in black, the other lattice points in blue-green. It's a nice regular square grid.

The vectors don't have to have any particular alignment with each other, or with the coordinate space.

But remember, a lattice is based on the real coordinate space ℝⁿ. That's an infinite set of points based on arbitrary real numbers.

I'm using MathJax to do math within HTML.

Learning With Errors is a category of lattice problem that could be used in cryptography. It represents secret information as a set of equations with errors — the actual value of the secret is hidden by the noise added to the representation. It's the problem of inferring the linear \(n\)-ary function \(f\) over a finite ring from provided samples $$ y_i = f(x_i), $$ some of which are erroneous. The errors, the deviation from equality, follow some known noise model. The problem comes down to finding the function \(f\) or some close approximation with high probability.

Learning With Errors or LWE was introduced in 2005, and brought its author the 2018 Gödel Prize for outstanding computer science work. Like RSA with small primes or elliptic-curve cryptography over a small field, a simplified LWE scenario makes the concepts fairly easy to grasp. But then the practical implementations enormously enlarge the search space, making it extremely difficult to find a solution.

Amazon 0792376889

Amazon 0265271045

So here's how this gets used. Let's say that Alice wants to communicate securely with Bob, because that's how we always frame it:

Alice comes up with a basis for a brand-new lattice, one whose vectors have never been used before. Probably. By "brand-new", I mean "ephemeral", of course. We're assuming that it has never been used and that it won't happen to be used again in the future. Probably. We're dealing with real numbers here, so it's the fault of the software developer if these aren't unpredictable and always unique.

Well, unpredictable enough, and unique over an adequately long period. Nothing is perfect.

Alice generates the lattice that the basis defines, and then selects one of out of the infinite number of points to serve as Alice's private key.

Then Alice randomly selects a point in the vicinity of the private-key point. It must be closer to the private-key point than to any other point, and it must be as arbitrarily precise and as random as Alice can manage. The random offset is the noise, the random deviation of \( y_i \) away from equality with \( f(x_i) \). That randomly selected point plus the lattice basis become Alice's public key.

Here's a graphical depiction of the public key information. The red and green vectors define the lattice, as before. The turquoise point is the randomly-chosen point in the vicinity of a selected lattice point. In some sense, this is both a message to the legitimate communicator and a challenge to any would-be attacker. The legitimate communicator will use the public key to encrypt messages so that only Alice can read them. An attacker would have to solve the impractically difficult problem that it represents.

Bob obtains Alice's public key, probably by its appearance within Alice's connection request. Alice's public key would be the set of numbers corresponding to the above picture — the randomly generated lattice and the randomly selected selected point. Bob can now generate an ephemeral symmetric key to be used on this communication only, encrypt that symmetric key using Alice's public asymmetric key, and send that ciphertext to Alice. It's a Key Encapsulation Mechanism, a way for Bob to send the ephemeral symmetric key in a way that only Alice can decrypt and read.

Alice knows all the ephemeral public/private key pairs in current use with connections being established, running, or shutting down, and also which key pair is associated with Bob's IP address or email address or whatever is relevant here.

Alice can decrypt the message containing the symmetric session key. That key is used with AES to encrypt all the following messages between the two. Good. Things are still working. We haven't broken anything.

Speaking of breaking things, there are two major worries in this overall situation. First, that an intruder could discover Alice's private key and thereby do all sorts of interception and archiving, masquerading, and modifying of traffic. Second, that Bob, once thought to be trustworthy, could turn bad and do the same, and it seems like he has an advantage by being closer to the situation than the outsider.

No, we're safe.

Either Bob or the would-be intruder would have to solve the impractically difficult problem of:

Given a lattice in ℝⁿ with this basis, what are the coordinates of the lattice point closest to these coordinates?

Nothing is perfect. This problem is not impossible to solve. Therefore our security could be violated. However...

Again, remember that ℝⁿ means arbitrarily specific coordinates in an infinitely large space.

And, remember that I mentioned how I was using two-dimensional images to keep the explanation simple. Now that you know how this lattice problem works, consider how much more difficult it would be in a higher number of dimensions. Three dimensions? Four? How about a lattice with 1,000 dimensions or more?

If you worry that it's inadequately secure, because it's inadequately difficult to find the private key point, then you should be using a higher number of dimensions and being more random with lattice generation.

U.S. NIST made a final selection of post-quantum algorithms in August 2024. The liboqs Open Quantum-Safe shared library of PQC functions soon supported the algorithms under the NIST naming conventions. By early 2025, more of the needed components were available, including support in both Chrome and Firefox.

NIST specified a KEM or Key-Encapsulation Mechanism based on the M-LWE or Module Learning With Errors problem. There are variants with different security levels. All are supported by the liboqs shared library, along with many others. Browsers began by supporting ML-KEM-768, with one providing roughly 192 bits of security.

"NIST finalizes trio of post-quantum encryption standards"
The Register
FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard FIPS 204: Module-Lattice-Based Digital Signature Standard FIPS 205: Stateless Hash-Based Digital Signature Standard NIST Frequently-Asked Questions on Post-Quantum Cryptography "NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption"

And so, we now have at least an initial solution for quantum-safe or post-quantum cryptography. Look down in the footer of this page. If you see:
  Crypto: ML-KEM-768/X25519
toward the lower right corner, then your browser used the ML-KEM-768 lattice-based quantum-safe key encapsulation method along with the X25519 elliptic-curve cipher to agree on an ephemeral symmetric key used for this page load only. That way if a sudden quantum computing breakthrough invalidates ECC, or if cryptographers are embarrassed to discover a weakness in ML-KEM-768, our connection is still protected.