A Peek Inside Post-Quantum Keys

If you have an ECDSA public key, you know precisely what is in it: the name of a curve and an elliptic curve point, which is itself a pair of large integers. Similarly, when we think of an RSA key or signature or ciphertext, we think of a bunch of integers packed together, and we are not wrong at all!

These representations are complete and satisfy developers, devices, cryptography experts, colleagues and extended family. We can comfortably say we know what is inside an RSA key, apart from "just bytes".

Is something going to change with migration to post-quantum cryptography? What is inside an ML-DSA key sitting on our system? What are these ML-KEM capsules made of? Does this migration imply a paradigm change, or can we all keep thinking about things we can understand at different levels?

All things considered, the only way we know how to do public-key cryptography is to pack increasingly abstract mathematical objects into what we call keys, ciphertexts, signatures, and the like.

We are still doing the same in this new era - where before we fit large integers or elliptic curve points, we are going to fit polynomial vectors and teach our devices to manipulate them.

(By the way, this is already happening. If you have a modern browser, when you connect to Fortanix Saas endpoints, your device picks a module lattice element instead of an elliptic curve point and sends it over the insecure line, so that this sessions' data is exchanged securely against post-quantum attackers.)

Public-key cryptography from raw materials

In public-key protocols, there are participants with unique abilities (sign, decrypt, decapsulate), which we model by granting each of them access to different mathematical trapdoors.

Whenever your device and a server attempt to connect, they convince each other they have unique abilities. After this ritual, they can secretly communicate over the otherwise insecure Internet lines.

To this end, hundreds or thousands of times a day, your device usually picks random points on some globally known elliptic curve and sends it to servers. This is known to be potentially insecure against quantum attackers, and to defend, devices now have to play another game.

So, what changes, exactly? Protocols will not suffer substantiates just yet - we still sign, decrypt, decap, and decapsulate. Machines, however, will have to manipulate different raw materials to do the same thing: apart from large integers, finite fields, and elliptic curve points, they now must deal with module lattices, codes, and isogenies.

In order to hold and manipulate these more abstract objects, some additional work is due by developers. On the processor level, everything is already set up to deal with bytes and integers and symmetric cryptography; things they will have to build upon to implement PQC algorithms.

It turns out that module lattices - what was ruled as the main crypto material for PQC by NIST - is quite familiar to implementors.

Module lattice elements - what do they look like?

An element of a module lattice is a handful of polynomials of given degree, where their integer coefficients follow some rules. The way to manipulate and combine these polynomials to quite natural: no big integers, no primality testing, no mysterious points at infinity, no addition formulae - just what looks like linear algebra on steroids.

A necessary word of caution; implementing this securely needs to be carried out by experts - much like implementing RSA or ECDH.

For instance, in ML-KEM-768, a public key contains one polynomial vector: three polynomials of degree 256 and with integer coefficients between -1664 and +1664.

Here, I created an ML-KEM-768 Security Object inside Fortanix DSM, and this is the one module lattice element that was packed into the public key:

 461 + 1142x + 589x² + 1663x³ + ... + 834x²⁵⁴ -906x²⁵⁵,
-1436 - 783x + 1456x² -601x³ + ... - 345x²⁵⁴ - 864x²⁵⁵,
-26+365x + 1329x² - 929 x³ + ... - 1373x²⁵⁴ - 250x²⁵⁵.

The corresponding secret key is another lattice element that probably looks similar to

-x + 2x⁴ + 2x⁵ + x¹⁰ -2x¹² + ... - x²⁵² - x²⁵⁵,
1 + 2x⁶ + x⁸ - 2x⁹ - x¹⁰ + ... + 2x²⁵⁴ - x²⁵⁵,
-2 + x² - x³ - 2x⁸ + 2x¹¹ + ... + x²⁵² - 2x²⁵⁵,

I say “probably” because I cannot extract it from Fortanix DSM - I did not mark the Security object as exportable upon creation - and the large quantum computer I forgot in my other pants would not be able to help me either.

(In hopes of fully satisfying the reader's curiosity, some more facts follow: an ML-KEM-768 capsule contains two lattice elements. An ML-KEM-768 private key contains one polynomial vector and a copy of the public key. An ML-DSA-65 key pair contains even more of these lattice elements, one for the public key and three for the private key.)

How are these polynomial vectors created, how do they relate to each other and what are the known implementation pitfalls are all topics for a cryptography afternoon, but we can certainly discuss how to represent these on our machines.

We mentioned that coefficients of these polynomials follow some rules.

This comes from the fact that polynomials are sampled from several statistical distributions in the ring using the randomness in your system, and ensuring that elements come from the correct distributions and stay there after operation is important.

With this in mind, a type-safe language with controlled mutability like Rust is an ideal candidate for secure implementations.

In ML-KEM and ML-DSA, we distinguish several types of polynomials (remember that there are always 256 integer coefficients). Sometimes, coefficients are randomly distributed in moderately large intervals like [-4190208, +4190208] or [-1664, 1664].

In other situations, polynomials have exactly τ coefficients in {-1, 1} and the rest are 0 (where τ is 39, 49 or 60). Furthermore, there is also need for polynomials whose coefficients lie in small integer intervals, like [-4, 4], following a binomial distribution centered about 0. Other times, a same element has to be reinterpreted with another set of representatives modulo q (e.g. positive versus centered about 0).

Rust again

Most implementations of ML-{KEM,DSA} just use arrays of integers for these polynomials, and make sure that everything is correct. Until there is formal verification of such implementations, bugs cannot be ruled out. The array approach is inferior than using strict types and compile-time type safety - things for which we use Rust nowadays. It is also quite comfortable!

Here is an idea of an abstraction that might be of interest to developers:

Use a trait 'Alignment' to indicate representatives of sets of integers. Another trait 'Coefficient' and several types implementing it:

- Binary,
- Ternary,
- Modular<const Q: u32, A: Alignment>,
- Bounded<const M: u32, A: Alignment>.

A trait Domain is used to distinguish whether a polynomial is in number-theoretic transform (NTT) domain or not.

With something like this in place, a single struct 'Poly<C: Coeff, D: Domain>' can be used to represent most types of polynomials above, with type safety:

'Poly<Modular<3329, Positive>, NotNtt>' means that coefficients are in [0, 3328] and the polynomial is not in NTT form.

The internal 'sigDecode' algorithm in 'ML-DSA' should produce:

- c: [Binary, C_LEN],
- z: Poly<Bounded<lambda_1, Centered>, NotNtt>,
- h: Poly<Modular<2, Positive>, NotNtt>

And so on.

So, now you know it, your post-quantum cryptographic material typically holds a bunch of polynomials, and there are ways to make implementations even more secure. Fortanix supports and uses NIST standardized post-quantum algorithms and the full CNSA 2.0 suite. Get in touch with us!