Research proof index

Predicate query bound. If oa makes at most n queries matching p, the transcript contains at most n p-matching entries (QueryLog.countQ).

Self-log fixed point. The two log layers produced by oa.withQueryLog.withQueryLog agree on every support point: simulating the logging oracle over oa.withQueryLog records exactly the queries that the inner withQueryLog already recorded, since withQueryLog does not add new queries to the underlying OracleComp.

Query-log lookup is the OracleSpec specialization of dependent lookup on PolyFun traces.

Fuelled unrolling commutes with interface transport along a lens: the unrolled query tree of the wrapped machine is the lens-translated unrolled tree. The syntactic (FreeM-level) content of interface wrapping, from which handler-level wrapping laws follow by FreeM.liftM naturality without touching machine states.

Boneh-Shoup Theorem 6.2. PRF security implies UF-CMA security for the derived MAC: for any forger A, the constructed distinguisher macToPRFReduction prf A satisfies UF_CMA_Advantage(A) ≤ prfAdvantage(prf, B) + 1/|R|.

In the ideal PRF experiment (random oracle), the reduction succeeds with probability at most 1/|R| , a fresh random oracle query is independent of the forger's output.