有限群上半直离散对数问题的经典计算难度研究
摘要
半直离散对数问题(SDLP)曾被提议作为后量子密码协议的基础，基于其非阿贝尔结构可抵抗量子攻击的假设。然而近期研究表明SDL在量子算法下可被高效破解，这引发了一个核心问题：SDL问题对经典攻击者是否具有优于标准离散对数问题(DLP)的计算优势？本研究通过理论分析和SageMath实验验证，发现SDL问题的经典难度高度依赖底层群结构平台。我们提出将群案例SDL问题重构为广义离散对数问题，并开发了改进的Baby-Step Giant-Step算法，其时间空间复杂度为O(√r)，其中r为底层循环结构的周期。实验结果表明：在有限域𝔽ₚ*中，SDL与DLP具有相当复杂度；在椭圆曲线E(𝔽ₚ)上，由于自同构群有界，SDL问题变得平凡；而在初等阿贝尔群𝔽ₚⁿ中，SDL问题可能比DLP更难，其复杂度取决于自同构特征值结构。这些发现表明半直积的非阿贝尔结构并不能天然保证更高的经典计算难度。
主要贡献
- 算法适配：将经典Baby-Step Giant-Step算法适配到SDL问题，获得O(√r)复杂度
- 平台依赖性证明：通过理论分析揭示SDL难度与底层群结构的强关联性
- 实验验证：在SageMath中实现算法并验证不同群平台下的性能差异
- 密码学启示：指出非阿贝尔结构本身不足以保证计算安全性，需更精细的代数结构设计
关键技术方法
- 问题重构：将SDL问题表述为广义离散对数问题
- 周期分析：利用群自同构的循环结构确定算法复杂度参数
- 特征值分析：在初等阿贝尔群案例中建立特征值分布与问题难度的关联
实验结果
| 群结构类型 | SDL问题复杂度 | 比较基准DLP复杂度 |
|---|---|---|
| 有限域𝔽ₚ* | O(√p) | O(√p) |
| 椭圆曲线E(𝔽ₚ) | O(1) (平凡) | O(√p) |
| 初等阿贝尔群𝔽ₚⁿ | O(√(pⁿ/k)) (k为特征值) | O(√(pⁿ)) |
密码学意义
本研究对后量子密码设计具有重要启示：单纯依赖非交换群结构不足以保证安全性，必须结合具体代数平台特性进行精细设计。在有限域和椭圆曲线等常见密码学平台上，SDL问题未能提供预期的额外安全增益。