Formal Verification and High-Assurance Post-Quantum Cryptographic Software

Formal verification High-Assurance Cryptographic Software (HACS) refers to a family of methods and toolchains that produce machine-checkable mathematical proofs about the behaviour of cryptographic implementations, covering functional correctness, memory safety and the absence of secret-dependent execution paths that would leak key material through timing side-channels. For sovereign European organisations that depend on post-quantum cryptography to protect data with multi-decade confidentiality requirements, these methods close a critical gap that neither NIST standardisation nor FIPS 140-3 certification alone can close.

Why Certification Alone Is Not Enough

NIST CMVP certification under FIPS 140-3 is a validated testing regime, not a proof of correctness. It confirms that a cryptographic module met defined criteria during a point-in-time evaluation. It says nothing about code paths introduced after that evaluation, nor about whether the implementation faithfully realises every edge case in the standard specification.

NIST published FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) in August 2024, completing the first wave of post-quantum standardisation. These documents define mathematically precise algorithm specifications. The question that formal verification addresses is a different one: does the code running on a server or gateway actually match that specification for every possible input, under every possible compiler optimisation, without leaking secret key material through timing differences?

As Karthikeyan Bhargavan, senior research scientist at Inria and a lead contributor to the HACL* and EverCrypt projects, has put it: “A certificate tells you a module was tested at a point in time. A formal proof tells you the implementation is correct for all possible inputs, not just the ones a test suite happened to cover.”

Formal Verification Methods Applied to PQC

Three main techniques are used in HACS work on PQC implementations: model checking, theorem proving and verified compilation. Each addresses a distinct failure mode.

Theorem proving and functional correctness

Theorem proving, used in the F* proof assistant that underlies HACL* and EverCrypt, allows developers to write a specification of what a function must return for every input and then verify that the implementation code satisfies that specification. For ML-KEM, this means proving that the key encapsulation and decapsulation functions are inverses, that matrix arithmetic over the polynomial ring is performed exactly as FIPS 203 specifies, and that no branch depends on secret data. The resulting proof is a machine-checkable artefact stored alongside the source code.

Verified compilation

A formally verified compiler, such as CompCert, guarantees that the compiled binary preserves the semantics of the source program. Without verified compilation, a proof about the source code does not automatically extend to the binary running on hardware. libcrux, maintained by Cryspen, addresses this partially by targeting a formally specified subset of Rust whose safety properties are preserved by the Rust borrow checker and by verified extraction toolchains. This makes libcrux particularly relevant for sovereign deployments that need to integrate PQC into Rust-based infrastructure without introducing a C dependency.

Constant-time verification

Secret-dependent branches and memory access patterns allow timing side-channel attacks that can recover key material even from correctly specified algorithms. Tools such as ct-verif and the secret-tracking type system in F* verify that no observable execution path depends on secret inputs, a property test suites cannot systematically confirm.

The Current Landscape of Formally Verified PQC Libraries

The production-readiness of formally verified PQC implementations varies significantly. The table below summarises the three most relevant open-source projects for sovereign European deployment.

libcrux is the furthest advanced for production ML-KEM deployment with formal assurance. Its ML-KEM implementation has been integrated into the rustls TLS library, which means organisations replacing legacy TLS stacks in sovereign infrastructure can consume a formally specified implementation via a standard Rust dependency. HACL* / EverCrypt covers the broadest classical algorithm suite and is deployed in Firefox, the Linux kernel and Signal, providing strong evidence of production hardening, while PQC coverage continues to develop.

ECCC Horizon HORIZON-CL3-2026-02-CS-ECCC and What It Signals for Procurement

The European Cybersecurity Competence Centre’s Horizon call HORIZON-CL3-2026-02-CS-ECCC explicitly targets the development of formal verification tools and their integration into HACS software workflows. For regulated organisations, the importance of this call is less about the funded projects themselves and more about the policy signal it carries.

ENISA has stated clearly in its post-quantum cryptography guidance that “cryptographic agility and formal verification are not luxuries; they are prerequisites for infrastructure that must remain trustworthy over decades.” The ECCC call operationalises this position by making EU funding conditional on applicants demonstrating that formal verification methods are embedded in realistic software development and maintenance pipelines, not treated as academic exercises.

For a compliance officer or procurement team, this means that evaluation criteria for PQC library selection should already reflect these expectations. A vendor that can only point to FIPS 140-3 certification for a component destined for critical infrastructure deserves closer scrutiny than one whose implementation is backed by proof artefacts. When the next supervisory audit asks for evidence of state-of-the-art cryptographic controls under NIS-2 Article 21 or DORA Article 9, a machine-readable proof is a stronger exhibit than a test report.

Integrating HACS into DevSecOps for Audit-Ready Compliance

Integrating formally verified libraries into a sovereign DevSecOps pipeline is primarily an architectural decision rather than a cryptographic one. The proof artefacts generated by tools such as F* or Hacspec are static outputs that do not change the build pipeline itself. What changes is the software bill of materials (SBOM) and the audit trail.

Concretely, a CISO or IT architect should require the following from a HACS-capable PQC library:

• Published proof artefacts stored in the same repository as the source code, version-locked and reproducible.
• A clear mapping from the proof claims to the relevant FIPS specification sections, so an auditor can verify that the proof covers the normative algorithm, not a simplified model.
• Continuous integration checks that re-verify proofs on every commit, preventing the drift that occurs when code is modified after a certificate is granted.
• An explicit constant-time verification step covering all code paths that process secret key material.

Under CRA Article 13, manufacturers of products with digital elements sold in the EU must apply security by design and maintain documentation demonstrating this. For a sovereign workspace provider or a regulated financial institution deploying a PQC-enabled gateway, the SBOM enriched with proof artefact references constitutes that documentation in a form that both national competent authorities and commercial auditors can evaluate objectively.

How a CISO or DPO Should Evaluate Competing Library Claims

The asymmetric risk profile of sovereign PQC infrastructure demands a structured evaluation approach. Vendor assertions that a library is “quantum-safe” or “NIST-compliant” have no informational content without specifics. A useful evaluation framework moves through four layers.

The first layer is specification coverage: does the implementation cover all normative requirements of FIPS 203, FIPS 204 or FIPS 205, including rejection sampling, hash domain separation and decapsulation implicit rejection? A formally verified implementation will have a proof claim for each of these properties; a test-based implementation will have test vectors that cover sampled cases.

The second layer is side-channel coverage: does the constant-time proof extend to all branches in the implementation as compiled, not just the reference source? This distinction matters because some compilers introduce conditional branches when optimising polynomial arithmetic.

The third layer is maintenance trajectory: who maintains the library, how quickly were past vulnerabilities patched, and are the proof artefacts re-checked on every release? A library with a formal proof that was last updated two major versions ago provides weaker assurance than one with continuous verification in its CI pipeline.

The fourth layer is jurisdictional independence: for sovereign European infrastructure, the maintenance and distribution of the cryptographic library should not be subject to US export control regulations or compelled disclosure under the CLOUD Act or FISA 702. Both libcrux (Cryspen, Switzerland) and the HACL* project (Inria, France) have European operational roots, which matters when selecting components for infrastructure that must remain outside foreign jurisdictional reach.

FAQ

Is FIPS 140-3 certification sufficient assurance for a PQC library used in sovereign infrastructure?

FIPS 140-3 certification confirms that a module met defined criteria at a specific evaluation point and that physical and logical security controls were present. It does not guarantee the implementation is free of logic errors for all possible inputs, nor does it cover code paths added after certification. For long-lived sovereign infrastructure where the cost of a vulnerability is asymmetrically high, formal proofs about functional correctness and memory safety complement certification and provide stronger continuous assurance.

What are HACL*, EverCrypt and libcrux, and how do they differ?

HACL* is a formally verified cryptographic library developed at Inria and Microsoft Research, written in the F* proof assistant language and compiled to C and WebAssembly. EverCrypt is a high-performance cryptographic provider built on HACL* that adds verified agility and multiplexing. libcrux, maintained by Cryspen, targets post-quantum algorithms such as ML-KEM and is written in a formally specified subset of Rust, enabling integration into modern systems without a C dependency. All three projects produce machine-checkable proofs of functional correctness, memory safety and absence of secret-dependent branches.

What does the ECCC Horizon HORIZON-CL3-2026-02-CS-ECCC call require from applicants?

The call invites proposals that develop or mature formal verification tools and integrate High-Assurance Cryptographic Software approaches into realistic software development workflows. For regulated organisations the key implication is a policy signal: procurement and development of PQC components in critical sectors is expected to include formal assurance evidence, not merely vendor assertions or test-based certification.

How do NIS-2, DORA and the CRA create concrete audit requirements for cryptographic components?

NIS-2 Article 21 requires essential and important entities to apply state-of-the-art cryptographic measures and to document their risk management. DORA Article 9 requires financial entities to maintain documentation that competent authorities can inspect. CRA Article 13 obliges manufacturers of products with digital elements to apply security by design, which includes embedded cryptographic components. Formally verified implementations, with proof artefacts stored alongside the software bill of materials, provide auditors with objective evidence beyond self-declaration.

What is the “harvest now, decrypt later” threat and why does it make formal verification urgent today?

Adversaries are believed to be collecting encrypted traffic now, intending to decrypt it once a sufficiently powerful quantum computer becomes available. Sensitive data with a long confidentiality horizon, such as health records, legal privilege communications or classified government data, is at risk today. Migrating to PQC protects this data prospectively, but only if the PQC implementation is itself correct. A logic error in an ML-KEM implementation could silently weaken or nullify the protection, making formal verification of those implementations an operational priority, not an academic one.