Repository navigation
Description
DeepMind has released a Lean verification of Signal's security down to machine code (blog post, paper, code at 808b4b7). Its computational part is built on VCVio, pinned at 967fdf2e, and uses OracleComp, simulateQ, 𝒟[·], IsQueryBoundP and SampleableType throughout.
This issue tracks moving the generic parts of that work into VCVio, and into PolyFun where a law is about handlers or cost in general. The Signal, PQXDH and libsignal games and proofs stay in DeepMind's repository.
Source paths below are relative to DeepMind's repository at 808b4b7.
Scope
- Quang Dao, Devon Tuma and Bas Spitters coordinate this work. An item lands in VCVio now only if its design decisions and dependencies sit with the three of us. Items that need agreement from another project, or that would wait on another author's open PR, are listed under "Not now" and block nothing else.
- DeepMind's costed reduction DSL is one instance of the PolyFun cost framework (Interaction cost: discrete bounds on interface use, consolidated across PolyFun, VCVio, ArkLib and CatCrypt PolyFun#387), not VCVio's cost model. Its choices (natural-number step costs, one price per query, a fixed
2^24size cap, its operation table) become parameters of the general statements, not defaults. - Security theorems name their reduction (rule 11 in
AGENTS.md), and no new notion is calledPPT(Tracking: connecting VCVio to cslib-frontier (strict PPT, VCVioFrontier, adequacy) #906). - A new security definition lands only together with a construction and a security proof for it. Otherwise the definition is dropped, however generic it is.
- Probability belongs to PolyFun. feat(ipfunctor): kept value contexts, and continuous interpretations of binding signatures PolyFun#436 to feat(probability): uniform draws, and output measures of certified meanings PolyFun#446 (merged 11-12 to 11-15) moved measure semantics, couplings, relational program logic, expectations and uniform draws there, VCVio imports them since refactor(EvalDist): import the generic measure semantics from PolyFun, with names unchanged #1085, and VCVio keeps the security layer. A lemma about distributions alone goes to PolyFun; a lemma that mentions advantages, oracle specs,
SampleableTypeor random oracles stays in VCVio.
Licensing and attribution
DeepMind's files carry Apache-2.0 headers ("Copyright 2026 Google LLC"), and the repository has no NOTICE file. A VCVio file that contains ported DeepMind text follows CONTRIBUTING.md ("Attribution And File Headers", point 4): it keeps Copyright (c) 2026 Google LLC, lists the porting authors in Authors:, and names the source file at 808b4b7 and the changes in its module docstring. Where we re-prove a statement against current VCVio API instead of copying the proof, the docstring credits DeepMind's file as the source of the statement.
Nothing comes from third_party/libsignal/ or the LibsignalTestVectors library, which are AGPL-3.0. No Google-authored code goes to PolyFun, QuantumFoundations or QuantumCrypto.
Generic lemmas
These need no design decision. Each VCVio port targets current main, which already includes #1023 (reducible simulateQ). Sources are under Computational/Proofs/. Three items are partly or wholly about distributions alone and go to PolyFun, on top of Verified-zkEVM/PolyFun#446 (merged): the uniform split equivalences (which may already follow from IsUniform.pair and IsUniform.map_of_bijective), the modular-reduction bias stated for uniformOn, and possibly the potential-function bound, as a corollary of wpFold_liftM_le. VCVio then gets the $ᵗ and simulateQ corollaries.
- Move
evalDistEq_map_run_simulateQ_eq_of_query_evalDistEq_map_eqfromCryptoFoundations/GPVHashAndSign/TrapProjection.leantoOracleComp/SimSemantics/StateT/StateProjection.lean. This is housekeeping and copies no DeepMind code. Merged refactor(OracleComp): move a state-projection distribution lemma next to its sibling #1199. - Support and query bounds:
AllSupportand its closure lemmas, a form ofIsQueryBoundP.simulateQ_run_StateT_of_stepthat allowskqueries per step, andisQueryBoundP_min(fromGameHop/StateSim.lean). - Distribution lemmas: uniform split equivalences for
VectorandBitVec,wp_uniformSample_equiv,evalDist_uniformBool_ite_true, a generalisation ofboolDist_le_of_apply_le, andboolBias_le_add_two_mul_boolDist(fromGameHop/Rnd.leanandGameHop/Advantage.lean). - Hybrids and bad events: the partition hybrid, the telescoping bound as a corollary of
Measure.boolDist_le_sum_range, a potential-function bound forsimulateQ, the guessing lemma, and a monotone-predicate form of the bad-event bound inRelational/SimulateQ/Resource.lean(fromGameHop/GlobalHybrid.leanandGameHop/Fel.lean). - State projections that leave out one oracle, as generalisations of the lemmas in
StateProjection.lean, plus three generic lemmas fromGameHop/CompDedup.lean. - Eager versus lazy sampling through a lawful lens, stated with PolyFun's
Lens.Stateand feat(OracleComp): mapLens, transporting oracle computations along lenses #1016'smapLens(merged), and once-only lazy sampling (fromGameHop/Swap.lean). DeepMind's own cache types are replaced byListCache. - Replay forking under a weaker hypothesis:
[AnswerMeasure spec]plus uniformity at the forked index, instead of[UniformAnswerMeasure spec], inle_prEvent_isSome_contextForkand the collision lemmas, and an unfolding lemmacontextFork_eq_bind_withPath. DeepMind spent about 490 lines ofSignalPqxdh/XeddsaRom/ForkingReduction.leanworking around the stronger hypothesis. The change is backward compatible becauseUniformAnswerMeasureextendsAnswerMeasure. Merged refactor(ReplayFork): weaken the replay-forking bounds to uniformity at the forked index #1091, which credits DeepMind's808b4b7(ReplayFork.lean). - Modular-reduction bias: the statistical distance between
(· % n) <$> $ᵗ Fin (2^k)and$ᵗ ZMod n(fromForkingReduction.lean). - Optional: random-oracle lemmas for an arbitrary draw under
withCaching, and a test game that keeps a lazy random-oracle table in its own state, proved equal to the layered form byListCache.adaptive_projection.
BAIF's secure-messaging stages related lemmas for VCVio in its ToVCVio library: lazy, eager and one-use sampling, bad flags and identical-until-bad simulation, PRP/PRF switching, and TV and bool-distance bounds. Compare each with DeepMind's version before porting either.
DeepMind also keeps about 450 local helper statements, mostly duplicates of VCVio API, and the largest group (279) is StateT plumbing. Those do not move. Of the 51 game-hop declarations that have a VCVio counterpart, 46 had it already at DeepMind's pin. A short guide to the simulation and StateT lemmas would likely help other users too.
Coupling up to a bad event
DeepMind proved its adapter couplings (LibsignalCli/CliPqAdapterCoupling.lean and its siblings) by manual induction. Across the repository, the proofs use inductionOn 1,036 times and RelTriple never. VCVio main has parts of the rule they needed (relTriple_simulateQ_run, DominatedUntilBad, AgreeUntilBad). It lacks a rule for two handlers with different state types, where the relation must hold only while the bad event has not happened and the error term is Pr[bad].
Verified-zkEVM/PolyFun#444 moves couplings and the relational program logic (RelWP, eRelWP, and the coupling algebra) into PolyFun, and lists a generic relational handler lift as not included. The rule above is such a lift, with the bad event kept in the postcondition. Its generic part therefore goes to PolyFun on top of Verified-zkEVM/PolyFun#444, and VCVio derives the simulateQ and RelTriple forms, as #1022 did for unary handler triples.
- PolyFun: a relational handler lift for two stateful handlers that needs the per-query judgment only from related, non-bad states, with the event bounds and the statistical-distance bound derived from it.
- PolyFun: a budget-indexed variant, a coupling constructor from a joint distribution whose marginals match the two sides, and restriction of the postcondition to the support of the left run.
- VCVio: the
simulateQandRelTriplecorollaries, and a small test example with the same shape as DeepMind's adapter coupling.
A quantitative form, with Pr[bad] as a state-dependent error term, would need a relational algebra at ℝ≥0∞, which Verified-zkEVM/PolyFun#444 also lists as not included. #1026 (merged) extends VCVio's until-bad bounds through a common random tail, so the VCVio corollaries reuse its lemmas.
Symmetric constructions
A new definition lands only with a construction and its security proof. DeepMind's repository contains three generic items that pass this test. Their proofs use no heartbeat or recursion-depth overrides and name their reductions. Specification paths are under LibsignalBinary/Specifications/CryptoGames/, and proof paths under Computational/Proofs/CryptoGames/.
| Item | New definition | Construction and proof | VCVio form |
|---|---|---|---|
| AEAD and Encrypt-then-MAC | Deterministic AEAD with associated data and its one-time CCA game (Primitives.lean) |
etm_otcca (AEAD/EtM.lean): the advantage is at most the cipher's one-time IND-CPA advantage, plus one PRF advantage for the challenge tag, plus one PRF advantage per decryption query, plus qd / |T|, each against a named reduction |
Shaped like DetSymmEncAlg, with decryption into Option; a scheme with no associated data is the special case. The cipher is a DetSymmEncAlg and the MAC a PRFScheme; DeepMind's own cipher and MAC types do not move |
| CBC | None: CBC is a DetSymmEncAlg |
cbc_indcpa (AEAD/CBC.lean): one-time IND-CPA from a PRF on blocks plus a birthday term |
Over a block cipher given as a keyed permutation, with the block size a parameter. Security uses the PRF advantage of the forward direction. DeepMind's version stubs decryption; the VCVio version decrypts and proves correctness |
| Forward-secure AEAD (FS-AEAD) | The FS-AEAD scheme and game (FSAEAD/, 1,501 lines) |
The construction from an AEAD and a PRG, and its security theorem (FSAEAD/, 10,051 lines of proof in 14 files), with named PRG and AEAD reductions |
Over the AEAD above and PRGScheme. Definition, construction and theorem merge together, split into files under VCVio's 1,500-line limit |
BAIF's secure-messaging proves the same one-time Encrypt-then-MAC bound (etmAEAD_security), a one-time AES-GCM bound from a PRP (gcmOneTimeAEAD_security) and Wegman–Carter MACs, and has FS-AEAD definitions with correctness. Only one Encrypt-then-MAC proof lands.
#1161 designs the multi-query, randomized counterparts (left-or-right CPA and CCA games, PRF encryption and Encrypt-then-MAC), implemented in #1164 and the draft #1165. The deterministic AEAD row should share its Encrypt-then-MAC with them rather than duplicate it.
ACD19 is Alwen, Coretti and Dodis, "The Double Ratchet: Security Notions, Proofs, and Modularization for the Signal Protocol" (ePrint 2018/1037).
PRs:
- Deterministic AEAD, Encrypt-then-MAC, and its one-time CCA bound, in one PR.
- CBC with decryption, correctness, and one-time IND-CPA.
- FS-AEAD: definition, construction and security theorem, as a stack that merges together (after the AEAD PR).
Dropped, each with what would bring it back:
| DeepMind definition | Why it is dropped | What would bring it back |
|---|---|---|
| Gap-DH, its strong variant, and Diffie–Hellman on curves with a cofactor | No generic scheme is proved secure under it; only PQXDH uses it | A generic scheme proved under Gap-CDH, such as a hashed ElGamal KEM, or a generic-group bound (#846) |
| KEM binding (SH-CR) and δ-correctness | Assumptions about Kyber; no construction is proved to satisfy them and no generic theorem uses them | A KEM proved binding or δ-correct, or a theorem that uses them |
| EUF-CMA with a DDH oracle, and the X25519/XEdDSA key-reuse assumption | Used only as PQXDH assumptions | A signature scheme proved secure in that setting |
| Continuous key agreement (CKA) and CKA from DDH | DeepMind proves only correctness; the security proof it cites is not in the public repository | A DDH-CKA security proof following ACD19. BAIF's secure-messaging has one (CKA/FromDDH/Security.lean) |
| PRF-PRNG | Only an assumption on Signal's root key derivation | A construction with a proof |
| The secure-messaging game and the ACD19 Double Ratchet construction | The security proof imports a DeepMind-internal package | A proof without that package |
Conventions for these PRs:
- Advantages use VCVio's
ℝ≥0∞boolBias. Where that differs from the paper's normalisation by a factor of 2, the docstring says so. - Each definition says where it departs from the paper. DeepMind marks such departures with DEV notes. For example, its one-time CCA decryption oracle refuses only the challenge pair, which is stronger than the ACD19 game; the VCVio version follows the paper or states the difference.
- Before a PR lands, check it for hypotheses of the form
∀ A, Adv A ≤ εon computational games. Such a hypothesis is false for unbounded adversaries and makes the theorem vacuous.
Everything specific to Signal stays in DeepMind's repository: the primitive-oracle device and byte-level DDH queries, Gap-DH over X25519 bytes and clamping, the PQXDH games, truncated HMAC and HKDF message-key derivation, the wire AEAD, and the Signal secure-messaging game and ratchet.
Cost: the DSL as one instance of the framework
DeepMind's CostedReduction (Computational/Specifications/Reductions/ReductionDsl/Core.lean) matches PolyFun's Handler.CostedReduction (Verified-zkEVM/PolyFun#396) with one particular exchange function. Its per-kind cost is a vector charge (Certified.ofDemand), and its two-stage reductions correspond to runUntil. PolyFun lacks two generic pieces, and VCVio lacks a statement shape that uses them:
- A stateful costed reduction in PolyFun: setup, a stateful handler within a charge, and finish, with bound
setupCost + exchange B + finishCost, a per-kind form, and a form for handlers certified only on allowed answers (feat(pfunctor): certified handlers over allowed answers PolyFun#432). Expected-cost transfer through stateful handlers, which feat(probability): expectations and expected charges of free programs through the fold PolyFun#445 listed as not included, has merged as feat(pfunctor): transfer expected cost through stateful handlers PolyFun#486. It should also absorb the general lemmas of feat(GroupModel): cost certificates for handler reductions #942 (open), so that the group-model cost certificates become an instance. - A tick interface in PolyFun: a
Ticksignature, its charge,eraseTicks, and the laws (erasure commutes with bind and lifting, and ticks leave the other charges unchanged). This is the instrumentation stage of the three-stage split in Interaction cost: discrete bounds on interface use, consolidated across PolyFun, VCVio, ArkLib and CatCrypt PolyFun#387, and CatCrypt's timed trees could rebase on it. - The statement shape in VCVio: a named costed-reduction family with a bounds structure, a bridge from
CostedReductionto the existingReductionWithCost(CryptoFoundations/Asymptotics/ReductionCost.lean), and ElGamal's reduction restated with its cost derived from its code (Tracking: connecting VCVio to cslib-frontier (strict PPT, VCVioFrontier, adequacy) #906) as the first consumer. - Only if we want existential statements over reductions: a description measure on PolyFun's scoped program syntax (feat(ipfunctor): kept value contexts, and continuous interpretations of binding signatures PolyFun#436 to feat(ipfunctor): import typed scoped syntax with kernel acceptance, per-declaration budgets and bundles PolyFun#439), with a counting theorem as for PolyFun's
DescriptionMeasure.
Questions for Quang, Devon and Bas before the first cost PR:
- Who charges the reduction's own code between calls: ticks on an instrumented program in PolyFun, CatCrypt's derivation tactics, or a realization layer later. Tracking: connecting VCVio to cslib-frontier (strict PPT, VCVioFrontier, adequacy) #906 lists a cost language for reduction code as open.
- Whether to generalise
Handler.CostedReductionin place or add a stateful structure beside it. - Whether to rebase feat(GroupModel): cost certificates for handler reductions #942 onto the stateful costed reduction before it merges, or merge it and refactor later.
- Whether to support statements of the form "there exists a reduction R" at all, and with which description bound: a constant, DeepMind's
2^24 + 2^12 · bits(budget), or a polynomial. - Whether the adversary's coin draws count against the reduction or the adversary. DeepMind's headline does not count them.
- Worst-case versus expected cost. feat(probability): expectations and expected charges of free programs through the fold PolyFun#445 provides both readings (expected charges and expected query counts); the open question is which one VCVio's cost statements use. Concrete versus asymptotic statements are also open (Shared cost model for reduction code (VCVio #906, PolyFun #337) lean-crypto-foundations/QuantumFoundations#5).
The docstring of each cost statement says what the bound leaves uncharged, and that per-operation prices are trusted until an adequacy theorem ties them to a machine. No name contains PPT.
Not now
| Item | Needs | Instead |
|---|---|---|
| DeepMind's DSL instance in VCVio or PolyFun | DeepMind | The DSL stays in DeepMind's repository. The generic cost pieces go ahead with ElGamal and #942 as consumers |
| A costed reduction with any number of pauses | A consumer other than the DSL | Parked |
| A shared interface with Signal Shot's ACD19 definitions | Another project | VCVio fixes its own interfaces |
| Author names or header changes agreed with DeepMind | DeepMind | Not needed under CONTRIBUTING.md |
| DeepMind moving to a VCVio release and deleting its copies | DeepMind | An optional note after the PRs land |
| The secure-messaging game and the Double Ratchet construction | A proof without DeepMind's internal package | Dropped until such a proof exists |
Related
- Tracking: connecting VCVio to cslib-frontier (strict PPT, VCVioFrontier, adequacy) #906: computational complexity, the reserved
PPTname, and a cost language for reduction code - Quantum reductions as signature morphisms, and gate-level cost #965: quantum reductions and gate-level cost
- Tracking: generic and algebraic group models (GGM and AGM) #846: generic and algebraic group models; feat(GroupModel): cost certificates for handler reductions #942 is an open group-model PR (feat(GroupModel): Type 1 and Type 2 pairing models and the separations of DDH #949 merged)
- feat(OracleComp): mapLens, transporting oracle computations along lenses #1016 (merged):
mapLens, needed for the eager/lazy lemma - refactor(EvalDist): import the generic measure semantics from PolyFun, with names unchanged #1085 (merged, replaces refactor(EvalDist): import the generic measure semantics of free programs from PolyFun #1029): VCVio imports PolyFun's measure layer with names unchanged
- feat(probability): measure and kernel semantics of free programs, and the security boundary PolyFun#441 (merged): measure and kernel semantics of free programs; PolyFun's boundary with VCVio becomes security
- feat(probability): optional and exceptional computations, couplings and relational program logic PolyFun#444 (merged): couplings and relational program logic; the coupling rule above builds on it
- feat(probability): expectations and expected charges of free programs through the fold PolyFun#445 (merged): expectations and expected charges; feat(pfunctor): transfer expected cost through stateful handlers PolyFun#486 (merged) adds their transfer through stateful handlers
- feat(probability): uniform draws, and output measures of certified meanings PolyFun#446 (merged): uniform draws; the pure distribution lemmas above build on it
- feat(ipfunctor): kept value contexts, and continuous interpretations of binding signatures PolyFun#436 to feat(ipfunctor): import typed scoped syntax with kernel acceptance, per-declaration budgets and bundles PolyFun#439 (merged): scoped program syntax, the home for a description measure
- feat(pfunctor): certified handlers over allowed answers PolyFun#432: certified handlers over allowed answers (merged)
- Probability layer: measure interpretations in PolyFun, security in VCVio PolyFun#400: the probability layer's tracker
- proof: extend until-bad bounds through common random tails #1026 (merged): until-bad bounds through common random tails
- Design: multi-query CPA and CCA games for
SymmEncAlg, with PRF encryption and Encrypt-then-MAC #1161, feat(SymmEncAlg): left-or-right CPA game for multiple encryptions, and CPA security of PRF-based encryption #1164 and feat(SymmEncAlg): left-or-right CCA game, and CCA security of Encrypt-then-MAC #1165: multi-query CPA and CCA games forSymmEncAlg, PRF encryption and Encrypt-then-MAC - Beneficial-AI-Foundation/secure-messaging: BAIF's Lean results on AEAD, Encrypt-then-MAC and GCM (see the comment below)
- Interaction cost: discrete bounds on interface use, consolidated across PolyFun, VCVio, ArkLib and CatCrypt PolyFun#387: interaction cost across PolyFun, VCVio, ArkLib and CatCrypt
- feat(pfunctor): certified handlers, costed reductions and stateful certificates PolyFun#396: certified handlers and costed reductions (merged)
- Monoidal closed tensor and the multiset comonad on lenses PolyFun#419 (closed): monoidal closed tensor and the multiset comonad on lenses (rewinding costs); its content merged as feat(pfunctor): monoidal closed structure of the tensor of lenses PolyFun#429 to feat(pfunctor): the weighted exponential on lenses PolyFun#431, feat(pfunctor): the graded exponential and count matrices on lenses PolyFun#448 and feat(pfunctor): Seely isomorphisms and the commutative comonoid for bangW PolyFun#449
- PolyFunFrontier: the cslib-frontier side of PolyFun PolyFun#425 (the cslib-frontier side) and Composition laws for quantitative realizations PolyFun#505 to A reference cost language in core PolyFun PolyFun#507 (backend-relative bounds, from the closed Backend-relative resource bounds roadmap PolyFun#279)
- Shared cost model for reduction code (VCVio #906, PolyFun #337) lean-crypto-foundations/QuantumFoundations#5: a shared cost model for reduction code
- CatCrypt's response to 'Crypto Foundations: one structure for shared code' lean-crypto-foundations/QuantumFoundations#18: CatCrypt's response on shared structure
Activity
astefano commentedon Nov 19, 2026
please see that at baif, we too had results (before gdm), about aead, etm, gcm, ... the docs make it maybe easier to see our material: https://beneficial-ai-foundation.github.io/secure-messaging/
the source code is at https://github.com/Beneficial-AI-Foundation/secure-messaging; please let us know if of interest to upstream some of our work.
dtumad commentedon Nov 20, 2026
Thanks, @astefano. We had a look, and several parts of secure-messaging would fit well upstream:
ToVCVio: PRP/PRF switching, Wegman–Carter MACs, and the bad-flag and identical-until-bad simulation lemmas;Would you like to open PRs for these yourselves, or would you rather we adapt some of them here, crediting your group? Either way, ports would target current
main, which is now on Lean v4.36 and takes its measure semantics from PolyFun (#1085, #1169). We may also use your proofs as a guide to where VCVio needs better automation.dtumad commentedon Nov 20, 2026
@quangvdao, I refreshed the body against
main(7c167e88):SymmEncAlg, with PRF encryption and Encrypt-then-MAC #1161, feat(SymmEncAlg): left-or-right CPA game for multiple encryptions, and CPA security of PRF-based encryption #1164 and feat(SymmEncAlg): left-or-right CCA game, and CCA security of Encrypt-then-MAC #1165 next to the AEAD row;Nothing else changed.
astefano commentedon Nov 21, 2026
Thanks for taking the time to look into this. As you find it's best. I assume it's maybe smoother that the vcvio team adapts the results worth including in vcvio. If you prefer that we open prs, please let us know.
dtumad commentedon Nov 21, 2026
@astefano I don't mind doing this myself, my main question would just be what convention you want for attribution. It seems everything is Apache(?), and I will add
Authors: Beneficial AI Foundationon things, but I think a lot will naturally belong as part of larger files with many authors so just want to double check on this.I will also probably generalize a lot of lemmas/constructions to
PolyFun, but I'll try to maintain the corresponding interface inVCVioif you eventually want to delete your copies.