- A new machine-checked proof formally verifies masking soundness for the Adams Bridge ML-DSA/ML-KEM accelerator across 1.17 million cells and 30 modules, replacing 2^25 Boolean SMT evaluations with a five-line Lean 4 argument.
- The result lifts verification from a single toy modulus (q = 5) to universal coverage of every modulus q > 0, including production values q = 3,329 (ML-KEM) and q = 8,380,417 (ML-DSA).
- Enterprises deploying FIPS 203 and FIPS 204 accelerators can now demand formally verified masking with a trusted base reduced to the Lean 4 kernel, shrinking certification risk and supplier audit scope.
Why PQC Hardware Masking Verification Just Changed
A post-quantum cryptography hardware vendor hands your procurement team a side-channel resistance attestation. Dig into the footnotes and you often find the same caveat: the masking soundness proof was machine-checked at q = 5 — a modulus chosen because SMT solvers like Z3 and CVC5 can enumerate 2^25 Boolean wire functions in finite time. Your production silicon runs ML-KEM at q = 3,329 and ML-DSA at q = 8,380,417. The gap between what was verified and what ships is roughly six orders of magnitude.
That gap has been the open secret of masked PQC hardware assurance. A new paper, From Finite Enumeration to Universal Proof: Ring-Theoretic Foundations for PQC Hardware Masking Verification (arXiv:2604.18717v1), closes it for a central sub-theorem. The authors deliver the first machine-checked universal proof of the r-free sub-theorem of Theorem 3.9.1: for every modulus q > 0, every wire function, and every pair of secrets, value-independence implies identical marginal distributions. The proof is written in Lean 4 with Mathlib, runs sorry-free, and reduces the trusted computing base from the trio of {Z3, CVC5, Python} down to the Lean 4 kernel alone.
The practical stakes: the proof was exercised against QANARY’s verification of the Adams Bridge ML-DSA/ML-KEM accelerator — 1.17 million cells across 30 modules. Anyone building, buying, or certifying masked PQC silicon now has a reference point that does not cap out at toy moduli.
The Problem: Finite Enumeration Does Not Scale to Real Cryptographic Moduli
Masking is the standard countermeasure against power-analysis side-channel attacks on cryptographic hardware. Secrets get split into shares, arithmetic is performed share-wise, and — if the masking is sound — no intermediate wire leaks information about the underlying secret. Proving soundness means proving that the joint distribution of observable wires is independent of the secret across every branch, every gate, every reshare.
For PQC algorithms built on lattice arithmetic, that proof must hold over the ring Z/qZ. The industry-standard approach encodes wire functions as Boolean circuits and hands them to an SMT solver. The solver enumerates assignments. The solver returns SAT or UNSAT. Engineers trust the result.
The approach has two structural failures at production scale:
1. Modulus ceiling. Prior machine-checked results on Adams Bridge hit q = 5. Push past that and the Boolean encoding explodes. ML-KEM’s q = 3,329 and ML-DSA’s q = 8,380,417 are unreachable by enumeration — the search space grows with q and with the bit-width of the wire function.
2. Trusted base bloat. When your soundness claim depends on Z3, CVC5, and a Python harness gluing them together, your trusted computing base includes every bug in every one of those tools. For a cryptographic accelerator entering FIPS certification, that is an auditor’s nightmare and a procurement committee’s stall tactic.
The core soundness result for Adams Bridge — Theorem 3.9.1 — was previously machine-checked only at q = 5 via 2^25 Boolean wire functions. Production deployments run at q = 3,329 and q = 8,380,417. That delta is not a rounding error; it is the reason masking assurance has lagged PQC deployment.
Technical Deep-Dive: Ring Axioms as the Abstraction Layer
The paper’s insight is to stop treating Z/qZ as a finite set of values to enumerate and start treating it as a commutative ring whose axioms already capture everything the soundness argument needs. Once you work at the axiomatic level, q becomes a parameter rather than a bound on proof complexity.
The authors deliver nine theorems — labelled T1 through T6 plus refined variants T1’ and T3’ — covering reparametrization of wire functions, bijectivity of share transformations, overflow bounds for finite-width arithmetic, bias analysis for the masking RNG, and a universal non-tightness counterexample that applies for every q ≥ 2. The centerpiece is the r-free sub-theorem of Theorem 3.9.1, which upgrades value-independence to marginal-distribution identity universally across q.
Current standard vs. universal proof
| Dimension | SMT Enumeration (prior) | Lean 4 Universal Proof (new) |
|---|---|---|
| Modulus coverage | q = 5 only | Every q > 0 |
| Search space | 2^25 Boolean wire functions | Symbolic ring argument |
| Proof size | Exponential finite evaluations | Five lines |
| Trusted base | Z3 + CVC5 + Python | Lean 4 kernel |
| ML-KEM applicability (q = 3,329) | Out of reach | Covered |
| ML-DSA applicability (q = 8,380,417) | Out of reach | Covered |
| Re-use across algorithms | Re-run per circuit | Proof portability via ring axioms |
| Certification audit surface | Solver bugs, harness bugs | Kernel soundness |
The proof, in Lean 4 with Mathlib, requires five lines versus 2^25 finite evaluations. It is sorry-free, reducing the trusted base from {Z3, CVC5, Python} to the Lean 4 kernel.
“Sorry-free” is the Lean community’s term for a proof that contains no axioms-to-be-filled-in and no admitted lemmas. Every step is machine-checked back to the kernel. For a cryptographic claim destined for a common criteria evaluation or FIPS 140-3 non-invasive attack mitigation review, that property is the difference between an auditor signing off and an auditor asking for another six months of evidence.
What the proof does not yet cover
The paper is precise about scope. The universal result targets the r-free sub-theorem — not the complete Theorem 3.9.1. The full theorem includes reshare randomness behavior (the “r” component) that remains verified by other means. The abstract does not specify which of the 30 Adams Bridge modules fall under the universal proof versus which still rely on prior enumeration. It also omits empirical side-channel validation — no TVLA or t-test data accompanies the formal result — which means the proof addresses logical soundness of the masking scheme, not the physical leakage of a specific tape-out.
Industry Context: NIST Timelines Are Tightening
NIST IR 8547, the transition to post-quantum cryptographic standards, was published in its initial public draft in March 2025. FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA) are the mandated algorithms. Hardware accelerators for both are moving from reference designs into tapeouts at merchant silicon vendors and hyperscaler custom chips.
Side-channel resistance is not optional for those deployments. Any accelerator handling long-lived signing keys or key-encapsulation secrets in a shared datacenter must assume a motivated adversary with oscilloscope-grade access to power rails or EM emanations. Masking is the first line of defense. A masking scheme that was only proven sound at q = 5 while shipping at q = 8,380,417 is a defense with a footnote.
The economic math is straightforward. Re-spinning silicon because a masking flaw emerges post-deployment runs into eight figures. Delaying a product launch because auditors will not accept an SMT-based proof at production moduli runs into nine figures of revenue exposure for a hyperscaler. A universal proof that ports across q values — and across algorithms that share the ring-theoretic substrate — collapses both risks.
The methodology also generalizes. Commutative ring axioms of Z/qZ apply to lattice-based PQC broadly, not just ML-KEM and ML-DSA. Future NIST selections in the additional digital signature competition and any standardized KEM variants inherit the same abstraction layer.
The BeQuantum Perspective: Formal Proofs Belong in the Supply Chain
BeQuantum’s PQC Layer ships with a mandate that side-channel countermeasures carry machine-checkable assurance, not solver-dependent attestations. The shift from SMT enumeration to Lean 4 universal proofs is exactly the kind of trusted-base reduction that makes supply-chain verification tractable.
Here is how we apply findings like this in practice:
Artifact-level verification. When a hardware vendor delivers a masked PQC accelerator, the Digital Notary records the proof artifact itself — the Lean 4 source, its Mathlib dependency graph, and the kernel version that checked it — as an immutable attestation tied to the silicon’s cryptographic identity. Downstream integrators verify the attestation against the kernel, not against a promise that Z3 was bug-free on the day the original proof ran.
Proof portability in IceCase hardware. Ring-theoretic abstractions port across algorithms. An assurance argument proven for ML-KEM at q = 3,329 does not need to be redone from scratch when a future standard lands at a different modulus — the five-line proof parametrizes cleanly. For hardware security modules that must support algorithm agility across NIST rounds, that portability is the difference between a firmware update and a new certification cycle.
Audit surface reduction. The trusted base collapsing from {Z3, CVC5, Python} to the Lean 4 kernel shrinks what regulators and customers must review. Our engagement model with CISOs in regulated sectors treats every element of the trusted base as a line item in the threat model. Fewer lines, tighter model.
This is not a claim that formal methods replace empirical side-channel testing. Tape-outs still need TVLA. The claim is narrower and more useful: the logical soundness layer, which used to be the weakest link in masking assurance at production moduli, now has a compact universal proof.
What You Should Do Next
Within 60 days, audit your PQC hardware attestations for modulus coverage. For every masked ML-KEM or ML-DSA accelerator on your roadmap, ask the vendor: at what q was the masking soundness proof machine-checked? If the answer is q = 5 or “we use SMT enumeration,” flag the delta between verification modulus and production modulus as an open risk item.
Within 90 days, map your trusted computing base for cryptographic assurance. Document which SMT solvers, scripting harnesses, and ancillary tools sit inside the trust boundary for each masking proof you rely on. This list is your auditor’s first question. Reducing it is a direct dependency on adopting proofs like the Lean 4 universal result over prior finite-enumeration attestations.
Before your next hardware procurement cycle, require proof-artifact delivery. Shift contract language from “vendor attests masking is sound” to “vendor delivers machine-checkable proof artifact with named kernel version.” This is already standard for safety-critical avionics and automotive SIL certifications. PQC accelerators protecting decade-long cryptographic assets deserve the same bar.
FAQ
Q: Does the Lean 4 proof eliminate the need for SMT-based verification of PQC hardware entirely?
A: No. The universal proof covers the r-free sub-theorem of Theorem 3.9.1 — the value-independence-to-marginal-identity argument across all q > 0. Other components of a complete masking soundness argument, including reshare randomness behavior, still use complementary techniques. The result is a major reduction in the finite-enumeration workload, not its total elimination.
Q: How does this affect organizations already deploying ML-KEM and ML-DSA accelerators in production?
A: It changes what you can ask your supplier for. Accelerators whose masking proofs were previously capped at q = 5 now have an available path to universal verification at the actual deployment moduli (q = 3,329 and q = 8,380,417). Procurement and security-architecture teams should treat the availability of Lean 4 proof artifacts as a supplier differentiator in the current refresh cycle.
Q: Why does the trusted base matter so much for cryptographic assurance?
A: Every tool inside the trusted base is a potential soundness bug. A proof checked by Z3, CVC5, and Python is only as trustworthy as those three systems combined. A proof checked by the Lean 4 kernel is trustworthy to the extent that the Lean kernel is — and the kernel is deliberately small, heavily reviewed, and independently re-implementable. For regulated industries and long-lived cryptographic secrets, that reduction is the core value proposition.
Last updated: 2026-04-23
Source: From Finite Enumeration to Universal Proof: Ring-Theoretic Foundations for PQC Hardware Masking Verification (arXiv:2604.18717v1)
