Waters 电路编译:公开可逆记录及 Ising 源的统计性质
OpenCritWinSpin.source_waters_compilercryptographyp2o-gran-per-chapterspin-systems
给定任意双线性群族 ,存在一个 Waters 验证电路,其记录保留输入消息和签名,正向电路求值与从完整记录恢复消息、签名都由统一的多项式时间函数实现。诚实生成的记录对消息和签名随机数是单射,线数满足 及 。
该电路的二次惩罚 Ising 源具有对称零对角矩阵、多项式行宽,以及公开可计算的 Hamiltonian 和消息映射,并且满足
消息边缘均匀;由其余记录预测某条消息的命中率恰为 ,消息碰撞概率至多 。
这条编译引理只建立源的构造与统计部分,为密码安全归约和零场适配提供共同的实际电路。
已退役:保留原先草图,后续沿 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_compiler (F : BilinearFamily) :
∃ circ : WatersCircuit F, SourceCircuitRecords circ ∧
SourceGeometry F circ.toSource ∧ SourceEfficient F circ.toSource ∧
SourceStatistics F circ.toSource := 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; §5.1 and §5.2, printed pp.18--20, Theorem 5.1(i)--(ii), proof using RV26 Lemmas 22--23 and MMS21 Lemma 43.