Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Q-bounded robust PPS and Construction A.5

Definition
PPSLattice_Supplement_QBoundedRPPS

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

cryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1secret-sharing

A QQQ-bounded robust PPS exposes unary QQQ at setup, allows at most QQQ set-key queries, and permits ciphertext size to depend polynomially on QQQ. Construction A.5 is the explicit QRQRQR-instance PPS construction with independent Shamir sharing in every bucket; it has public parameters and ciphertexts linear in QQQ, compact keys, and decoder locality independent of QQQ, with R=λ2(λ+1)2R=\lambda^2(\lambda+1)^2R=λ2(λ+1)2, threshold λ+1\lambda+1λ+1, and field width ⌈log⁡2(R+1)⌉\lceil\log_2(R+1)\rceil⌈log2​(R+1)⌉.

Definition code
import Mathlib
import Definitions.Def_BeyondDS_tup
import Definitions.Def_NoisyOWMPC_Negligible
import Definitions.Def_PPSLattice_PPS_Efficient
import Definitions.Def_PPSLattice_Supplement_RPPS
import Definitions.Def_PPSLattice_Supplement_EvolvingCSS
import Definitions.Def_PPSLattice_decBin
import Definitions.Def_PPSLattice_decSet
import Definitions.Def_PPSLattice_encSet
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 Q-bounded robust PPS, whose setup also receives `Q` (Definition A.1, p.66). -/
structure QBoundedRPPS where
  setup : ℕ → ℕ → ℕ → PMF (Str × Str)
  pkEnc : ℕ → ℕ → ℕ → Str → ℕ → PMF Str
  kgen : ℕ → ℕ → ℕ → Str → Str → Finset ℕ → PMF Str
  skEnc : ℕ → ℕ → ℕ → Str → Str → ℕ → Str → PMF Str
  decode : ℕ → ℕ → ℕ → Str → Finset ℕ → Str → ℕ → Str → Option Str

/-- Uniform polynomial-time syntax for Q-bounded robust PPS. `N` is binary and `Q` is unary. -/
def QBoundedRPPS.Efficient (E : QBoundedRPPS) : Prop :=
  PPTSampler (fun x : ℕ × ℕ × ℕ => BeyondDS.tup [encNat x.1, encBin x.2.1, encNat x.2.2])
    (fun x => (E.setup x.1 x.2.1 x.2.2).map fun z => BeyondDS.tup [z.1, z.2]) ∧
  PPTSampler (fun x : ℕ × ℕ × ℕ × Str × ℕ =>
      BeyondDS.tup [encNat x.1, encBin x.2.1, encNat x.2.2.1, x.2.2.2.1,
        encBin x.2.2.2.2])
    (fun x => E.pkEnc x.1 x.2.1 x.2.2.1 x.2.2.2.1 x.2.2.2.2) ∧
  PPTSampler (fun x : ℕ × ℕ × ℕ × Str × Str × Finset ℕ =>
      BeyondDS.tup [encNat x.1, encBin x.2.1, encNat x.2.2.1, x.2.2.2.1,
        x.2.2.2.2.1, encSet x.2.2.2.2.2])
    (fun x => E.kgen 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) ∧
  PPTSampler (fun x : ℕ × ℕ × ℕ × Str × Str × ℕ × Str =>
      BeyondDS.tup [encNat x.1, encBin x.2.1, encNat x.2.2.1, x.2.2.2.1,
        x.2.2.2.2.1, encBin x.2.2.2.2.2.1, x.2.2.2.2.2.2])
    (fun x => E.skEnc 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.1 x.2.2.2.2.2.2) ∧
  PolyTimeOn (fun x : ℕ × ℕ × ℕ × Str × Finset ℕ × Str × ℕ × Str =>
      BeyondDS.tup [encNat x.1, encBin x.2.1, encNat x.2.2.1, x.2.2.2.1,
        encSet x.2.2.2.2.1, x.2.2.2.2.2.1, encBin x.2.2.2.2.2.2.1,
        x.2.2.2.2.2.2.2])
    (fun x => match E.decode 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.1 x.2.2.2.2.2.2.1 x.2.2.2.2.2.2.2 with
      | none => [] | some mu => mu)

def appendixR (lam : ℕ) : ℕ := lam ^ 2 * (lam + 1) ^ 2
def appendixH (lam : ℕ) : ℕ := Nat.clog 2 (appendixR lam + 1)
def AppendixFieldMessage (lam : ℕ) : Set Str := {m | m.length = appendixH lam}
/-- The source's canonical embeddings of field elements `0` and `1` into the `h`-bit model. -/
def appendixBit (lam : ℕ) (b : Bool) : Str :=
  (List.range (appendixH lam)).map fun j => b && decide (j = 0)

/-- PPS correctness for an arbitrary explicitly supplied string message family. -/
def PPS.CorrectFor (E : PPS) (Message : ℕ → Set Str) : Prop :=
  ∀ lam N : ℕ, 1 ≤ lam → N ≤ 2 ^ lam → ∀ S ⊆ Finset.Icc 1 N, ∀ i ∈ S,
    ∀ mu ∈ Message lam, ((E.gsetup lam N).bind fun crs => (E.mskgen lam N crs).bind fun msk =>
      (E.skEnc lam N crs msk i mu).bind fun ct => (E.kgen lam N crs msk S).map fun sk =>
        decide (E.decode lam N crs S sk i ct = some mu)) true = 1

/-- Full PPS compactness for an arbitrary message family. -/
def PPS.FullyCompactFor (E : PPS) (Message : ℕ → Set Str) : Prop :=
  ∃ c : ℕ, ∀ lam N : ℕ, 1 ≤ lam → 1 ≤ N → N ≤ 2 ^ lam →
    ∀ crs ∈ (E.gsetup lam N).support, crs.length ≤ (lam + Nat.clog 2 N + 2) ^ c ∧
      ∀ msk ∈ (E.mskgen lam N crs).support,
        (∀ i ∈ Finset.Icc 1 N, ∀ ct ∈ (E.pkEnc lam N crs i).support,
          ct.length ≤ (lam + Nat.clog 2 N + 2) ^ c) ∧
        (∀ i ∈ Finset.Icc 1 N, ∀ mu ∈ Message lam,
          ∀ ct ∈ (E.skEnc lam N crs msk i mu).support,
            ct.length ≤ (lam + Nat.clog 2 N + 2) ^ c) ∧
        ∀ S ⊆ Finset.Icc 1 N, ∀ sk ∈ (E.kgen lam N crs msk S).support,
          sk.length ≤ (lam + Nat.clog 2 N + 2) ^ c

def PPS.IsSchemeForPostKey (E : PPS) (Message : ℕ → Set Str) : Prop :=
  E.Efficient ∧ PPSLattice.Supplement.PPS.CorrectFor E Message ∧
    PPSLattice.Supplement.PPS.FullyCompactFor E Message ∧
    PPSLattice.Supplement.PPS.PostKeyPayloadHiding E Message

def QBoundedRPPS.Correct (E : QBoundedRPPS) (Message : ℕ → Set Str) : Prop :=
  ∃ nu : ℕ → ℝ, NoisyOWMPC.Negligible nu ∧ ∀ lam N Q : ℕ,
    1 ≤ lam → 1 ≤ Q → N ≤ 2 ^ lam →
    ∀ S ⊆ Finset.Icc 1 N, ∀ i ∈ S, ∀ mu ∈ Message lam,
      1 - nu lam ≤ (((E.setup lam N Q).bind fun z =>
        (E.kgen lam N Q z.1 z.2 S).bind fun sk =>
          (E.skEnc lam N Q z.1 z.2 i mu).map fun ct =>
            decide (E.decode lam N Q z.1 S sk i ct = some mu)) true).toReal

/-- Definition A.1 compactness: keys remain `poly(λ,log N)`, while ciphertexts may grow by an
arbitrary polynomial in the unary setup bound `Q`. Public-parameter size is not part of
Definition 6.14 compactness and is recorded separately for Construction A.5. -/
def QBoundedRPPS.Compact (E : QBoundedRPPS) (Message : ℕ → Set Str) : Prop :=
  ∃ c : ℕ, ∀ lam N Q : ℕ, 1 ≤ lam → 1 ≤ N → N ≤ 2 ^ lam →
    1 ≤ Q → ∀ z ∈ (E.setup lam N Q).support,
      (∀ S ⊆ Finset.Icc 1 N, ∀ sk ∈ (E.kgen lam N Q z.1 z.2 S).support,
        sk.length ≤ (lam + Nat.clog 2 N + Nat.clog 2 Q + 3) ^ c) ∧
      (∀ i ∈ Finset.Icc 1 N, ∀ ct ∈ (E.pkEnc lam N Q z.1 i).support,
        ct.length ≤ (lam + Nat.clog 2 N + Q + 3) ^ c) ∧
      ∀ i ∈ Finset.Icc 1 N, ∀ mu ∈ Message lam,
        ∀ ct ∈ (E.skEnc lam N Q z.1 z.2 i mu).support,
          ct.length ≤ (lam + Nat.clog 2 N + Q + 3) ^ c

open Classical in
/-- Bounded-adaptive-robustness interaction, counting KGen queries while allowing arbitrary
interleaving with encryption queries. -/
noncomputable def qbrppsRun (E : QBoundedRPPS) (Message : ℕ → Set Str)
    (A : RestrictedDec.Adversary) (lam N Q : ℕ) (pp msk : Str) (istar : ℕ) (b : Bool) :
    ℕ → ℕ → Str → Str → PMF Bool
  | 0, _, _, _ => PMF.uniformOfFintype Bool
  | fuel + 1, keyCount, st, input => (A.activate lam st input).bind fun r =>
      match decRPPSMove r.2 with
      | .enc i mu =>
          if i ∈ Finset.Icc 1 N ∧ i ≠ istar ∧ mu ∈ Message lam then
            (E.skEnc lam N Q pp msk i mu).bind fun ct =>
              qbrppsRun E Message A lam N Q pp msk istar b fuel keyCount r.1 ct
          else qbrppsRun E Message A lam N Q pp msk istar b fuel keyCount r.1 []
      | .key S =>
          if keyCount < Q ∧ S ⊆ Finset.Icc 1 N ∧ istar ∉ S then
            (E.kgen lam N Q pp msk S).bind fun sk =>
              qbrppsRun E Message A lam N Q pp msk istar b fuel (keyCount + 1) r.1 sk
          else PMF.uniformOfFintype Bool
      | .guess b' => PMF.pure (decide (b' = b))

open Classical in
/-- The adversary chooses `(N,Q,i*,μ0,μ1)` before setup; the challenge is always a secret-key
encryption of `μ_b`, as in Definition A.1. -/
noncomputable def qbrppsGame (E : QBoundedRPPS) (Message : ℕ → Set Str)
    (A : RestrictedDec.Adversary) (lam : ℕ) : PMF Bool :=
  (A.activate lam [] []).bind fun r0 =>
    let fs := BeyondDS.untup r0.2
    let N := decBin (fs.getD 0 [])
    let Q := BeyondDS.decNat (fs.getD 1 [])
    let istar := decBin (fs.getD 2 [])
    let mu0 := fs.getD 3 []
    let mu1 := fs.getD 4 []
    if 1 ≤ Q ∧ istar ∈ Finset.Icc 1 N ∧ mu0 ∈ Message lam ∧ mu1 ∈ Message lam then
      (PMF.uniformOfFintype Bool).bind fun b => (E.setup lam N Q).bind fun z =>
        (E.skEnc lam N Q z.1 z.2 istar (if b then mu1 else mu0)).bind fun ct =>
          qbrppsRun E Message A lam N Q z.1 z.2 istar b (A.p.eval lam + 1) 0 r0.1
            (BeyondDS.tup [z.1, ct])
    else PMF.uniformOfFintype Bool

def QBoundedRPPS.BoundedAdaptiveRobust (E : QBoundedRPPS) (Message : ℕ → Set Str) : Prop :=
  ∀ A : RestrictedDec.Adversary, A.Valid →
    NoisyOWMPC.Negligible fun lam => |((qbrppsGame E Message A lam) true).toReal - 1 / 2|

/-- Locality of Construction A.5: Decode reads no public-parameter bits and at most a polynomial
in `(λ,log N)` ciphertext bits, independently of `Q` and `|S|`. The two natural-valued functions
are an explicit random-access cost certificate for the deterministic decoder. -/
def QBoundedRPPS.Local (readPP readCT : ℕ → ℕ → ℕ → ℕ) : Prop :=
  (∀ lam N Q, readPP lam N Q = 0) ∧
  ∃ c : ℕ, ∀ lam N Q, readCT lam N Q ≤ (lam + Nat.clog 2 N + 2) ^ c

/-- A finite-field Shamir interface at the Appendix-A parameters. Field elements are their exact
`h`-bit encodings. -/
structure ShamirFamily where
  share : ℕ → Str → PMF (List Str)
  recon : ℕ → Finset ℕ → List Str → Option Str

private def selectedShares (Gamma : Finset ℕ) (shares : List Str) : List Str :=
  (Gamma.sort (· ≤ ·)).map fun r => shares.getD (r - 1) []

/-- The correctness, perfect privacy, field-width, and polynomial-time properties of the Shamir
scheme invoked in Lemma A.2. -/
def ShamirFamily.Valid (H : ShamirFamily) : Prop :=
  PPTSampler (fun x : ℕ × Str => BeyondDS.tup [encNat x.1, x.2])
      (fun x => (H.share x.1 x.2).map BeyondDS.tup) ∧
  PolyTimeOn (fun x : ℕ × Finset ℕ × List Str =>
      BeyondDS.tup [encNat x.1, encSet x.2.1, BeyondDS.tup x.2.2])
      (fun x => (H.recon x.1 x.2.1 x.2.2).getD []) ∧
  (∀ lam mu, 1 ≤ lam → mu ∈ AppendixFieldMessage lam →
    ∀ shares ∈ (H.share lam mu).support,
      shares.length = appendixR lam ∧ ∀ y ∈ shares, y ∈ AppendixFieldMessage lam) ∧
  (∀ lam mu, 1 ≤ lam → mu ∈ AppendixFieldMessage lam →
    ∀ Gamma ⊆ Finset.Icc 1 (appendixR lam), lam + 1 ≤ Gamma.card →
      ∀ shares ∈ (H.share lam mu).support,
        H.recon lam Gamma (selectedShares Gamma shares) = some mu) ∧
  ∀ lam mu0 mu1, 1 ≤ lam → mu0 ∈ AppendixFieldMessage lam →
    mu1 ∈ AppendixFieldMessage lam → ∀ Gamma ⊆ Finset.Icc 1 (appendixR lam),
      Gamma.card < lam + 1 →
      (H.share lam mu0).map (selectedShares Gamma) =
        (H.share lam mu1).map (selectedShares Gamma)

private noncomputable def sampleN {α : Type} : (n : ℕ) → (ℕ → PMF α) → PMF (List α)
  | 0, _ => PMF.pure []
  | n + 1, D => (D 0).bind fun a =>
      (sampleN n fun j => D (j + 1)).map fun as => a :: as

private noncomputable def uniformFinsetOrDefault {α : Type} [DecidableEq α] [Inhabited α]
    (s : Finset α) : PMF α :=
  if h : s.Nonempty then PMF.uniformOfFinset s h else PMF.pure default

private def a5At (xs : List Str) (R k r : ℕ) : Str :=
  xs.getD ((k - 1) * R + (r - 1)) []

private def sequenceOptions {α : Type} : List (Option α) → Option (List α)
  | [] => some []
  | none :: _ => none
  | some a :: rest => (sequenceOptions rest).map fun as => a :: as

open Classical in
/-- The actual algorithms of Construction A.5. There are exactly `Q*R` independent PPS
instances; keys choose a uniform bucket and a uniform `(λ+1)`-subset, and secret-key encryption
Shamir-shares the message independently in every bucket. -/
noncomputable def constructionA5 (E : PPS) (H : ShamirFamily) : QBoundedRPPS where
  setup lam N Q :=
    (sampleN (Q * appendixR lam) fun _ =>
      (E.gsetup lam N).bind fun crs => (E.mskgen lam N crs).map fun msk => (crs, msk)).map
        fun zs => (BeyondDS.tup (zs.map Prod.fst), BeyondDS.tup (zs.map Prod.snd))
  pkEnc lam N Q pp i :=
    let crss := BeyondDS.untup pp
    (sampleN (Q * appendixR lam) fun j => E.pkEnc lam N (crss.getD j []) i).map BeyondDS.tup
  kgen lam N Q pp mskCode S :=
    let R := appendixR lam
    let crss := BeyondDS.untup pp
    let msks := BeyondDS.untup mskCode
    (uniformFinsetOrDefault (Finset.Icc 1 Q)).bind fun k =>
      (uniformFinsetOrDefault ((Finset.Icc 1 R).powersetCard (lam + 1))).bind fun Gamma =>
        let rs := Gamma.sort (· ≤ ·)
        (sampleN rs.length fun j =>
          let r := rs.getD j 0
          let crs := a5At crss R k r
          (E.kgen lam N crs (a5At msks R k r) S).map fun sk => BeyondDS.tup [crs, sk]).map
            fun pairs => BeyondDS.tup [encBin k, encSet Gamma, BeyondDS.tup pairs]
  skEnc lam N Q pp mskCode i mu :=
    let R := appendixR lam
    let crss := BeyondDS.untup pp
    let msks := BeyondDS.untup mskCode
    (sampleN Q fun k0 => (H.share lam mu).bind fun shares =>
      (sampleN R fun r0 =>
        E.skEnc lam N (a5At crss R (k0 + 1) (r0 + 1))
          (a5At msks R (k0 + 1) (r0 + 1)) i (shares.getD r0 []))).map
      fun buckets => BeyondDS.tup buckets.flatten
  decode lam N _ _ S skCode i ctCode :=
    if i ∈ S then
      let fs := BeyondDS.untup skCode
      let k := decBin (fs.getD 0 [])
      let Gamma := decSet (fs.getD 1 [])
      let pairs := BeyondDS.untup (fs.getD 2 [])
      let cts := BeyondDS.untup ctCode
      let R := appendixR lam
      let ys := (Gamma.sort (· ≤ ·)).mapIdx fun j r =>
        let pair := BeyondDS.untup (pairs.getD j [])
        E.decode lam N (pair.getD 0 []) S (pair.getD 1 []) i (a5At cts R k r)
      (sequenceOptions ys).bind fun shares => H.recon lam Gamma shares
    else none

/-- The exact linear public-parameter and ciphertext bounds proved for Construction A.5. -/
def QBoundedRPPS.ConstructionA5Linear (E : QBoundedRPPS)
    (Message : ℕ → Set Str) : Prop :=
  ∃ c : ℕ, ∀ lam N Q : ℕ, 1 ≤ lam → 1 ≤ N → N ≤ 2 ^ lam → 1 ≤ Q →
    ∀ z ∈ (E.setup lam N Q).support,
      z.1.length ≤ Q * (lam + Nat.clog 2 N + 2) ^ c ∧
      (∀ i ∈ Finset.Icc 1 N, ∀ ct ∈ (E.pkEnc lam N Q z.1 i).support,
        ct.length ≤ Q * (lam + Nat.clog 2 N + 2) ^ c) ∧
      ∀ i ∈ Finset.Icc 1 N, ∀ mu ∈ Message lam,
        ∀ ct ∈ (E.skEnc lam N Q z.1 z.2 i mu).support,
          ct.length ≤ Q * (lam + Nat.clog 2 N + 2) ^ c

/-- The exact Construction-A.5 object, tied definitionally to the algorithms above, together with
the correctness, compactness, linear-size, efficiency, and random-access locality conclusions
proved on pp.67--68. -/
structure ConstructionA5 (E : PPS) where
  shamir : ShamirFamily
  shamir_valid : shamir.Valid
  scheme : QBoundedRPPS
  scheme_eq : scheme = constructionA5 E shamir
  readPP : ℕ → ℕ → ℕ → ℕ
  readCT : ℕ → ℕ → ℕ → ℕ
  efficient : scheme.Efficient
  correct : PPSLattice.Supplement.QBoundedRPPS.Correct scheme AppendixFieldMessage
  compact : PPSLattice.Supplement.QBoundedRPPS.Compact scheme AppendixFieldMessage
  linear : PPSLattice.Supplement.QBoundedRPPS.ConstructionA5Linear scheme AppendixFieldMessage
  locality : PPSLattice.Supplement.QBoundedRPPS.Local readPP readCT

open Classical in
/-- Construction 6.17 instantiated with a Q-bounded RPPS, using `N=2^λ`. By Appendix-A
locality the public share is empty; `pp` is retained only in the private dealer state and in the
secret keys produced by Construction A.5. -/
noncomputable def construction617Q (E : QBoundedRPPS) : EvolvingCSS where
  setup lam Q _ s := (E.setup lam (2 ^ lam) Q).map fun z =>
    ([], BeyondDS.tup [z.1, z.2, [s], encBin Q])
  addVertex lam Q _ t st S :=
    let fs := BeyondDS.untup st
    let pp := fs.getD 0 []
    let msk := fs.getD 1 []
    let s := (fs.getD 2 []).headD false
    (E.kgen lam (2 ^ lam) Q pp msk S).bind fun sk =>
      (E.skEnc lam (2 ^ lam) Q pp msk t (appendixBit lam s)).map fun ct =>
        (BeyondDS.tup [encBin Q, sk, ct], st)
  recon lam G A _ shares :=
    if G.ContainsEdge A then
      let p := firstEdge G A
      let vf := BeyondDS.untup (shares.getD (p.2 - 1) [])
      let uf := BeyondDS.untup (shares.getD (p.1 - 1) [])
      let Q := decBin (vf.getD 0 [])
      (E.decode lam (2 ^ lam) Q [] (G.getD (p.2 - 1) ∅) (vf.getD 1 []) p.1
        (uf.getD 2 [])).map fun mu => mu.headD false
    else none

def EvolvingCSS.NoPublicShare (C : EvolvingCSS) : Prop :=
  ∀ lam Q D s z, z ∈ (C.setup lam Q D s).support → z.1 = []

/-- With collusion bound `Q` and unbounded degree, each vertex share has size
`Q·poly(λ)` (Theorem A.11). -/
def EvolvingCSS.QLinearSharesUnboundedDegree (C : EvolvingCSS) : Prop :=
  C.EfficientWithBounds encNat encBin ∧
    ∃ c : ℕ, ∀ lam Q : ℕ, 1 ≤ lam → 1 ≤ Q → ∀ s,
      ∀ z ∈ (C.setup lam Q (2 ^ lam) s).support, ∀ t st S,
        S ⊆ Finset.Icc 1 (t - 1) → ∀ out ∈ (C.addVertex lam Q (2 ^ lam) t st S).support,
          out.1.length ≤ Q * (lam + 2) ^ c

end PPSLattice.Supplement
Source
Goyal–Yadugiri, STOC 2027 submission (manuscript sha256 7f9c493f…), Definition A.1, Construction A.5, and Definition A.8, pp.66–70

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