Repository navigation
Conversation
🤖 PR SummaryMathematical FormalizationIND-CCA Security Game (
|
| Metric | Count |
|---|---|
| 📝 Files Changed | 3 |
| ✅ Lines Added | 1037 |
| ❌ Lines Removed | 0 |
Lean Declarations
✏️ Added: 63 declaration(s)
VCVio/CryptoFoundations/SymmEncAlg/INDCCA.lean (9)
@[expose] def IND_CCA_Adversary.MakesAtMostDecryptionQueries@[expose] def IND_CCA_Experiment [DecidableEq C] (encAlg : SymmEncAlg (OracleComp spec) M K C)@[expose] def IND_CCA_Game [DecidableEq C] (encAlg : SymmEncAlg (OracleComp spec) M K C)@[expose] def IND_CCA_challengeImpl (encAlg : SymmEncAlg (OracleComp spec) M K C) (k : K)@[expose] def IND_CCA_decryptImpl [DecidableEq C] (encAlg : SymmEncAlg (OracleComp spec) M K C)@[expose] def IND_CCA_impl [DecidableEq C] (encAlg : SymmEncAlg (OracleComp spec) M K C) (k : K)@[expose] noncomputable def IND_CCA_Advantage [DecidableEq C]abbrev IND_CCA_Adversary (_encAlg : SymmEncAlg (OracleComp spec) M K C)theorem IND_CCA_Advantage_probComp [DecidableEq C] (encAlg : SymmEncAlg ProbComp M K C)
VCVio/Schemes/EncryptThenMac.lean (54)
@[expose] def ForgeryAt (vf : C → T → Bool) (j : ℕ) (s : GameState C T) : Prop@[expose] def ForgeryLogged (vf : C → T → Bool) (s : GameState C T) : Prop@[expose] def FreshValidAt (vf : C → T → Bool) (j : ℕ) (s : GameState C T) : Prop@[expose] def StopInv (j : ℕ) (s : GameState C T) : Prop@[expose] def ccaDecryptImpl (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)@[expose] def ccaLogImpl (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)@[expose] def challengeImpl (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)@[expose] def cpaChallengeImpl (mac : MacAlg ProbComp C Km T) (km : Km) :@[expose] def cpaDecryptImpl :@[expose] def cpaReduction (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)@[expose] def cpaReductionImpl (mac : MacAlg ProbComp C Km T) (km : Km) :@[expose] def flattenWriterT (impl : QueryImpl spec (StateT σ (WriterT (List A) ProbComp))) :@[expose] def forger [Inhabited C] [Inhabited T] (enc : SymmEncAlg ProbComp M Ke C)@[expose] def forgerChallengeImpl (enc : SymmEncAlg ProbComp M Ke C) (ke : Ke) (leak : M → Λ)@[expose] def forgerDecryptImpl : QueryImpl (C × T →ₒ Option M)@[expose] def forgerImpl (enc : SymmEncAlg ProbComp M Ke C) (ke : Ke) (leak : M → Λ) (b : Bool)@[expose] def forgerView (s : GameState C T) : List (C × T) × QueryLog (C →ₒ T)@[expose] def forgeryExperiment (enc : SymmEncAlg ProbComp M Ke C)@[expose] def rejectDecryptImpl :@[expose] def rejectExperiment (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)@[expose] def rejectImpl (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)@[expose] def scheme (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T) :@[expose] def stopChallengeImpl (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)@[expose] def stopImpl (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)@[expose] noncomputable def forgerTaggedImpl (enc : SymmEncAlg ProbComp M Ke C)abbrev GameState (C T : Type)abbrev ccaSpec (M C T : Type)lemma forgeryAt_of_freshValidAt {vf : C → T → Bool} {j : ℕ} {s : GameState C T}lemma forgeryLogged_append {vf : C → T → Bool} {s : GameState C T} (h : ForgeryLogged vf s)lemma rejectImpl_run_inl_inl (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)lemma rejectImpl_run_inr (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)lemma run_simulateQ_liftTarget_writerT {α : Type} (oa : ProbComp α) :lemma snd_of_mem_support_challengeImpl (enc : SymmEncAlg ProbComp M Ke C)lemma stopImpl_run_inl_inl (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)lemma stopImpl_run_inl_inr (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)lemma stopImpl_run_inr (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)lemma win_forgerView_of_forgeryAt [Inhabited C] [Inhabited T] {vf : C → T → Bool} {j : ℕ}theorem IND_CCA_Advantage_le [Inhabited C] [Inhabited T] (enc : SymmEncAlg ProbComp M Ke C)theorem IND_CCA_Experiment_eq (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)theorem agreeUntilBad_ccaLogImpl_rejectImpl (enc : SymmEncAlg ProbComp M Ke C)theorem boolDist_IND_CCA_Experiment_rejectExperiment_le (enc : SymmEncAlg ProbComp M Ke C)theorem forgeryExperiment_le_sum [Inhabited C] [Inhabited T] (enc : SymmEncAlg ProbComp M Ke C)theorem forgeryLogged_imp_exists_freshValidAt (enc : SymmEncAlg ProbComp M Ke C)theorem map_run_simulateQ_evalDistEq_of_eq_until_stoppedtheorem map_run_simulateQ_evalDistEq_pure_of_stopped (impl : QueryImpl spec (StateT σ ProbComp))theorem map_run_simulateQ_stopImpl (enc : SymmEncAlg ProbComp M Ke C)theorem prEvent_rejectImpl_freshValidAt_eq (enc : SymmEncAlg ProbComp M Ke C)theorem preservesInv_rejectImpl (enc : SymmEncAlg ProbComp M Ke C)theorem preservesInv_stopImpl (enc : SymmEncAlg ProbComp M Ke C) (mac : MacAlg ProbComp C Km T)theorem rejectExperiment_eq_IND_CPA_Experiment (enc : SymmEncAlg ProbComp M Ke C)theorem run'_simulateQ_rejectImpl (enc : SymmEncAlg ProbComp M Ke C)theorem run_simulateQ_eq_map_flattenWriterTtheorem run_simulateQ_flattenWriterT (impl : QueryImpl spec (StateT σ (WriterT (List A) ProbComp)))theorem strongUnforgeableExperiment_forger [Inhabited C] [Inhabited T]
sorry Tracking
- No
sorrys were added, removed, or affected.
📋 **Additional Analysis**
Review Findings
Copyright header
- Both new files (
INDCCA.leanandEncryptThenMac.lean) correctly include the standard header with the author name and copyright year 2026. No issues.
File structure (prologue layout)
INDCCA.lean: Header, blank line,module, thenpublic importlines, blank line, then module docstring. Correct.EncryptThenMac.lean: Header, blank line,module, thenpublic importlines, blank line, then module docstring. Correct.
Module docstrings
- Both files have module docstrings giving a concise title and summary, with references when material. Check.
INDCCA.lean: includes notation reference (Katz–Lindell §5.1.2) and lists main definitions/statements. Check.EncryptThenMac.lean: includes references, a proof sketch, and lists main definitions/statements. Check.
Declaration docstrings
INDCCA.lean: All exposed definitions have descriptive docstrings. Check.EncryptThenMac.lean: All exposed definitions have descriptive docstrings. Check.
Section headers
- Both files use
/-! ## Section title -/doc-comment headers, not ASCII banners. Check.
set_option lines
- Neither file adds any per-file
set_optionlines, including no linter suppressions. Check.
Module scopes
- Both files use
public section(notbackward.privateInPublicorbackward.proofsInPublic). Check. - They use
public import,public meta import, or plainimportappropriately. Check. - No cross-package
import all PolyFun.…appears. Check. - The
@[expose]attribute is used on definitions where unfolding is part of the intended public API (e.g.IND_CCA_Adversary.MakesAtMostDecryptionQueries,IND_CCA_challengeImpl, etc.) and not on all definitions. Check.
Imports
- Imports are at the top of each file, after the module line. Check.
INDCCA.leanimportsINDCPAandOracleComp.SimSemantics.StateT.Basic; these are conceptually within the same module layer. Check.EncryptThenMac.leanimportsSymmEncAlg.INDCCA,MacAlg, and a fewOracleCompsimulation helpers. These respect the module layering described inAGENTS.md(CryptoFoundations before Schemes). Check.
omit usage
- Several
omit [DecidableEq C] [DecidableEq T]lines appear inEncryptThenMac.leanfor lemmas that do not need these instances. The number ofomitlines is not excessive relative to the number ofvariablebinders; each omission is for a specific lemma where the omitted instance is not used in the proof. Check.
variable usage
- Variables are declared with
variableat the top of thepublic sectionor in sub-sections. The[DecidableEq C] [DecidableEq T] [DecidableEq Λ]assumptions are placed on thesectionthat genuinely needs them (the game definitions and security theorems). For lemmas that do not need them,omitis used. This matches the guidance on section variables. Check.
Naming conventions
- Terms of
Props (e.g.ForgeryLogged,FreshValidAt,StopInv,MakesAtMostDecryptionQueries) useUpperCamelCase. The.leanfile itself usesUpperCamelCasefor the module name, but the definition names are correctly capitalized. - Functions are named as their return types:
IND_CCA_Adversary,IND_CCA_challengeImpl,ccaLogImpl, etc. – these match the Mathlib naming rules. - Theorem names are
snake_case(e.g.IND_CCA_Advantage_probComp,agreeUntilBad_ccaLogImpl_rejectImpl, etc.). Check.
Buildability (not tested, but structure suggests compliance)
- No
sorryappears in either file. - The new files are added to the umbrella import in
VCVio.lean(bothpublic importlines in the diff). The contributor likely ran./scripts/update-lib.shafter adding the files; this cannot be verified from the diff alone, but the imports inVCVio.leanare present.
Exposed definitions and public sections
INDCCA.leanuses@[expose]onIND_CCA_Adversary.MakesAtMostDecryptionQueries,IND_CCA_challengeImpl,IND_CCA_decryptImpl,IND_CCA_impl,IND_CCA_Experiment,IND_CCA_Game,IND_CCA_Advantage,IND_CCA_Advantage_probComp. The rest of the definitions (IND_CCA_Adversary) is anabbrev– not exposed, which is fine.EncryptThenMac.leanuses@[expose]onscheme,challengeImpl,ccaDecryptImpl,rejectDecryptImpl,ccaLogImpl,rejectImpl,ForgeryLogged,rejectExperiment,forgeryExperiment,cpaChallengeImpl,cpaDecryptImpl,cpaReductionImpl,cpaReduction,FreshValidAt,stopChallengeImpl,stopImpl,StopInv,ForgeryAt,flattenWriterT,forgerChallengeImpl,forgerDecryptImpl,forgerImpl,forger,forgerTaggedImpl,forgerView. This is a long list but each corresponds to a public component of the proof. The module docstring lists only the most important ones; the remaining exposed definitions are internal helpers that the rest of the construction needs. Not a violation.
Licensing
- Both headers include the Apache 2.0 license line. Check.
Unused variables/linters
- No new linter suppressions added. No warning of potential issues from the diff.
Summary of issues found
- None. The diff complies with the style guide, documentation expectations, module-scope rules, naming conventions, and attribution policy.
📄 **Per-File Summaries**
- VCVio.lean: The file now publicly imports
SymmEncAlg.INDCCA, which provides IND-CCA security definitions for symmetric encryption, andSchemes.EncryptThenMac, which defines an Encrypt-then-MAC construction. These additions indicate that the project’s security hierarchy and composable-scheme library have been extended to cover the authenticated encryption model that corresponding proofs will rely on. - VCVio/CryptoFoundations/SymmEncAlg/INDCCA.lean: Summary unavailable — AI generation failed.
- VCVio/Schemes/EncryptThenMac.lean: This file implements the formal proof that the Encrypt-then-MAC construction yields a CCA-secure symmetric encryption scheme, given a CPA-secure encryption
encand a strongly unforgeable MACmacwith deterministic verification. It defines thescheme, the CCA gameccaLogImpl, the rejecting gamerejectImpl, the CPA reductioncpaReduction, and the SUF-CMA forgersforger. The main theoremIND_CCA_Advantage_lebounds the CCA advantage of the combined scheme by the CPA advantage ofcpaReductionplus the sum of the SUF-CMA advantages of the forgers. The proof relies on the lemmaagreeUntilBad_ccaLogImpl_rejectImplshowing that the real and rejecting games coincide until a forgery is logged, the equivalencerejectExperiment_eq_IND_CPA_Experimentrelating the rejecting game to a CPA experiment, and a hybrid argumentforgeryExperiment_le_sumbounding the forgery probability via the stopping technique and the forgers.
Last updated: 2026-11-22 02:02 UTC.
e7e0ad6 to
52428c4
Compare
…d CPA security of PRF-based encryption
`VCVio/CryptoFoundations/SymmEncAlg/INDCPA.lean` defines the
multi-query left-or-right CPA game of a `SymmEncAlg` with the shared
`LeftOrRight.oracle`, keyed by the scheme's own `keygen`, mirroring
`DEMScheme.IND_CPA_Game`.
`VCVio/Schemes/PRFEncryption.lean` proves that
`Enc_k(m) = (r, F_k(r) + m)` is CPA-secure:
Adv_CPA ≤ prfAdvantage (prfReduction A true)
+ prfAdvantage (prfReduction A false) + q (q - 1) / |R|,
through a random-function game kept as a log, identical-until-bad
(`QueryImpl.AgreeUntilBad`) against a fresh-value game, and the per-query
hazard bound for nonce repetition.
…-then-MAC
`VCVio/CryptoFoundations/SymmEncAlg/INDCCA.lean` defines the multi-query
CCA game of a `SymmEncAlg`: the left-or-right oracle logs the challenge
ciphertexts in `StateT (List C)` and the decryption oracle rejects them
with `none`.
`VCVio/Schemes/EncryptThenMac.lean` proves, for a MAC with deterministic
verification (`mac.verify k c t = pure (vf k c t)`) and an adversary with
at most `q` decryption queries,
Adv_CCA(EtM, A) ≤ Adv_CPA(enc, cpaReduction A)
+ Σ_{j<q} (Adv_SUF(forger A true j) + Adv_SUF(forger A false j)).
The proof replaces decryption by rejection until a fresh valid
decryption query (`QueryImpl.AgreeUntilBad`), simulates the rejecting
game with a CPA adversary that tags its own ciphertexts, and bounds the
forgery event by guessing the decryption query. The forger stops tagging
after the guessed query; a stopping lemma
(`map_run_simulateQ_evalDistEq_of_eq_until_stopped`) shows the guessed
query has the same distribution as in the unstopped game.
52428c4 to
5f0cd47
Compare
# Conflicts: # VCVio.lean # VCVio/CryptoFoundations/SymmEncAlg/INDCPA.lean # VCVio/Schemes/PRFEncryption.lean
|
#1164 has merged, so I merged |
Depends on #1164; only the last commit is new.
Summary
Design discussion: #1161. This is the multi-query textbook theorem: a randomized
SymmEncAlgthat is CPA-secure for many encryptions, plus a SUF-CMA MAC. It complements the one-time
deterministic-AEAD bound planned in #1086. Refused and invalid ciphertexts both decrypt to
none,the convention the public-key game has used since #1104.
VCVio/CryptoFoundations/SymmEncAlg/INDCCA.leanThis file adds the multi-query CCA game of a
SymmEncAlg(Katz–Lindell 3rd ed. §5.1.2). Katz–Lindellstate the game with one challenge; this is its left-or-right form with many challenges, and the
docstring says so.
IND_CCA_Adversary encAlg := OracleComp (spec + LeftOrRight.spec M C + (C →ₒ Option M)) Bool.IND_CCA_challengeImpl: theLeftOrRight.oracle, which also logs the returned ciphertext inStateT (List C).IND_CCA_decryptImpl: answersnoneon logged challenge ciphertexts andencAlg.decrypt k cotherwise.
IND_CCA_Experiment/IND_CCA_Game/IND_CCA_Advantage(boolBias) andIND_CCA_Advantage_probComp(boolDistof the fixed-bit experiments).IND_CCA_Adversary.MakesAtMostDecryptionQueries.VCVio/Schemes/EncryptThenMac.leanThis file adds
scheme enc macwith key(kₑ, kₘ). Encryption returns(c, t)withta tag onc, and decryption returnsnoneunless the tag verifies (Katz–Lindell §5.3.1; Boneh–Shoup v0.6§9.4.1).
Main theorem
EncryptThenMac.IND_CCA_Advantage_le: for a MAC with deterministic verification(
hvf : ∀ k c t, mac.verify k c t = pure (vf k c t)) and an adversary with at mostqdecryption queries,
Named reductions:
cpaReduction: samples a MAC key, forwards challenge pairs to the CPA oracle, tags the returnedciphertexts, and answers every decryption query with
none.forger … b j: runs the game at bitbwith its own encryption key, gets tags from the taggingoracle until the
j-th decryption query, then stops tagging and outputs that query.Proof structure:
ccaLogImpl, by state projection(
IND_CCA_Experiment_eq). The logged game records each decryption query with its freshness.ccaLogImplandrejectImpl, which answers every decryption query withnone, agree until afresh decryption query verifies (
agreeUntilBad_ccaLogImpl_rejectImpl,ForgeryLogged).This gives
boolDist_IND_CCA_Experiment_rejectExperiment_le.rejectImplis the CPA game ofcpaReduction(rejectExperiment_eq_IND_CPA_Experiment).forgeryExperiment_le_sum):qdecryption queries, a logged forgery is one of the firstq(
IsQueryBoundP.cost_le_of_mem_support_run_simulateQ).j-th query has the same law in the game that stops tagging after it. This uses ageneric stopping lemma,
map_run_simulateQ_evalDistEq_of_eq_until_stopped: two handlersequal before a stopping state, which both freeze an observation afterwards, give the
observation the same law.
j-th fresh query is fresh against the final log(
preservesInv_stopImpl).forgerView, is the forger's run againstMacAlg.taggingOracle(map_run_simulateQ_stopImpl, viaQueryImpl.mapStateTBaseandflattenWriterT).Assumptions and scope:
hvf). With probabilistic verification, step 2 would raisethe bad flag with verification coins that the forger cannot reproduce.
[Inhabited C] [Inhabited T]. The forger needs a default output when fewer thanj + 1decryption queries occur.
encormac: CCA security does not need one.q_dfactor. It comes from guessing the decryption query, becauseMacAlg.strongUnforgeableExperimenthas no verification oracle. The bound keeps one forger perhidden bit and per index, so no averaging over
jis needed.Generic pieces that could move to
OracleComp/SimSemanticsif useful:map_run_simulateQ_evalDistEq_of_eq_until_stopped,flattenWriterT/run_simulateQ_flattenWriterT, andrun_simulateQ_liftTarget_writerT.No existing declaration changes.
VCVio.leangains the two imports generated by./scripts/update-lib.sh.Verification
lake build VCVio.CryptoFoundations.SymmEncAlg.INDCCA VCVio.Schemes.EncryptThenMac: 0 errors,0 warnings.
lake exe axiomsweep --check --root <module>on the four modules of this stack (122 declarations): zerosorryandzero non-standard axioms.
./scripts/update-lib.sh, thenscripts/check-imports.sh.lake lint -- --style-only.lake exe runLinter --no-build VCVio.Schemes.EncryptThenMac. Its 13 findings are alldefsWithUnderscoreonIND_CPA_*/IND_CCA_*names.scripts/lint.pyaccepts every one ofthem by its acronym-led naming policy (
acronym_led).I did not run a full
lake buildorlake lint -- --env-onlylocally. CI runs both.Checklist
CONTRIBUTING.md, AttributionAnd File Headers); docstrings are intrinsic, with no change history or "renamed from" wording.
public sectionwith per-declaration@[expose](Module Scopes), andthe expose-boundary baseline was lowered in this PR if a file was converted.
./scripts/update-lib.shleaves the umbrella files unchanged, andlake exe axiomsweep --checkpasses: nosorryand no non-standard axiom.(
axiomsweep --checkrun with--rooton the four modules of this stack (122 declarations); CI runs the whole-library sweep.)set_option linter.* false, no deprecated aliases (docs/agents/gotchas.md§18, §23),and no native FFI test executables on the PR path.
uv run --no-project --python 3.12 python scripts/check-agent-docs.pypasses.
VCVioTest/gained one-callentries, no proof gained a second tactic call outside a dated gap pair, and the before/after
line counts of the touched proofs are listed above. (N/A: no simp set changed.)