Post-quantum cryptography in a game scripting language sounds like a joke. It isn't one any more.
This is the first ML-KEM for Luau: the key exchange NIST standardised as FIPS 203, written in pure Luau and built from the first line to compete with native libraries like Go's crypto/mlkem. All three parameter sets. About 400 lines. No dependencies. Every operation at every security level finishes in under a millisecond:
| Parameter set | generateKeys | encapsulate | decapsulate |
|---|---|---|---|
| ML-KEM-512 | 313 µs | 326 µs | 363 µs |
| ML-KEM-768 | 506 µs | 545 µs | 594 µs |
| ML-KEM-1024 | 781 µs | 828 µs | 886 µs |
Repo: Rukioyuza/MLKEM
A full ML-KEM-768 key exchange costs about 1.1 ms. That is competitively fast by any standard, from a VM that was never meant to do this. Getting there was the hardest programming I've done, and this post walks through all of it.
What you're up against
ML-KEM needs two things from a runtime, and it needs them fast.
Keccak. Every random-looking byte in ML-KEM comes from SHA-3 or SHAKE: the matrix, the noise, the key hashes, the shared secret. Keccak is built on 64-bit lanes. Its whole design is XOR, AND and rotation of 64-bit words.
Polynomial arithmetic. Polynomials with 256 coefficients modulo 3329, multiplied through a number-theoretic transform.
Now look at what Luau gives you. Numbers are doubles. The bit32 library stops at 32 bits. Buffers read and write 32 bits at most. No 64-bit rotate, no SIMD, no assembly, no intrinsics.
Native libraries get 64-bit registers, compiled machine code, and often hand-written assembly for Keccak. I got bit32.lrotate and a buffer.
And Keccak is nearly all of the runtime. One ML-KEM-768 key generation runs the Keccak permutation a little over 40 times: once to expand the seed, about 27 times to sample the matrix, 6 for noise, 9 to hash the public key. Each permutation is 24 rounds over 25 lanes. That is roughly 50,000 half-lane rotations inside a 506 µs budget.
If the permutation is slow, nothing else matters. So that's where the fight was.
Keccak with no 64-bit words
The obvious approach stores each lane as a high half and a low half. Then every rotation needs shifts on both halves, with bits carried across the middle. Slow, branchy, and easy to get wrong.
I threw that out and used bit interleaving. Each 64-bit lane is stored as two 32-bit words: one holds the bits at even positions, the other holds the bits at odd positions.
It sounds like it makes everything harder. Watch what it does to rotation:
- Rotate by an even amount
2k: even bits stay even, odd bits stay odd. Rotate each half byk. - Rotate by an odd amount
2k + 1: the halves trade places. The old odd half, rotated byk + 1, becomes the new even half. The old even half, rotated byk, becomes the new odd half.
Every 64-bit rotation becomes exactly two bit32.lrotate calls. Nothing is carried between them:
if amount % 2 == 0 then -- even 64-bit rotation: rotate both halves buffer.writeu32(moved, target, bit32.lrotate(even, half)) buffer.writeu32(moved, target + 4, bit32.lrotate(odd, half)) else -- odd rotation: the halves swap buffer.writeu32(moved, target, bit32.lrotate(odd, half + 1)) buffer.writeu32(moved, target + 4, bit32.lrotate(even, half)) end XOR and AND don't care how bits are arranged, so theta and chi run on the halves untouched. The single rotate-by-1 inside theta falls out of the same rule:
local mixEven = bit32.bxor(buffer.readu32(parity, left), bit32.lrotate(buffer.readu32(parity, right + 4), 1)) local mixOdd = bit32.bxor(buffer.readu32(parity, left + 4), buffer.readu32(parity, right)) Then the steps get fused. Theta's mixing, rho's rotation and pi's shuffle all happen in one pass: each lane is mixed, rotated, and written straight to its final position in a second buffer. Chi reads from that buffer back into the state. No lane moves twice.
The bill comes due at the edges
Interleaved state is fast to permute and unreadable. Input arrives as plain bytes. Output must leave as plain bytes.
Pulling bits apart one at a time would burn everything the permutation saved. So there are two lookup tables of 65,536 entries each.
The first takes 16 input bits and returns the even bits and the odd bits already separated, packed into one 32-bit word. Two lookups, one shift, and you have both halves of a 32-bit chunk. The second does the reverse, spreading 16 bits onto even positions so two results can be OR'd back into plain bytes.
Absorbing a lane is four lookups. Squeezing one is four more. The tables cost 512 KB, built once at load. Worth every byte.
No pasted constants
There isn't a single hard-coded round constant, rotation offset or pi index in the file. The round constants come out of the spec's LFSR at load time, already interleaved. The rotation offsets come from the triangular-number walk around the state.
That was deliberate. Every pasted constant is a place for a typo, and in Keccak a typo doesn't crash. It hashes.
Even padding has a trap. The domain byte goes after the message and 0x80 goes on the last byte of the block. When the message is one byte short of a full block, they land on the same byte and have to be OR'd together. Miss it and you pass every test except one length.
Polynomials: stop fighting the doubles
Every C implementation of ML-KEM uses Montgomery or Barrett reduction to dodge integer division. I spent a while assuming I needed the same.
I didn't. Every value in Luau is already a double. The modulus is 3329, so the product of two coefficients tops out near 11 million, and doubles are exact up to 2^53. The butterfly is the textbook formula:
local upper = zeta * buffer.readu16(polynomial, offset + span) % MODULUS local lower = buffer.readu16(polynomial, offset) buffer.writeu16(polynomial, offset, (lower + upper) % MODULUS) buffer.writeu16(polynomial, offset + span, (lower - upper) % MODULUS) Luau's % is floored, so a negative difference wraps into range with no branch. Seven layers of that, 127 roots of unity generated at load in bit-reversed order, and the forward transform is done.
ML-KEM's transform stops one layer early. You don't end up with 256 numbers, you end up with 128 tiny polynomials of degree one, each living modulo X² − ζ for a different ζ, with the sign flipping on every other pair. Multiplication means 128 of those little products.
Here it is fused with accumulation: multiplyAccumulate(sum, left, right) adds the product directly into the running sum. The worst intermediate is three coefficients multiplied together, about 3.7 × 10^10, still exact. No temporary polynomial ever exists.
Compression and byte packing are fused the same way. One loop rounds each coefficient down to 1, 4, 5, 10 or 11 bits and feeds it into a bit accumulator. The decoder reads four bytes, shifts and masks, with the read offset clamped so the last coefficient can't run off the end of the buffer.
Sampling a word at a time
Matrix entries come from SHAKE128 by rejection sampling. Every three bytes hold two 12-bit candidates, so one 32-bit read at a three-byte stride grabs both.
Noise is a centered binomial: count some random bits, subtract a count of other random bits. Bit by bit, that is hundreds of iterations per polynomial. Instead, one masked add counts every field in a 32-bit word at once:
local sums = bit32.band(word, pattern) + bit32.band(bit32.rshift(word, 1), pattern) -- per-field popcount That line produces the counts for eight coefficients. ML-KEM-512 uses a wider distribution, three bits per count, which packs four coefficients into three bytes. The noise buffer is 196 bytes instead of 192 purely so the final 4-byte read has somewhere to land.
The matrix that never exists
ML-KEM multiplies a vector of polynomials by a matrix of polynomials. For ML-KEM-1024, that matrix is 16 polynomials of freshly squeezed SHAKE output.
This implementation never stores it. Each entry is sampled into one scratch polynomial, multiplied into the running sum, and overwritten by the next:
sampleUniform() multiplyAccumulate(products[row], sampled, secrets[column]) Encryption needs the transposed matrix. That is the same loop with two index bytes swapped.
All working memory is allocated once when the module loads. A call to encapsulate allocates exactly two buffers, the shared secret and the ciphertext, and nothing else. The garbage collector never shows up in the timings, which is why the 10th and 90th percentiles sit within a few percent of the median.
Decapsulation
Decapsulation decrypts, re-encrypts what it got, and compares against the ciphertext it was handed. If they differ, it returns a pseudorandom value derived from a secret seed instead of an error. An attacker feeding it forged ciphertexts learns nothing.
The comparison ORs together the XOR of every 4-byte word instead of stopping at the first mismatch, and the rejection value is computed every time, match or not.
Why this was so gruelling
Cryptography gives no partial credit.
A sorting bug gives you a mostly sorted list. A layout bug gives you a button in the wrong place. A Keccak bug gives you 32 bytes that look exactly as random as the correct answer. There is no "close".
Now stack the layers. The shared secret is wrong. Is it the interleave table? A rotation offset? The padding byte? A root of unity in the wrong slot? The sign on the base multiplication? The rounding constant in compression? The matrix indices the wrong way round, which is a mistake famous enough that an early draft of the standard itself made it? Every one of those is a single character in the source. Every one produces the same symptom.
Then the optimisations turn on you. Interleaving means you can't print the state and compare it to a reference dump. Fusing rho and pi means there is no intermediate state to look at. Fusing multiply and accumulate means there is no product to check. Never storing the matrix means there is no matrix to inspect. Every trick that bought microseconds removed a place to put a breakpoint.
And nothing throws. A value that drifts past 32 bits is silently truncated by bit32. A shift that is off by one still returns a number. A buffer offset that is off by four still reads valid memory. The program runs to completion, cheerfully, and hands you garbage.
So you debug bottom-up and trust nothing. Get one permutation right. Then one hash. Then one polynomial. Then one transform and its inverse. Then one sample. Only then does the scheme on top have a chance. And every time you make something faster, you prove it all again.
Every microsecond in that table was bought one at a time.
Try it
local MLKEM = require(path.to.MLKEM) local kem = MLKEM[768] -- seed, rejectionSeed and randomness are 32-byte buffers you supply local encapsulationKey, decapsulationKey = kem.generateKeys(seed, rejectionSeed) local sharedSecret, ciphertext = kem.encapsulate(encapsulationKey, randomness) local sameSecret = kem.decapsulate(decapsulationKey, ciphertext) Code is at github.com/Rukioyuza/MLKEM.