量子科技中心_量科网

该研究团队提出Eidolon——一种基于NP完全问题k-可着色性（k≥3）的实用后量子签名方案。该工作将Goldreich-Micali-Wigderson零知识协议推广至任意k≥3情形，应用Fiat-Shamir变换，并采用Merkle树承诺技术将签名规模从O(tn)压缩至O(t log n)。关键创新在于通过植入"静默"着色方案生成困难实例，这些着色能保持随机图的统计特性。研究人员首次对此类方案进行了针对经典求解器（整数线性规划ILP、DSatur算法）和定制图神经网络（GNN）攻击者的实证安全分析。实验表明，当n≥60时，两类方法均无法还原秘密着色方案，证明精心设计的k-着色实例能抵抗包括机器学习在内的现代密码分析。这标志着组合数学硬度问题作为后量子签名可信基础的理论复兴。