Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

公开可恢复的 Waters 记录:统一常数的 CDH 伪造归约

Open
CritWinSpin.source_waters_cdh

by Maxliu · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographyp2o-gran-per-chapterspin-systems

存在一个独立于双线性群族、验证电路、对手和样本数的常数 C>0C>0C>0,使下述归约成立。设 Waters 验证电路具有公开的多项式时间求值及签名恢复函数,保留消息位,并且诚实生成记录的分布恰为有效记录集上的均匀分布。

对每个概率多项式时间算法 AAA,每个可有效计算的多项式样本数 T(d)≥1T(d)\ge1T(d)≥1,都存在概率多项式时间算法 BBB,使所有充分大的 ddd 满足

Pr⁡{A(P,F1:T)=F∗∈ΩP, ΨP(F∗)∉{ΨP(Ft)}t=1T}≤C T(d)d AdvCDH(B;d).\Pr\{A(P,F_{1:T})=F_*\in\Omega_P,\ \Psi_P(F_*)\notin\{\Psi_P(F_t)\}_{t=1}^T\} \le C\,T(d)\sqrt d\,\mathrm{Adv}_{\rm CDH}(B;d).Pr{A(P,F1:T​)=F∗​∈ΩP​, ΨP​(F∗​)∈/{ΨP​(Ft​)}t=1T​}≤CT(d)d​AdvCDH​(B;d).

左侧概率包括随机群参数、公钥、均匀训练记录和对手随机性。该结论为带损失的算法归约,无须先假定 CDH 困难。高效恢复函数保证有效新记录可转为原 Waters 实验中的新消息签名。

已退役:保留原先草图,后续沿 CritWinSpin.p7b_5_1_waters_embedding 继续证明。

Preamble
import Mathlib
import Definitions.Def_CritWinSpin_SourceReduction
open QAlgorithms.Complexity QuantumPRC OWFLocalDesc IsingLTL.BeliefProp
open scoped BigOperators
set_option autoImplicit false
Formal statement
namespace CritWinSpin
theorem source_waters_cdh :
    ∃ C : ℝ, 0 < C ∧ ∀ (F : BilinearFamily) (circ : WatersCircuit F),
      SourceCircuitRecords circ →
      (∀ d, 1 ≤ d → ∀ desc, GenSupport F.gen d desc → ∀ (key : WatersKey F desc d)
        (y : BinCfg (circ.n0 d)), circ.genLaw d desc key y = unifOn (circ.omega d desc key) y) →
      SourceSecurity F circ.toSource C := by sorry
end CritWinSpin
Source
Liu, Zhang, Ren, The Critical Window for Sampling and Learning-to-Sample in Spin Systems, STOC 2027 submission, manuscript SHA256 f77584dab87d9e6d0936a083a2e3d26476a91a9d73dc303674514a3257c0de95; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/943.pdf; Theorem 5.1(iii), printed p.19, equation (27), proof printed p.20, invoking HJK12 Theorem 2.3 and RV26 Theorem 47.

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