How It Works
Veil implements ML-KEM (FIPS 203) for key encapsulation and ML-DSA (FIPS 204) for digital signatures. Both are built on lattice-based cryptography and rely on the hardness of the Module Learning With Errors (M-LWE) problem.
Why new cryptography?
Everything we use today (RSA, ECDSA, ECDH, Ed25519) rests on either integer factorization or the discrete logarithm problem. Shor's algorithm breaks both in polynomial time on a quantum computer.
Lattice problems don't have this weakness. The best known quantum algorithms barely improve over classical ones. NIST ran a multi-year competition and selected lattice-based schemes as the replacement standard.
Lattices and M-LWE
A lattice is a regular grid of points in 
-dimensional space, generated by integer combinations of basis vectors. The core hard problems (finding the shortest vector, or SVP, and the closest point to a target, or CVP) are exponentially hard in high dimensions, even for quantum computers.
M-LWE is a structured variant of these problems. Take a random public matrix 
, a secret vector 
with small entries, and a noise vector 
with small entries. Compute 
and publish 
. The challenge is recovering .
Without the noise, this is just linear algebra; Gaussian elimination handles it. The noise is what makes it hard: every equation has a small random error, and the system becomes intractable.
The "Module" part means we work over polynomial rings 
instead of plain integers. A single polynomial packs 256 coefficients, multiplication runs in 
via NTT, and the structure is still believed to be hard.
Polynomial rings
Every element of 
is a polynomial of degree < 256 with coefficients mod 
:
The quotient by 
means 
, wrapping high-degree terms back with a sign flip. This negacyclic structure is exactly what NTT needs for fast multiplication.
ML-KEM uses 
, ML-DSA uses 
. Both are NTT-friendly primes with roots of unity of the right order.
Number Theoretic Transform (NTT)
Naive polynomial multiplication in is 
. The NTT (essentially an FFT over a finite field) brings it down to . You evaluate both polynomials at roots of unity, multiply pointwise, then interpolate back.
In practice, most internal operations stay in NTT domain. Polynomials are transformed once and only converted back when needed.
ML-KEM
ML-KEM is a Key Encapsulation Mechanism: it packages a random shared secret into a ciphertext that only the private key holder can open.
Key generation samples a secret and computes the noisy product 
. To encapsulate, you encrypt a random message under the public key with fresh noise. To decapsulate, you use to strip away the noise and recover the message. This works because the secret and noise vectors are small enough that their inner products nearly cancel, leaving the message recoverable by rounding.
ML-DSA
ML-DSA is a Digital Signature Algorithm based on Fiat-Shamir with Aborts.
Key generation samples secrets 
and computes 
. To sign, you mask with a random 
, compute a challenge 
, and produce the response 
. If 
would leak information about 
, you reject and try again. Verification checks that 
is consistent with the challenge.
The rejection step is critical. Without it, signatures would gradually leak the secret key.
Security levels
NIST defines security categories relative to symmetric algorithms:
| Category | Equivalent Strength | ML-KEM | ML-DSA |
|---|---|---|---|
| 1 | AES-128 | ML-KEM-512 | ML-DSA-44 |
| 3 | AES-192 | ML-KEM-768 | ML-DSA-65 |
| 5 | AES-256 | ML-KEM-1024 | ML-DSA-87 |
Higher categories use larger matrices (
), which means bigger keys and slower operations, but more security margin.