椭圆曲线离散对数问题的覆盖攻击

The discrete logarithm problem in elliptic curves has important applications in cryptosystems based on discrete logarithms. The assumption that this problem is hard underpins the security of various protocols. Recent progress attacking the discrete logarithm problem in elliptic curves over non-prime fields inspires strong motivation for big breakthroughs. This project focuses on cover attacks on the discrete logarithm problem in elliptic curves. This class of attacks is a method to transform the problem into the discrete logarithm problems in the Jacobians of some curves which can be solved faster. We will develop methods of constructing the coverings which will in turn give some new attacks. We will also give a method to compute isogenies on the Jacobians of genus three curves, by which we hope to transform the discrete logarithm problem in the Jacobians of hyperelliptic curves into the discrete logarithm problems in the Jacobians of non-hyperelliptic curves which can be solved with lower complexity. Besides, we will explore new algorithms for solving the discrete logarithm problem in the Jacobians of non-hyperelliptic curves.

椭圆曲线离散对数问题在基于离散对数的密码体制中有重要的应用，许多协议的安全性都基于它的困难性。近年来关于非素域有限域上椭圆曲线离散对数问题的一系列进展激发了在该问题上取得更大突破的研究动力。本项目研究椭圆曲线离散对数问题的覆盖攻击，覆盖攻击旨在通过将椭圆曲线离散对数问题转化至其覆盖曲线的雅可比群来降低求解的复杂度。我们将研究覆盖曲线及映射的构造方法，进而给出新的覆盖攻击方法。我们还将研究亏格3曲线的雅可比簇间同源的计算，利用同源将离散对数问题从超椭圆覆盖曲线的雅可比群转化至非超椭圆曲线雅可比群，以此进一步降低计算的复杂度。此外，我们将探索求解非超椭圆曲线离散对数问题的新算法。

本项目研究扩域上椭圆曲线离散对数问题的覆盖攻击。覆盖攻击分为两个步骤：首先是构造椭圆曲线的一个覆盖，其中覆盖曲线定义在基域上。由相应的覆盖映射可实现椭圆曲线离散对数问题至覆盖曲线的雅可比簇上离散对数问题的转化。然后对后者应用指标计算等快速求解算法。我们的主要研究内容是覆盖的构造和覆盖曲线的雅可比簇上离散对数问题的解法。在覆盖映射的构造方面，我们给出了某些二次扩域上素数阶椭圆曲线的二次覆盖映射的构造方法，其应用包括构造有限域上雅可比群阶是大素数的亏格2曲线、实现某些四次扩域上素数阶椭圆曲线的离散对数问题的覆盖-分解攻击。对覆盖曲线是亏格3的超椭圆曲线情形，我们给出了其雅可比簇到非超椭圆曲线雅可比簇的(l,l,l)-同源计算方法，利用这样的同源可实现离散对数问题的转化，降低了解离散对数问题的时间复杂度。我们还利用非交互的双密钥封装机制的框架，构造了在随机谕言模型下安全的基于超奇异同源的认证密钥交换协议。