Theorem A.11 — bounded-collusion evolving-graph CSS with no public share
OpenPPSLattice.Supplement.theorem_A_11cryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1secret-sharing
Under post-key-query payload hiding, Construction 6.17 instantiated with Construction A.5 is an adaptively secure evolving-graph CSS with collusion bound , unbounded degree, vertex shares, and no public share.
Differences from the source:
- reading: Definition 6.16 quantifies over graph lengths while this construction fixes the index space to → Lean makes the implicit PPT-execution bound explicit as in correctness; reason: polynomially many vertices lie in this index space asymptotically and the paper's proof uses exactly that space.
- encoding: The paper refers to the two constructions and the embeddings by name → Lean packages the exact Construction-A.5 algorithms and Shamir laws, uses canonical -bit encodings of field zero and one, and applies Construction 6.17 to that scheme; reason: the conjunction states adaptive security, Q-linear shares, and empty public share without permitting an unrelated witness.
Preamble
import Mathlib import Definitions.Def_PPSLattice_Supplement_QBoundedRPPS set_option autoImplicit false
Formal statement
namespace PPSLattice.Supplement
/-- **Theorem A.11**, Goyal--Yadugiri, STOC 2027 submission (manuscript sha256 7f9c493f...),
p.71. Under post-key-query payload hiding, Construction 6.17 instantiated with Construction A.5
is an adaptively secure evolving-graph CSS with collusion bound `Q`, unbounded degree,
`Q·poly(λ)` vertex shares, and no public share.
**Formalization Note.** The existential witness is the fully specified Construction-A.5 bundle,
not an arbitrary robust PPS. `construction617Q` is Construction 6.17 with that Q-bounded scheme;
locality is what makes its public share empty. -/
theorem theorem_A_11 (E : PPS)
(hE : PPSLattice.Supplement.PPS.IsSchemeForPostKey E AppendixFieldMessage) :
∃ C : ConstructionA5 E,
PPSLattice.Supplement.QBoundedRPPS.BoundedAdaptiveRobust C.scheme
AppendixFieldMessage ∧
(construction617Q C.scheme).IsScheme ∧
(construction617Q C.scheme).QLinearSharesUnboundedDegree ∧
(construction617Q C.scheme).NoPublicShare := by sorry
end PPSLattice.Supplement
Source
Goyal–Yadugiri, STOC 2027 submission (manuscript sha256 7f9c493f…), Theorem A.11, p.71