Research proof index

Monotonicity of Probability If event A (defined by predicate f) implies event B (defined by predicate g) for all outcomes r, then the probability of A is less than or equal to the probability of B.

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.

Probability of a nonzero polynomial evaluating to zero over a uniform product distribution is at most d / m, where d bounds the total degree and m bounds below the cardinality of each factor. This bridges schwartz_zippel_counting with the probability formulation.

Helper lemma for probability marginalization. Pr_{ (x, y) ← D₁ × D₂ }[ P x ] = Pr_{ x ← D₁ }[ P x ]

Schwartz-Zippel Lemma (Probability Form): For a non-zero multivariate polynomial P of total degree at most d over a finite field L, the probability that P(r) evaluates to 0 for a uniformly random r is at most d / |L|.