Deploy EasyCrypt to Europe — Gilles Barthe 🇫🇷 (IMDEA Madrid 🇪🇸 / Max Planck 🇩🇪), the Proof Assistant for Machine-Checked Cryptographic Security Proofs, on EU Infrastructure in 2026

When the US National Institute of Standards and Technology selected CRYSTALS-Kyber as the primary post-quantum key encapsulation mechanism — standardised as ML-KEM in FIPS 203 in August 2024 — it was not just a choice of algorithm. It was a validation of an entire approach to cryptographic assurance: machine-checked formal proofs of security properties, carried out in a proof assistant specifically designed for cryptographic reasoning.

The proof assistant was EasyCrypt. The team was European.

Gilles Barthe — born in France, former researcher at INRIA Sophia Antipolis 🇫🇷, then founding researcher at IMDEA Software Institute 🇪🇸 in Madrid, now director at Max Planck Institute for Security and Privacy 🇩🇪 in Bochum — led the development of EasyCrypt with Benjamin Grégoire 🇫🇷 (INRIA Sophia Antipolis 🇫🇷), Manuel Barbosa 🇵🇹 (Universidade do Porto 🇵🇹), Pierre-Yves Strub 🇫🇷 (IMDEA Madrid 🇪🇸 → École Polytechnique 🇫🇷), and José Bacelar Almeida 🇵🇹 (Universidade do Minho 🇵🇹). The formal correctness of CRYSTALS-Kyber — the cryptographic primitive now protecting post-quantum secure communications across the European Union — was machine-checked using their tool. As EU AI Act Article 9 mandates systematic risk documentation for high-risk AI systems, and BSI and ANSSI mandate PQC migration timelines for critical infrastructure, EasyCrypt provides the most rigorous form of compliance evidence available: a machine-verified proof that your cryptographic implementation is correct.

The Cryptographic Security Proof Problem

Traditional cryptographic security proofs are pen-and-paper mathematical arguments. A security reduction proves that breaking the cryptographic scheme is at least as hard as solving an underlying computational problem (discrete logarithm, lattice shortest-vector, etc.). These proofs are the foundation of modern cryptographic confidence — but they are written in mathematical notation, reviewed by human experts, and subject to human error.

History is replete with security proofs later found to be subtly incorrect. The Lucky Thirteen attack on TLS 1.2 exploited a timing side-channel that invalidated informal "padding oracle" arguments. The PKCS#1 v1.5 RSA encryption scheme survived decades of "proofs" before Bleichenbacher's 1998 attack. In 2022, Fiat-Shamir with aborts lattice signature schemes had informal security arguments revised after formal analysis.

EasyCrypt addresses this by formalising the proof in a machine-checked logical framework, where every step of every security reduction is verified by a proof checker — not by human reviewers who may be tired, distracted, or simply wrong.

What EasyCrypt Is — Probabilistic Relational Hoare Logic

EasyCrypt is a proof assistant based on probabilistic relational Hoare Logic (pRHL), a logic specifically designed for reasoning about pairs of probabilistic programs — the natural structure of game-based cryptographic security proofs.

Game-Based Security Proofs

Modern cryptographic security is formalized as a security game between a challenger and a probabilistic polynomial-time adversary. Security means: no efficient adversary can win the game with probability significantly better than random chance. A security reduction proves that any adversary breaking the scheme can be used to solve the underlying hard problem.

These proofs naturally take the form of a sequence of game transformations:

G₀   (original security game)
≈ε₁  G₁   (game hop: replace PRF with random function — ε₁ = PRF advantage)
≈ε₂  G₂   (game hop: abort on bad event — ε₂ = collision probability)
≈ε₃  G₃   (game hop: switch to ideal — ε₃ = 0 by information-theoretic argument)

The final game G₃ is trivially unwinnable. The total advantage is bounded by ε₁ + ε₂ + ε₃. EasyCrypt makes each ≈ εᵢ step machine-checkable.

pRHL Judgments

The core of EasyCrypt is the pRHL judgment:

⊢ c₁ ~ c₂ : Φ / Ψ

This asserts: for all memories satisfying pre-condition Φ, the output distributions of programs c₁ and c₂ are related by post-condition Ψ. Special cases include:

• Indistinguishability: Pr[c₁ : E] ≤ Pr[c₂ : E] + ε — adversary cannot distinguish game G₁ from G₂
• Equivalence: output distributions are identical (ε = 0)
• Simulation: any adversary against c₁ can be transformed into an adversary against c₂

EasyCrypt Syntax

An EasyCrypt proof module defines types, distributions, and probabilistic procedures:

require import AllCore Real Distr DBool.

(* Key generation: sample random key from uniform distribution *)
module KeyGen = {
  proc kg() : key = {
    var k : key;
    k <$ dkey;      (* <$ : sample from distribution *)
    return k;
  }
}.

(* Security game: IND-CPA (indistinguishability under chosen-plaintext attack) *)
module Game(A : Adversary) = {
  proc main() : bool = {
    var k, m0, m1, c, b, b';
    k <@ KeyGen.kg();
    (m0, m1) <@ A.choose(pk(k));
    b <$ {0,1};           (* challenger samples random bit *)
    c <- enc(pk(k), if b then m1 else m0);
    b' <@ A.guess(c);
    return b = b';
  }
}.

(* Proof lemma: advantage of any adversary is bounded *)
lemma ind_cpa_security (A <: Adversary) &m :
  `| Pr[Game(A).main() @ &m : res] - 1%r/2%r | <= advantage_PRF A.

The <@ operator calls a probabilistic procedure; <$ samples from a distribution; %r converts between integer and real arithmetic. The lemma states the security bound, and the proof body uses tactics like proc, call, rnd, wp, skip, and auto to verify each step.

Verified Cryptography: What EasyCrypt Has Proved

EasyCrypt has been used to produce machine-checked security proofs for some of the most widely deployed cryptographic implementations in the world:

CRYSTALS-Kyber / ML-KEM (NIST FIPS 203)

Barbosa, Bhargavan, Blot, Grégoire, Kiefer, Kobeissi, Liao, Rezk, Strub (IEEE SP 2023): formal verification of CRYSTALS-Kyber, the NIST post-quantum key encapsulation mechanism standardised as ML-KEM FIPS 203. The proof covers the full IND-CCA₂ security reduction, including the Fujisaki-Okamoto transform from IND-CPA to IND-CCA₂. This is the cryptographic primitive now mandated by BSI 🇩🇪 and ANSSI 🇫🇷 for PQC transition in EU critical infrastructure.

CRYSTALS-Dilithium / ML-DSA (NIST FIPS 204)

EasyCrypt verification of the module lattice digital signature scheme, standardised as ML-DSA FIPS 204 — the EU's preferred post-quantum signature algorithm for eIDAS 2.0 EUDI Wallet credentials.

HACL* — High-Assurance Cryptographic Library

Zinzindohoué, Bhargavan, Protzenko, Beurdouche (CCS 2017): HACL* is a formally verified cryptographic library written in F* (another EU-research proof assistant, Microsoft Research Cambridge 🇬🇧 / INRIA Paris 🇫🇷) and deployed in:

• Firefox (Mozilla) — SHA-256, ChaCha20-Poly1305, Ed25519, X25519
• Linux kernel — Poly1305 (merged 2019)
• Signal Protocol (Open Whisper Systems)
• WireGuard VPN

HACL* base cryptographic security properties are established in EasyCrypt. EasyCrypt proves the security game; F* verifies the implementation against the spec; Jasmin (see below) extracts verified assembly.

AWS s2n-tls

Amazon Web Services uses EasyCrypt to verify cryptographic components of s2n-tls, the TLS implementation used in AWS services globally. Security properties verified include: record layer confidentiality, handshake authentication, forward secrecy.

The Jasmin Pipeline

Jasmin (Almeida, Barbosa, Barthe, Blot, Grégoire, Laporte, Oliveira, Pacheco, Strub, Unruh — CCS 2017) is a programming language for writing high-speed, formally verified cryptographic code at the assembly level. The pipeline:

EasyCrypt proof (security reduction)
        ↓
Jasmin source (assembly-like, EU-designed language)
        ↓
Verified compilation to x86-64 assembly
        ↓
Machine-checked security: from proof to binary

Jasmin code achieves performance comparable to hand-optimised assembly while carrying machine-checked correctness proofs. EU research provenance: Universidade do Porto 🇵🇹 + INRIA Sophia Antipolis 🇫🇷 + IMDEA Madrid 🇪🇸.

The EU Infrastructure Angle

EasyCrypt is not just a research tool — it is the backbone of Europe's post-quantum cryptographic transition infrastructure. The same tool that proved CRYSTALS-Kyber correct is available to EU enterprises building NIS2-compliant, eIDAS 2.0-ready, AI Act-compliant systems.

Running EasyCrypt on EU-hosted infrastructure ensures your verification artefacts — the .ec proof files, the verified specification files, the proof obligations — remain under EU jurisdiction. For systems subject to GDPR, NIS2, or EU AI Act, this matters: verification artefacts may describe system architecture and security assumptions that themselves constitute sensitive business logic.

sota.io provides EU-native deployment: hosted in Germany 🇩🇪, GDPR-compliant by default, no CLOUD Act exposure. Unlike Railway (US), Render (US), or Vercel (US), sota.io is an EU corporate entity — US authorities cannot compel access to your proof files or cryptographic specifications under the CLOUD Act.

Deploying EasyCrypt on sota.io — Step by Step

Step 1: Create the EasyCrypt Docker Image

EasyCrypt is distributed via opam (OCaml package manager). A minimal Dockerfile for a CI verification service:

FROM ocaml/opam:ubuntu-22.04-ocaml-4.14

USER opam
RUN opam update && opam install -y easycrypt

WORKDIR /proofs
COPY . .

# Verify all .ec files in the /proofs directory
CMD ["bash", "-c", "opam exec -- easycrypt check -I theories/ *.ec"]

Or use the official EasyCrypt Docker image directly:

FROM easycrypt/easycrypt:latest

WORKDIR /proofs
COPY . .
CMD ["easycrypt", "check", "Main.ec"]

Step 2: Write a Minimal Security Proof

(* IND-CPA security for a symmetric cipher *)
require import AllCore Real Distr DBool.

type key, plaintext, ciphertext.

op enc : key -> plaintext -> ciphertext.
op dec : key -> ciphertext -> plaintext.

axiom correctness k m : dec k (enc k m) = m.

module type Adversary = {
  proc choose(* pk *) () : plaintext * plaintext
  proc guess(c : ciphertext) : bool
}.

module Game(A : Adversary) = {
  proc main() : bool = {
    var k, m0, m1, c, b, b';
    k <$ dkey;
    (m0, m1) <@ A.choose();
    b <$ {0,1};
    c <- enc k (if b then m1 else m0);
    b' <@ A.guess(c);
    return b = b';
  }
}.

Step 3: Deploy to sota.io

# One-command deployment
sota deploy --name easycrypt-verifier --dockerfile Dockerfile

# Natural language interface
# "Deploy this Dockerfile as a proof-checking service"

Step 4: CI/CD Integration

# .github/workflows/verify-crypto.yml
name: Verify Cryptographic Proofs
on: [push, pull_request]
jobs:
  easycrypt:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4
      - name: Run EasyCrypt on EU infrastructure
        run: |
          curl -X POST https://your-ec-verifier.sota.io/check \
            -F "proof=@SecurityProof.ec" \
            -H "Authorization: Bearer ${{ secrets.SOTA_TOKEN }}"

The service runs EasyCrypt in CI, returns VERIFIED or the failing proof obligation with line numbers, and logs every proof check to EU-hosted persistent storage.

EasyCrypt in the EU Regulatory Landscape

BSI (Bundesamt für Sicherheit in der Informationstechnik) 🇩🇪

BSI's Technical Guideline TR-02102 mandates post-quantum migration for German federal agencies and regulated industries. ML-KEM (CRYSTALS-Kyber) and ML-DSA (CRYSTALS-Dilithium) — both EasyCrypt-verified — are BSI's primary PQC recommendations. EasyCrypt proofs constitute the highest-assurance evidence for BSI compliance.

ANSSI (Agence Nationale de la Sécurité des Systèmes d'Information) 🇫🇷

ANSSI's hybrid post-quantum recommendations for critical French infrastructure specifically reference the INRIA/IMDEA research ecosystem (Barthe's group). EasyCrypt proof artefacts are accepted as formal security evidence in ANSSI evaluation processes.

NIS2 Art. 21 — Cryptographic Measures

NIS2 Directive (EU) 2022/2555 Art. 21(2)(h): "the use of cryptography and encryption" as a mandatory risk management measure for operators of essential services. EasyCrypt provides machine-checked evidence that cryptographic implementations meet the security properties claimed — directly satisfying the auditability requirements of NIS2 implementation assessment.

eIDAS 2.0 — EUDI Wallet Cryptography

Regulation (EU) 2024/1183: the European Digital Identity Wallet uses CRYSTALS-Dilithium (ML-DSA) for credential signatures. EasyCrypt's formal verification of ML-DSA is directly relevant to EUDI Wallet providers seeking LoA High certification under eIDAS 2.0.

EU AI Act Art. 9 — Risk Management for High-Risk AI

For AI systems in Annex III categories (biometric identification, critical infrastructure, employment tools), Art. 9 requires documented risk management including "systematic testing and verification measures." EasyCrypt proofs of cryptographic components (authentication, data integrity, confidentiality) constitute machine-checkable risk management evidence — stronger than any pen-and-paper security analysis.

CRA 2027 — Cyber Resilience Act

Products with digital elements placed on the EU market after 2027 must demonstrate "state of the art" security. Machine-checked cryptographic proofs represent the highest currently achievable assurance level — a defensible claim of CRA compliance for cryptographic components.

EU Research Provenance

EasyCrypt is 100% EU research output:

• IMDEA Software Institute 🇪🇸 (Madrid) — Gilles Barthe, Pierre-Yves Strub — Spanish national research institute, funded by Comunidad de Madrid and Spanish government
• INRIA Sophia Antipolis 🇫🇷 — Benjamin Grégoire — French national research institute (Équipe Marelle / Éclat)
• Max Planck Institute for Security and Privacy 🇩🇪 (Bochum) — Gilles Barthe — German Max Planck Society
• Universidade do Porto 🇵🇹 — Manuel Barbosa — Portuguese national university
• Universidade do Minho 🇵🇹 — José Bacelar Almeida — Portuguese national university
• ANR (Agence Nationale de Recherche) 🇫🇷 — primary funding source for early EasyCrypt development
• ERC (European Research Council) Advanced Grant — Barthe's research program funded by EU Framework Programme

Jasmin (the verified assembly pipeline) adds:

• NOVA LINCS 🇵🇹 (Lisbon) — Portuguese research center
• CRIStAL 🇫🇷 (Lille) — Centre de Recherche en Informatique, Signal et Automatique de Lille

Zero US institutional involvement in the core tool development. EU sovereignty from proof assistant to verified assembly.

Getting Started

1. Sign up for sota.io free tier — no credit card required
2. Pull the EasyCrypt Docker image: docker pull easycrypt/easycrypt:latest
3. Write your first security proof (easycrypt check HelloCrypto.ec)
4. Deploy your proof-checking CI service to EU infrastructure in under 10 minutes

For teams already using EasyCrypt locally, the cloud deployment adds persistent proof storage, CI integration, team collaboration on proof development, and GDPR-compliant artefact archiving for compliance audit trails.

For teams beginning PQC migration, sota.io's formal verification series covers the EU cryptographic toolchain: EasyCrypt for security proofs, ProVerif for protocol verification, Tamarin for 5G/TLS, and Verificatum for e-voting — all deployable on EU-sovereign infrastructure.

EasyCrypt is developed by Gilles Barthe, Benjamin Grégoire, Manuel Barbosa, Pierre-Yves Strub, José Bacelar Almeida, and contributors. MIT License. Source: github.com/EasyCrypt/easycrypt. Documentation: easycrypt.info.