一类带辅助输入椭圆曲线离散对数问题安全性分析研究

This project mainly focuses on how to solve the elliptic curve discrete logarithm problem with auxiliary inputs. Under the condition that the auxiliary information is known, the related theoretical knowledge of group theory and algebraic geometry is used to give a new solution method for this kind of problem. Through the study of the deep hierarchical algebra structure of the elliptic curve discrete logarithmic group, we investigate that auxiliary information gives new changes of solving the elliptic curve discrete logarithm problem. We construct a special group corresponding to different auxiliary information, and act it on the elliptic curve discrete logarithm group. We analyze the internal relationship among the orbits formed by the elements in the discrete logarithmic group of the elliptic curve. Therefore, a breakthrough is found to solve the elliptic curve discrete logarithm problem with the condition of known auxiliary information. The research results of this project will provide theoretical and practical support for the selection of the security parameters of the cryptographic scheme designing with the difficulty of the elliptic curve discrete logarithm with auxiliary inputs.

本项目主要研究一类带辅助输入的椭圆曲线离散对数问题如何求解，在已知辅助信息的条件下，采用群论和代数几何的相关理论知识给出该类问题新的求解方法。通过对椭圆曲线离散对数群深层次代数结构的研究，深入分析辅助信息给椭圆曲线离散对数问题求解带来的新变化。我们针对不同的辅助信息相应的构造一个特殊的群，将该群作用到椭圆曲线离散对数群上，分析作用后椭圆曲线离散对数群中元素形成的轨道之间的内部关系，从而为求解已知辅助信息条件下椭圆曲线离散对数问题找到突破口。本项目的研究成果将为以带辅助输入椭圆曲线离散对数问题困难性设计的密码方案安全参数选取提供理论和实际的依据。

当前密码学界对经典椭圆曲线离散对数问题 (Elliptic Curve Discrete Logarithm Problem，ECDLP)研究进展比较缓慢，而ECDLP的变形带辅助输入椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem with Auxiliary Inputs，ECDLP-wAI)已经作为新的困难性假设被广泛应用于许多密码方案的设计之中，项目对ECDLP-wAI的求解进行了相关的研究。.利用群论和代数几何的相关理论知识给出椭圆曲线离散对数群新的表示方法，通过对椭圆曲线离散对数群深层次代数结构的研究，给出群元素一种新的表达方式，使得在该表达方式下群中的元素可以有规则的表示出来，引入群在集合上作用的理论方法，进而给出群作用下轨道的划分。进一步我们分别对非连续型和离散型ECDLP-wAI进行了求解研究。通过实验验证了ECDLP-wAI求解算法的正确性。.我们的研究结果表明，基于ECDLP-wAI问题是不能像基于ECDLP困难问题一样设计密码方案的。我们已经发现2种类型的ECDLP-wAI是不能被作为密码方案安全性假设。对于众多的带辅助输入类型的椭圆曲线离散对数问题，除已经被我们发现的2种类型外，目前对众多类型带辅助输入椭圆曲线离散对数问题的安全性分析还需继续研究。.本项目研究成果一方面为基于ECDLP-wAI设计的密码方案安全参数选取提供理论，另一方面在ECDLP 求解进展缓慢的情形下，我们给出的两类ECDLP-wAI求解算法目前看来可能是ECDLP一个新的突破方向。这些研究工作将为基于带辅助输入的密码方案参数选取提供有力的理论依据。.在本项目的资助下，发表学术论文9篇，申请专利1项。培养网络空间安全研究生4名，博士生2名。