公开可恢复的 Waters 记录:统一常数的 CDH 伪造归约
OpenCritWinSpin.source_waters_cdhcryptographyp2o-gran-per-chapterspin-systems
存在一个独立于双线性群族、验证电路、对手和样本数的常数 ,使下述归约成立。设 Waters 验证电路具有公开的多项式时间求值及签名恢复函数,保留消息位,并且诚实生成记录的分布恰为有效记录集上的均匀分布。
对每个概率多项式时间算法 ,每个可有效计算的多项式样本数 ,都存在概率多项式时间算法 ,使所有充分大的 满足
左侧概率包括随机群参数、公钥、均匀训练记录和对手随机性。该结论为带损失的算法归约,无须先假定 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 CritWinSpinSource
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.