椭圆曲线密码分析技术研究

The elliptic curve cryptography (ECC), as a mature cryptosystem, and its application has been widely used. With the development of the quantum algorithms, the security of ECC has always been concerned. The elliptic curve discrete logarithm problem (ECDLP) lies at the heart of almost all elliptic curve cryptography and pairing-based cryptography. To solve ECDLP, researchers continuously proposed new algorithms and improved variants, and the ECC challenge records were broken constantly. ..This project will study a number of ECDLP computation problems penetrate deeply, including: (1) make use of the elliptic curve group structures and the features of the point operations, to design more efficient algorithms for ECDLP computation; (2) design efficient algorithm to solve the multi-elliptic curve discrete logarithm problem, and analysis its computational complexity; (3) based on the quantum algorithm of ECDLP, explore efficient quantum algorithms for elliptic curve isogeny and design quantum algorithms for certain NPC problems. This project will address a number of important issues mentioned above on ECDLP computations, so as to evaluate the security level of current ECC commercial standards more precisely, to explore new more efficient algorithms to solve ECDLP.

椭圆曲线密码(ECC)作为一种成熟的密码体制，有着广泛的应用。其安全性一直是业界关注的重点，特别是量子计算不断发展的情况下。椭圆曲线离散对数问题(ECDLP)是椭圆曲线密码系统和双线性对密码系统的核心。研究者们围绕ECDLP不断提出新的以及改进算法，持续刷新ECC破解记录。..本项目将针对ECDLP计算中的多个问题展开深入研究，具体包括：(1) 利用椭圆曲线上群结构及点的运算特性，设计更加有效的ECDLP求解算法；(2) 针对多椭圆曲线离散对数问题，设计有效的求解算法，并分析其计算复杂度；(3) 基于ECDLP量子算法，探索椭圆曲线同种(isogeny)问题有效量子算法以及部分NPC问题量子算法。本项目的研究将解决上述ECDLP计算中的多个重要问题，从而更好的评估现有ECC商业标准的安全性，为设计更加有效的ECDLP求解算法做积极探索。

椭圆曲线密码(ECC)是当前应用非常广泛的一种密码系统，在量子计算不断有新的进展情况下，ECC安全性备受瞩目，不仅学术界和工业界，还包括政府部门。椭圆曲线离散对数问题(ECDLP)是椭圆曲线密码系统和双线性对密码系统的关键理论基础。在量子计算逐渐发展的情况下，为了有效评估椭圆曲线密码的安全性，本项目重点研究了ECDLP可能存在的改进算法，以及当前量子算法对ECDLP的影响。.具体地，本项目研究内容主要包括如下几方面：(1) 利用椭圆曲线上群结构及点的运算特性，基于经典的小步大步算法，我们设计更加有效改进算法，相较于原来的算法，改进算法效率提高约40%，相关成果为发表在AMC上的论文：“Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm”；(2) 针对多椭圆曲线离散对数问题，我们设计了更加有效的并行求解算法，并分析了计算复杂度，相关论文为：“On Solving Multiple Elliptic Curve Discrete Logarithm Problems”；(3) 基于ECDLP量子算法，我们评估了量子算法对现有ECC的影响，根据破解ECDLP需要的量子比特规模和量子门电路的数量，我们估计在未来若干年内ECC还是可用的。同时我们也探索了子集和问题，格问题，以及椭圆曲线同种(isogeny)问题有效量子算法。基于量子算法，我们尝试设计了几个量子密码方案，相关论文包括：“Multi-party quantum key agreement protocol secure against collusion attacks”，“A New Lattice Sieving Algorithm Base On Angular Locality-sensitive Hashing”等。.本项目的研究解决了上述ECDLP相关计算中的若干重要问题，能更好的评估现有ECC商业标准的安全性，积极探索了设计更加有效的ECDLP求解算法。