Research proof index

For a computation that is structurally within budget, the budget check in the counting semantics is redundant on the support.

Overwriting one coordinate of a uniform function table is measure-preserving. Drawing a value u uniformly from R, then a full function table g : D → R uniformly, and returning Function.update g t u yields the same distribution as drawing the table directly. This is the t-marginal independence of the uniform (product) distribution on D → R:...

Restricting a uniform function table to a subdomain along an injection is uniform. For an injection e : A → B between finite types, drawing a uniform table g : B → R and restricting it along e (i.e. g ∘ e) yields the uniform distribution on A → R. This is the marginalization of the uniform (product) distribution on B → R onto the block of...

If val z.2 ≤ c for all z in the support of costDist, then expectedCost ≤ c. This is the key bridge from worst-case (support) bounds to expected bounds.

CMA-to-NMA reduction for Fiat-Shamir signatures built from a Sigma protocol. The reduction runs the CMA adversary with simulated signing transcripts and a managed random oracle, then appends a single explicit live random-oracle query for the forgery's hash point so that the verification challenge is part of the forkable transcript (the `nmaAdvFromCmaWithF...

Running the inner unifForward + roImpl simulator against a source computation with an nmaHashQueryBound Q can grow the internal queryLog by at most Q. Each source Sum.inr step consumes one unit of the nmaHashQueryBound budget, while roImpl appends to queryLog only on a cache miss, hence at most once per such step.