Theorem 6.9 — adaptive pseudorandomness
OpenPPSLattice.Supplement.theorem_6_9cryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandomness
For an efficient, correct, fully compact bit-message PPS, payload hiding implies adaptive pseudorandomness of the PSPRG in Construction 6.2, with at most one projection query and terminal admissibility .
Differences from the source:
- encoding: The source uses a uniform PPT oracle experiment → Lean records query sets and the single projection flag in a fuel-bounded reactive run and scores inadmissible transcripts by an independent fair bit; reason: this preserves the printed adaptive query order and final admissibility test in a total function.
Preamble
import Mathlib import Definitions.Def_PPSLattice_Supplement_PPSBit import Definitions.Def_PPSLattice_Supplement_PSPRG set_option autoImplicit false
Formal statement
namespace PPSLattice.Supplement
/-- **Theorem 6.9 (Adaptive Pseudorandomness)**, Goyal--Yadugiri, STOC 2027 submission
(manuscript sha256 7f9c493f...), p.48. Payload hiding alone implies adaptive pseudorandomness of
Construction 6.2.
**Formalization Note.** The game permits arbitrary interleaving of evaluation queries with at most
one projection query and checks `I ∩ T = ∅` only at the end; it is not a selective game. -/
theorem theorem_6_9 (E : PPS)
(hEff : E.Efficient)
(hCorrect : PPSLattice.Supplement.PPS.BitCorrect E)
(hCompact : PPSLattice.Supplement.PPS.BitFullyCompact E)
(hPayload : PPSLattice.Supplement.PPS.BitPayloadHiding E) :
(construction62 E).AdaptivelyPseudorandom := by sorry
end PPSLattice.Supplement
Source
Goyal–Yadugiri, STOC 2027 submission (manuscript sha256 7f9c493f…), Theorem 6.9, p.48