Amar Akshat · github.com/amarshat
ML-DSA spends most of its arithmetic multiplying polynomials in
Z_q[X]/(X^256+1), with q = 8380417. It does this the standard way:
transform both operands with the NTT, multiply coefficient by
coefficient, transform back. Earlier work in this repository proved that
PQClean’s reference C computes the FIPS 204 forward and inverse NTT.
That says the transform is the transform. It does not say that
transform, pointwise multiply and inverse, composed, give you the
product. This post closes that gap for the models SAW proved the C
functions equal to, and says where in the scheme the result applies. How
sign.c composes the C functions is read from the source,
not proved; the table below and docs/COMPOSITION.md
say exactly where that line falls.
Everything here is in the repository and
reproduces from a make target. The target is PQClean’s
ML-DSA-44 clean implementation at commit
202a8f9. reduce.c, ntt.c,
poly.c and polyvec.c are vendored unmodified
with SHA-256 pinned; sign.c and packing.c are
not vendored.
For polynomials a and b whose coefficients all satisfy |c| < q, on
the Cryptol models that SAW proves equal to the C functions
ntt, poly_pointwise_montgomery and
invntt_tomont:
invntt(pointwise(ntt a, ntt b)) = a * b in Z_q[X]/(X^256+1)
Here * and the reduction mod X^256+1 are the polynomial
multiplication and remainder from Isabelle’s standard library, at a type
of integers mod 8380417. They are not a convolution formula written for
this project, so the right-hand side is not something the proof could
have been tuned to. The theorem is ntt_mult_ring in Conv_Bridge.thy.
The matrix products need a second form, because ML-DSA samples the
matrix A directly in NTT form. Its rows are never the output of
ntt, so the theorem above does not apply to them. Each row
of Ay is computed as four pointwise products summed with
poly_add, then poly_reduce, then the inverse.
The theorem acc_mult_ring in Acc_Bridge.thy
says: for any polynomials A_i whose transforms are the sampled rows, the
composed models’ output for that row is A_1y_1 + A_2y_2 +
A_3y_3 + A_4*y_4 mod X^256+1. Every row has such A_i, because the
transform is onto mod q, and that is proved too
(ntt_int_surj). This is FIPS 204’s NTT^-1(A_hat o NTT(y))
read as polynomials.
The Montgomery bookkeeping is proved rather than assumed.
poly_pointwise_montgomery leaves a factor 2^-32.
invntt_tomont multiplies by 41978 and leaves another 2^-32.
The unnormalised inverse leaves a factor 256. Since 41978 * 256 = 2^64
mod q, these cancel exactly, and the theorem has no leftover scale. The
intermediate bounds are proved as well: forward outputs are not reduced
and can reach 9q, and the proof checks that the products of two such
values still fit montgomery_reduce’s input range, that four
pointwise outputs added together cannot overflow a 32-bit int, and that
the sum is inside reduce32’s precondition.
| Operation | Where | Each function on the path | Composed model computes the product | sign.c calls them in that order, on those inputs |
|---|---|---|---|---|
| A*s1 | key generation | proved (SAW) | proved (acc_mult_ring) |
read from the source |
| A*y | signing | proved (SAW) | proved (acc_mult_ring) |
read from the source |
| cs1, cs2, c*t0 | signing | proved (SAW) | proved (ntt_mult_ring) |
read from the source |
| Az - ct1*2^d | verification | proved (SAW) | proved (ver_row_ring) |
read from the source |
The first column of results means every function on the path, from
the vector and matrix loops in polyvec.c down to
montgomery_reduce, is proved equal to a Cryptol model in
the form it is called (including the calls where the output overlaps an
input), and the loops are proved to leave their inputs unchanged (the
signer reuses the challenge and A across calls). The second means
Isabelle proves the composition of those models computes the product.
The third is where the proofs stop: that sign.c makes those
calls in that order, on those buffers, with inputs in the ranges the
theorems assume, is read from the C. sign.c is not part of
the proof. docs/COMPOSITION.md
lists every hypothesis of the three theorems and the proof or
sign.c line that discharges it.
Verification needed three more pieces: the shift by 2^13, a
subtraction, and a pointwise call whose output overwrites one of its
inputs. The theorem ver_row_ring in Ver_Bridge.thy
says each row of verification’s computation is A_1z_1 + … +
A_4z_4 - c(2^13t1) mod X^256+1, which is FIPS 204
Algorithm 8’s NTT^-1(A_hat o NTT(z) - NTT(c) o NTT(t1*2^d)) read as
polynomials.
ntt, invntt_tomont,
poly_pointwise_montgomery, poly_add,
poly_sub, poly_shiftl,
poly_reduce,
polyvecl_pointwise_acc_montgomery, the
poly_ntt and poly_invntt_tomont wrappers, and
the loops over vector entries and matrix rows. Each proof has a mutant
(the claimed result with 1 added to one coefficient) that SAW rejects
with a counterexample. make saw.make lift-check.make convolution.make verify runs all of it. The pinned checkers are SAW
1.5.1 (with its bundled z3), cryptol-to-isabelle from the same release,
Isabelle2025-2 and the AFP snapshot of 2026-06-05. The results are
claimed for those versions.
sign.c composes the proved functions: the call
order, which buffer is passed where, and which function produces each
input. Each is read from a named line of the pinned source, listed in docs/COMPOSITION.md.
The output ranges of the unpack functions that produce t1, t0, s1, s2, z
and y are proved in SAW (poly_ranges.saw); the ranges of A
(rej_uniform), keygen’s secrets (rej_eta) and c
(poly_challenge) are read from the source, and sampling is
not checked against FIPS 204.-O0 -fwrapv. That no signed overflow happens on a normal
build is mechanized for the forward NTT and for the pointwise, add,
subtract, reduce and accumulate functions and the loops on the
multiplication paths (make poly-nsw, which also checks that
the two builds differ only in overflow and inbounds flags).
For the inverse NTT and the transform wrappers it is argued from the
proved bounds. The compiler is trusted.by eval method). A check in
the build fails if the headline theorems pick up any other oracle.poly_shiftl shifts a signed int, which C defines only
for non-negative values that do not overflow. That holds because t1 is
10-bit (proved for polyt1_unpack’s output; that
unpack_pk uses it is read from the source). SAW does not see
that kind of undefined behaviour.The full list, with file references, is in docs/ASSUMPTIONS.md
under A-ROW, A-POINTWISE and OF-4.
The AFP entry CRYSTALS-Kyber proves the convolution theorem for the NTT generically, over a quotient ring. The mathematics here is the same; the part that is new is connecting it to a C implementation, including the Montgomery factors and the bounds, and to the places the scheme calls it.
Each milestone was reviewed by re-running the tools and checking
every claim against the output. The first round found that an early
draft overstated where the result applied, that a “no
by eval” claim was true of the new files but not of the
theorem, and that three of four Isabelle mutation tests only showed the
proof script breaking when its statement changed. The second found
unverified loops between sign.c and the proved functions.
Those loops are now proved, and the rest is corrected in the text above.
The third, on verification, found that the loops reused by the signer
were not proved to leave their inputs unchanged; they now are. A later
round found that this page still described the composition as proved on
the C, and that “unchanged across iterations” was only proved for the
calls that receive the buffer, not for the unverified code between them;
both are corrected, and mutants now test the “unchanged” clauses.
git clone https://github.com/amarshat/pqc-assay && cd pqc-assay
./scripts/setup.sh # pinned toolchain into .tools/ (macOS arm64 tested)
make saw # C == Cryptol
make lift-check # Isabelle model == lift of the Cryptol SAW checked
make convolution # the Isabelle theorems in this post
make verify # everything
The first Isabelle build compiles its library dependencies and takes a while; later builds take seconds.