Repository navigation
Description
Objective
Connect VCVio to cslib-frontier, so that it has one definition of probabilistic polynomial time and one route to proving it:
- Definition.
PPTmeans cslib-frontier's (formerly complexitylib) strict uniformIsPPTandIsOraclePPT: one finite fair-coin machine and one polynomial clock, fixed across the security parameter. - Proof method. It is proved through PolyFun's quantitative witnesses and VCVio's backend-relative
IsOraclePPTBy. An adequacy theorem connects the two.
The generic theory (the backend, typed-oracle encodings and adequacy) lives in PolyFun, tracked in Verified-zkEVM/PolyFun#425, which superseded Verified-zkEVM/PolyFun#337. This issue tracks VCVio's side, including the VCVioFrontier package in review in #1206. The design record is docs/design/computational-complexity.md; this issue is its checklist.
Current state
The status of the design doc's delivery phases at main f1e63c78:
- Foundation and usability audit: landed.
- Quantitative PolyFun core and first bounded closure: landed.
- Backend-neutral bridge, with
IsOraclePPTBy, contracts and certificates: landed. - Optional backend package:
VCVioComplexitywas removed in chore: remove VCVioComplexity and VCVioCslib, and fold VCVioWidgets into Examples #1073. Machine-level backends now go in PolyFun's nestedPolyFunFrontierpackage (PolyFunFrontier: the cslib-frontier side of PolyFun PolyFun#425) and VCVio’s companion package (in review in feat(frontier): sync PolyFun and realize one-time pad and ElGamal security #1206). - Adequacy: not landed. The general implication from
IsOraclePPTByto a strict open-oracle machine remains open. - End-to-end canaries and tooling: partly landed. feat(frontier): sync PolyFun and realize one-time pad and ElGamal security #1206 adds machine-level one-time pad secrecy and a DDH bound for the implemented one-time ElGamal experiment.
- Expected time: not landed.
- Reactive/UC complexity: not landed. The findings are in the comments below, and the UC side is UC follow-ups from the PolyFun UC audit (HasPlugFactorization, quotient semantics, graded observations, non-vacuous OTP) #633.
What cslib-frontier (formerly complexitylib) changes
- Phases 4 and 5. complexitylib now has oracle machines (
MultiTapePTM.runOracle) and the oracle predicateIsOraclePPTOn, with closure rules and open stateful substitution (IsOraclePPT.run_interpret_preprocess_open). This replaces the planned VCVio-ownedOracleTM. Adequacy becomes a generic PolyFun theorem, and VCVio states nothing machine-level of its own. - Closure. Its tidy multi-tape calculus inhabits every structural mixin and gives exact composition cost, so the general closure gate of phase 4 can be met.
- Programs.
ProbCompis the sameFreeMin both libraries, by reducible unfolding. - Query bounds. VCVio's
IsQueryBoundis already PolyFun'sIsRollBound(see refactor(QueryTracking): prove the total query bound laws by PolyFun's roll-bound laws #889), and PolyFun proves complexitylib'sHasQueryBoundsequivalent to it when every response type is inhabited. Its special cases (IsQueryBoundP,IsTotalQueryBound,IsPerIndexQueryBound,AllQueriesSatisfy) are now PolyFun charge bounds (refactor(query-bound): derive query-bound special cases from PolyFun charge bounds #1060).
VCVioFrontier
PR #1206 adds VCVioFrontier/ as a nested Lake package for the parts of VCVio that need cslib-frontier, with core VCVio staying backend-neutral. It mirrors PolyFun's PolyFunFrontier (Verified-zkEVM/PolyFun#424, #425). This section moved here from #1149.
Shape
- Lakefile: requires
VCViobypath = ".."; cslib-frontier pinned by commit (87063d8ain feat(frontier): sync PolyFun and realize one-time pad and ElGamal security #1206); PolyFun at VCVio's pin; and cslib and Mathlib at cslib-frontier's pins, declared last. - Toolchain: cslib-frontier's (
v4.36.0-rc2when planned), with its own committed manifest. - Scripts:
scripts/check-pins.pychecks the pins and--sync-fromupdates them from a PolyFun commit. - Layout: modules at their VCVio-relative path with
-- frontier: …markers, and aVCVioFrontierTestlibrary. - CI: a separate
frontier.ymlworkflow filtered by path, running the build plus the axiom sweep. - Guard: core and Interop never import
CslibFrontier.*,VCVioFrontier.*orPolyFunFrontier.*, and the root lakefile and manifest never name cslib-frontier. An umbrella check covers the nested package. - Conventions: never
open Cslib, becauseProbComp,OracleComp,OracleSpecandunifSpeccollide and both libraries define appttactic.
Roadmap
The items marked in review are in #1206, which uses Verified-zkEVM/PolyFun#511 on Verified-zkEVM/PolyFun#510.
- Spike: VCVio's import closure on v4.36. VCVio moved to v4.36.0 in chore(deps): port VCVio to v4.36 and adopt upstream program logic and measure APIs #1169.
- Package skeleton: lakefile, README, pin checks and sync, CI and import isolation. In review.
- M1 (program bridge): canaries that both libraries'
ProbCompare the same CSLibFreeM, and𝒟[p] = (Cslib.ProbComp.eval p).toMeasure. In review. - M2 (asymptotic bridges):
negligible ↔ Cslib.Crypto.Negligible;boolDist = Game.advantage;SecurityGame.secureAgainst ↔ Game.Indistinguishable. In review. - M3 (strict PPT): a typed-adversary strict-PPT predicate, stated through PolyFun's encoding lenses into the word interface rather than VCVio-specific encodings (word programs
IsPPTand equal in distribution through pinned encodings); the strict-PPT instantiation of the family-levelsealSchemehiding theorem (feat(PointerChainPuzzle): asymptotic hiding for parameter families of the sealed scheme #1152), with efficiency preservation of the reduction as a hypothesis. Partly in review. feat(frontier): sync PolyFun and realize one-time pad and ElGamal security #1206 givesElGamal.AdversaryRealizationfor the two ElGamal procedures. The general encoding-lens predicate and thesealSchemeinstantiation remain open. - M5 (first discharged reduction): In review.
ElGamal.ddhReduction_isPPTproves the one-time DDH reduction is strict PPT for each strict-PPT word adversary. For a word adversary realizing a typed adversary,AdversaryRealization.machine_output_openOracleidentifies the machine’s output law with the encoded result of VCVio’s original handled reduction. ElGamal proof walkthrough - Later: discharge the
sealSchemereduction's efficiency. That needs typed-to-word oracle encodings, the memoized random oracle and byte certificates.
Scope notes
- Strict uniform PPT applies to parameter families. Fixed-size instantiations such as leanSeal get concrete statements only: an asymptotic class bounds nothing at a fixed parameter.
- cslib-frontier has no
ByteArray/UInt8polynomial-time certificates yet.
Checklist
- Unqualified
IsPPT. Export it as complexitylib's predicate, after PolyFun's adequacy theorem lands. This settles the reservation in the design doc's "Decision summary". - Second-order bounds. Decide whether response-size models remain a separately named notion. complexitylib's oracle clock is first-order: polynomial in the input, with replies read through bounded prefixes.
- Crypto overlap. Decide how VCVio relates to complexitylib's
Cslib.Cryptolayer (games, negligibility, PRG/PRF/GGM). Adopt only its complexity predicates. - Docs. Bring the delivery-phase status in
docs/design/computational-complexity.mdup to date. Partly done: the doc records the removal ofVCVioComplexityand the move to cslib-frontier, andVCVioComplexity/PROVENANCE.mdwent with chore: remove VCVioComplexity and VCVioCslib, and fold VCVioWidgets into Examples #1073.
Moved from PolyFun #279
These VCVio items were listed under "Downstream" in Verified-zkEVM/PolyFun#279. They are checked against main 8cd101a9; the cost items were rechecked against main c2192f88 on 9 November.
- El Gamal vacuity. Done in refactor(ElGamal): state multi-query IND-CPA with the hybrid reductions named #941:
elGamal_IND_CPA_le_sum_ddhAdvantage(Examples/ElGamal/Basic.lean) bounds the advantage by the named hybrid reductions.elGamal_IND_CPA_le_q_mul_ddh(Examples/ElGamal/Basic.lean:298) assumeshddhfor the reduction of every one-time adversary.- An adversary that computes the discrete log has one-time advantage 1. By
elGamal_oneTime_advantage_eq_two_mul_ddhAdvantage, that is twice its reduction's DDH advantage, sohddhforcesε ≥ 1/2, and the conclusion is trivial forq ≥ 1. - Restate the theorem pointwise over
A's own hybrid adversaries:IND_CPA_Advantage A ≤ q · 2 · max_i ddhAdvantage (R (A_i)). - Pin the vacuity with a canary, and audit the other
∀ advhypotheses.
- Resource-model declarations.
- Interface charges: done, through PolyFun's interface-cost stack (Interaction cost: discrete bounds on interface use, consolidated across PolyFun, VCVio, ArkLib and CatCrypt PolyFun#387) and refactor(query-bound): derive query-bound special cases from PolyFun charge bounds #1060 and Derive cost transfer, determined cost and enforcement from PolyFun charge handlers #1062.
- Open: a cost language for reduction code, an adversary class,
Propgap carriers, and pinned footprints for headline theorems.
- Worst-case cost reading. Add one beside the
NecessaryandLowerreadings (VCVio/ProgramLogic/Unary/WP/). It would be PolyFun's charge-foldOpSpec.toUpperWPMonad, which PolyFun now has (PFunctor/Free/Do.lean). - Small fixes.
- A
FinEnumtag list in the PRF reader, in place ofFinset.univ.toList(Examples/PRFTagReader/Auth.lean:66). - El Gamal's
intrinsiccost derived from code (Examples/ElGamal/ReductionCost.lean:72).
- A
The UC item (replace Context.fuel with a conservation bound) moves to #633.
Related
- Tracking: generic and algebraic group models (GGM and AGM) #846: generic and algebraic group models. A counting kernel designed in PolyFun feat(falcon): add Rényi divergence and approximate arithmetic infrastructure #279 (M5), now tracked in Interaction cost: discrete bounds on interface use, consolidated across PolyFun, VCVio, ArkLib and CatCrypt PolyFun#387, gives generic DLog, DDH and point-search witnesses.
- refactor(QueryTracking): prove the total query bound laws by PolyFun's roll-bound laws #889: total query-bound laws by PolyFun's roll-bound laws.
- Composition laws for quantitative realizations PolyFun#505, Reactive conservation under composition PolyFun#506 and A reference cost language in core PolyFun PolyFun#507: backend-relative resource bounds, from the closed Backend-relative resource bounds roadmap PolyFun#279.
- Interaction cost: discrete bounds on interface use, consolidated across PolyFun, VCVio, ArkLib and CatCrypt PolyFun#387: interface cost (charges, budgets and their transfer).
- PolyFunFrontier: the cslib-frontier side of PolyFun PolyFun#425: PolyFunFrontier, PolyFun's side of the frontier packages (it superseded complexitylib integration: polynomial-time backend, oracle PPT and adequacy PolyFun#337).
- UC follow-ups from the PolyFun UC audit (HasPlugFactorization, quotient semantics, graded observations, non-vacuous OTP) #633: UC, including the efficiency of UC adversaries, simulators and environments.
- Program logic: orchestrating core
vcgen#1155: program logic, including the readings ofOracleComp.
No issue or PR is opened in complexitylib, CSLib or Mathlib as part of this work.
Activity
chore(VCVioComplexity): remove the complexitylib-v1 nested package
chore: remove VCVioComplexity and VCVioCslib, and fold VCVioWidgets i…
dtumad commentedon Nov 12, 2026
Findings on phase 8 (reactive/UC complexity), from an audit of the UC layer at
main87bc1892f. The UC side is tracked in #633.No UC notion restricts the efficiency of the adversary, simulator or environment today.
ObservedCompEmulates,ObservedCompUCSecureandStandard.UCSecuretake no bound at all.AsympObservedCompEmulates(VCVio/Interaction/UC/Computational.lean:380) takes a freeisPPT : Adv → Prop, but leaves the simulator and the systems unrestricted.ReactiveSecuritybounds only fuel.TokenBudgetCertificateandConservingexist in PolyFun, but no security notion requires them.Two existing designs.
spitters/CatCrypt-core) states efficiency as a predicate with closure fields,UCAdmClass(Crypto/UCAdmClass.lean:79). Its dummy-adversary equivalence uses exactly closure underpure, coproduct and bind (Crypto/CompUCEquivalence.lean:128-179).Crypto/UCAdmClass.lean:90-94). Real time classes are graded and are not instances (Complexity/D/TimeAdm.lean).f1b10c2has a Canetti-style UC layer under polynomial call budgets (CslibFrontier/Crypto/Protocols/UC/). It models interaction, not running time (Emulation.lean:41-44).The closure theorem a polynomial-time UC class needs is proved in cslib-frontier and not yet here. Absorbing an adversary into an environment, composing a simulator with an adversary, and absorbing a hybrid protocol all reduce to oracle substitution:
IsOraclePPTOn.run_interpret_preprocess_open(Computability/Probabilistic/Oracle/Substitution.lean:148), with per-call reply and state-growth allowances;VCVio/CryptoFoundations/Asymptotics/OracleClosure.lean:22-24).Direction for the UC design section (step 3 of
docs/design/uc-campaign.md, drafted locally first).PolyFunFrontier, built fromIsOraclePPTOnper activation.Canetti's Claim 14, the equivalence of environment-dependent and standard simulators, additionally needs a universal environment in the class. I found only a deterministic clocked universal multi-tape machine in cslib-frontier (
Computability/Machines/Turing/MultiTape/Universal/Clocked.lean), and no probabilistic oracle one; that absence is unconfirmed.[-]Tracking: computational complexity (PPT definition, complexitylib backend, adequacy)[/-][+]Tracking: connecting VCVio to cslib-frontier (strict PPT, VCVioFrontier, adequacy)[/+]