该论文研究基于同源的密码学(isogeny-based cryptography)中的一个基础计算问题:在素数域 F_p 上搜索超奇异椭圆曲线。此前相关工作在 F_{p^2} 域上引入了非重数距离(NonMultiplicity Distance, NMD)目标函数,用于衡量 Frobenius 迹偏离 p 的倍数的程度,并表明无信息随机搜索在候选规模超过约 10^13 时失效。本文则将视角转向素数域 F_p,这一设置对应定向同源协议如 CSIDH、OSIDH 和 SQISign。尽管候选空间从 p^2 缩小到 p,但超奇异轨迹(supersingular locus)在渐近意义下仍然稀疏(约有 O(√p log p) 条曲线),因此搜索在指数级别上仍然困难。作者提出了一种针对 F_p 定制的模因算法(memetic algorithm),采用一维 j-不变量染色体、位级重组、自适应变异和周期性局部搜索,并以 NMD 作为优化目标。实验使用 30 个独立随机种子,在 40 位、46 位和 51 位素数(p ≈ 1.13×10^15)规模上进行基准测试,结果显示:算法在 46 位规模下能发现一条精确的超奇异曲线,并能持续收敛到 Frobenius 迹极接近零的“近超奇异”普通曲线。最佳 NMD 值在 40 位时为 19,在 51 位时为 3,对应的相对迹偏差在 Hasse 区间内分别达到 1.3×10^-5 和 4.5×10^-8。这些结果表明,NMD 驱动的模因搜索能有效导航稀疏的 F_p 搜索空间,并系统性地定位近超奇异结构。该研究的主要贡献在于:首次将模因算法应用于 F_p 域上的超奇异曲线搜索,提出了针对该问题的染色体编码与变异策略,并通过大范围实验验证了方法的有效性。适合关注后量子密码学、同源密码协议安全性分析以及数学优化算法在密码学中应用的研究人员阅读。
💡 推荐理由: 该研究直接关系 CSIDH、SQISign 等同源密码协议的安全性基础,探索了在素数域上高效搜索超奇异曲线的新方法,为评估这类协议的实际安全边界提供了新的技术视角。
🎯 建议动作: 研究跟进