Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Publicly sampleable projective pseudorandom generator

Definition
PPSLattice_Supplement_PSPRG

by iris · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandomness

A PSPRG has polynomial-time setup, public sampling, secret projection, and indexed evaluation algorithms. Its properties require both evaluations to return the same actual bit (not two failures), projected-key compactness, sampling indistinguishability, and adaptive pseudorandomness with at most one projection query and the final condition I∩T=∅I\cap T=\varnothingI∩T=∅.

Definition code
import Mathlib
import Definitions.Def_AvgPHETH_uniformDist
import Definitions.Def_BeyondDS_tup
import Definitions.Def_NoisyOWMPC_Negligible
import Definitions.Def_PPSLattice_PPS
import Definitions.Def_PPSLattice_decBin
import Definitions.Def_PPSLattice_decSet
import Definitions.Def_PPSLattice_encBin
import Definitions.Def_PPSLattice_PPTSampler
import Definitions.Def_PPSLattice_PolyTimeOn
import Definitions.Def_RestrictedDec_Adversary

open QAlgorithms.Complexity
set_option autoImplicit false

namespace PPSLattice.Supplement

/-- A publicly sampleable projective pseudorandom generator (PSPRG), Definition 6.1, pp.43--44
of Goyal--Yadugiri (manuscript sha256 7f9c493f...). -/
structure PSPRG where
  setup : ℕ → ℕ → PMF (Str × Str)
  samp : ℕ → ℕ → Str → Finset ℕ → PMF Str
  project : ℕ → ℕ → Str → Str → Finset ℕ → PMF Str
  eval : ℕ → ℕ → Str → Finset ℕ → Str → ℕ → Option Bool

/-- The four PSPRG algorithms are uniform polynomial time; `ell` is encoded in unary, as in
Definition 6.1. -/
def PSPRG.Efficient (G : PSPRG) : Prop :=
  PPTSampler (fun x : ℕ × ℕ => BeyondDS.tup [encNat x.1, encNat x.2])
    (fun x => (G.setup x.1 x.2).map fun z => BeyondDS.tup [z.1, z.2]) ∧
  PPTSampler (fun x : ℕ × ℕ × Str × Finset ℕ =>
      BeyondDS.tup [encNat x.1, encNat x.2.1, x.2.2.1,
        BeyondDS.tup ((x.2.2.2.sort (· ≤ ·)).map encBin)])
    (fun x => G.samp x.1 x.2.1 x.2.2.1 x.2.2.2) ∧
  PPTSampler (fun x : ℕ × ℕ × Str × Str × Finset ℕ =>
      BeyondDS.tup [encNat x.1, encNat x.2.1, x.2.2.1, x.2.2.2.1,
        BeyondDS.tup ((x.2.2.2.2.sort (· ≤ ·)).map encBin)])
    (fun x => G.project x.1 x.2.1 x.2.2.1 x.2.2.2.1 x.2.2.2.2) ∧
  PolyTimeOn (fun x : ℕ × ℕ × Str × Finset ℕ × Str × ℕ =>
      BeyondDS.tup [encNat x.1, encNat x.2.1, x.2.2.1,
        BeyondDS.tup ((x.2.2.2.1.sort (· ≤ ·)).map encBin), x.2.2.2.2.1,
        encBin x.2.2.2.2.2])
    (fun x => match G.eval x.1 x.2.1 x.2.2.1 x.2.2.2.1 x.2.2.2.2.1 x.2.2.2.2.2 with
      | none => [] | some b => [b])

/-- Perfect consistency of a projected key with the full projected key (Definition 6.1). -/
def PSPRG.Correct (G : PSPRG) : Prop :=
  ∀ lam ell : ℕ, 1 ≤ lam → 1 ≤ ell → ∀ S ⊆ Finset.Icc 1 ell, ∀ i ∈ S,
    (G.setup lam ell).bind (fun z =>
      (G.project lam ell z.1 z.2 (Finset.Icc 1 ell)).bind fun skAll =>
        (G.project lam ell z.1 z.2 S).map fun sk =>
          decide ((G.eval lam ell z.1 (Finset.Icc 1 ell) skAll i = some false ∧
              G.eval lam ell z.1 S sk i = some false) ∨
            (G.eval lam ell z.1 (Finset.Icc 1 ell) skAll i = some true ∧
              G.eval lam ell z.1 S sk i = some true))) true = 1

/-- Projected-key compactness `poly(λ, log ℓ_out)`, uniformly on every output support. -/
def PSPRG.Compact (G : PSPRG) : Prop :=
  ∃ c : ℕ, ∀ lam ell : ℕ, 1 ≤ lam → 1 ≤ ell →
    ∀ z ∈ (G.setup lam ell).support, ∀ S ⊆ Finset.Icc 1 ell,
      (∀ sk ∈ (G.samp lam ell z.1 S).support, sk.length ≤ (lam + Nat.clog 2 ell + 2) ^ c) ∧
      ∀ sk ∈ (G.project lam ell z.1 z.2 S).support,
        sk.length ≤ (lam + Nat.clog 2 ell + 2) ^ c

/-- Moves in the adaptive PSPRG experiment. -/
inductive PSPRGMove
  | project (S : Finset ℕ)
  | eval (i : ℕ)
  | guess (b : Bool)

/-- `00,S`; `01,i`; or a final guess. -/
def decPSPRGMove (w : Str) : PSPRGMove :=
  let fs := BeyondDS.untup w
  match fs.getD 0 [] with
  | [false, false] => .project (decSet (fs.getD 1 []))
  | [false, true] => .eval (decBin (fs.getD 1 []))
  | _ => .guess ((fs.getD 1 []).headD false)

/-- Sampling indistinguishability: `Samp(S)` and `Project(msk,S)` cannot be distinguished for an
adaptively chosen admissible `S` (Definition 6.1, p.44). -/
noncomputable def psprgSamplingGame (G : PSPRG) (A : RestrictedDec.Adversary) (lam : ℕ) : PMF Bool :=
  (A.activate lam [] []).bind fun r0 =>
    let ell := BeyondDS.decNat r0.2
    (G.setup lam ell).bind fun z =>
      (A.activate lam r0.1 z.1).bind fun r1 =>
        let S := decSet r1.2
        if S ⊆ Finset.Icc 1 ell then
          (PMF.uniformOfFintype Bool).bind fun b =>
            (if b then G.project lam ell z.1 z.2 S else G.samp lam ell z.1 S).bind fun sk =>
              (A.activate lam r1.1 sk).map fun r2 =>
                match decPSPRGMove r2.2 with | .guess b' => decide (b' = b) | _ => false
        else PMF.uniformOfFintype Bool

/-- Recursive adaptive-pseudorandomness interaction. At most one Project query is accepted;
admissibility `I ∩ T = ∅` is checked only when the adversary guesses, exactly as printed. -/
noncomputable def psprgAdaptiveRun (G : PSPRG) (A : RestrictedDec.Adversary) (lam ell : ℕ)
    (pp msk skAll y : Str) : ℕ → Bool → Finset ℕ → Finset ℕ → Str → Str → PMF Bool
  | 0, _, _, _, _, _ => PMF.uniformOfFintype Bool
  | fuel + 1, projected, I, T, st, input =>
      (A.activate lam st input).bind fun r =>
        match decPSPRGMove r.2 with
        | .project S =>
            if !projected ∧ S ⊆ Finset.Icc 1 ell then
              (G.project lam ell pp msk S).bind fun sk =>
                psprgAdaptiveRun G A lam ell pp msk skAll y fuel true I (T ∪ S) r.1 sk
            else PMF.uniformOfFintype Bool
        | .eval i =>
            if i ∈ Finset.Icc 1 ell then
              let honest := (G.eval lam ell pp (Finset.Icc 1 ell) skAll i).getD false
              let random := y.getD i false
              psprgAdaptiveRun G A lam ell pp msk skAll y fuel projected (insert i I) T r.1
                [if y.headD false then random else honest]
            else psprgAdaptiveRun G A lam ell pp msk skAll y fuel projected I T r.1 []
        | .guess b' =>
            if Disjoint I T then PMF.pure (decide (b' = y.headD false))
            else PMF.uniformOfFintype Bool

/-- Adaptive pseudorandomness game. The first bit of `y` stores the challenge bit and the remaining
`ell` bits are the independent random output vector. -/
noncomputable def psprgAdaptiveGame (G : PSPRG) (A : RestrictedDec.Adversary) (lam : ℕ) : PMF Bool :=
  (A.activate lam [] []).bind fun r0 =>
    let ell := BeyondDS.decNat r0.2
    (G.setup lam ell).bind fun z =>
      (G.project lam ell z.1 z.2 (Finset.Icc 1 ell)).bind fun skAll =>
        (PMF.uniformOfFintype Bool).bind fun b =>
          (AvgPHETH.uniformDist ell).bind fun bits =>
            psprgAdaptiveRun G A lam ell z.1 z.2 skAll (b :: bits) (A.p.eval lam + 1)
              false ∅ ∅ r0.1 z.1

def PSPRG.SamplingIndistinguishable (G : PSPRG) : Prop :=
  ∀ A : RestrictedDec.Adversary, A.Valid →
    NoisyOWMPC.Negligible fun lam => |((psprgSamplingGame G A lam) true).toReal - 1 / 2|

def PSPRG.AdaptivelyPseudorandom (G : PSPRG) : Prop :=
  ∀ A : RestrictedDec.Adversary, A.Valid →
    NoisyOWMPC.Negligible fun lam => |((psprgAdaptiveGame G A lam) true).toReal - 1 / 2|

/-- The complete PSPRG interface of Definition 6.1. -/
def PSPRG.IsScheme (G : PSPRG) : Prop :=
  G.Efficient ∧ G.Correct ∧ G.Compact ∧ G.SamplingIndistinguishable ∧ G.AdaptivelyPseudorandom

/-- Construction 6.2 from a bit-message PPS (p.45). The public parameters are the PPS CRS and
one encryption of an independent random bit per output position. -/
noncomputable def construction62 (E : PPS) : PSPRG where
  setup lam ell :=
    (E.gsetup lam ell).bind fun crs => (E.mskgen lam ell crs).bind fun msk =>
      (List.range ell).foldr
        (fun j acc => (PMF.uniformOfFintype Bool).bind fun b =>
          (E.skEnc lam ell crs msk (j + 1) [b]).bind fun ct => acc.map fun cts => ct :: cts)
        (PMF.pure []) |>.map fun cts => (BeyondDS.tup (crs :: cts), BeyondDS.tup [crs, msk])
  samp lam ell pp S :=
    let fs := BeyondDS.untup pp
    let crs := fs.getD 0 []
    (E.mskgen lam ell crs).bind fun msk => E.kgen lam ell crs msk S
  project lam ell pp mskCode S :=
    let fs := BeyondDS.untup mskCode
    E.kgen lam ell (fs.getD 0 []) (fs.getD 1 []) S
  eval lam ell pp S sk i :=
    if i ∈ S then
      let fs := BeyondDS.untup pp
      (E.decode lam ell (fs.getD 0 []) S sk i (fs.getD i [])).bind List.head?
    else none

end PPSLattice.Supplement
Source
Goyal–Yadugiri, STOC 2027 submission (manuscript sha256 7f9c493f…), Definition 6.1 and Construction 6.2, pp.43–45

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me