小特征有限域离散对数问题研究及其在密码学中的意义

Discrete logarithm problem over finite fields has important applications in cryptography. The hardness of this problem underpins the security of many cryptography protocols. Recently, a series of improvements have been made to solve this problem over small characteristic finite fields, which inspire possibilities of further breakthroughs. This research aims at finding innovative ideas and methods of solving discrete logarithms over small characteristic finite fields and analyzing applications in cryptography. We will optimize and improve known algorithms, focusing on removing some heuristic assumptions and speeding up the algorithm in practice. We will also design new algorithms with lower time complexity. Besides, we will apply these results to solve related problems and analyze their effects on certain cryptosystems.

有限域离散对数问题在密码学中有重要的应用，许多密码协议的安全性是基于该问题的困难性假设。近年来关于小特征有限域离散对数问题的一系列进展激发了求解该问题取得更大突破的可能性。本课题旨在研究求解小特征有限域离散对数问题的新思想、新方法及其在密码学中的意义。我们将对已知的求解小特征有限域离散对数的算法进行优化和改进，侧重于减少所使用的启发式的假设，提高运行效率。我们还将设计求解该问题的时间复杂度更低的新算法。此外，我们将应用这些算法求解相关问题，以及分析这些结果对相关密码体制的影响。

现代密码学方案的安全性是建立在一些计算困难问题之上的，其中离散对数问题是被广泛采用的困难问题之一。本项目主要研究了小特征有限域离散对数问题求解，以及相关的不同版本的离散对数问题和深洞问题的求解。本项目的主要结果包括：（1）设计了一个时间复杂度最优的求解一类陪集代表元的算法，可以应用于加速BGJT算法；（2）改进了 Kummer 扩域分解基离散对数的求解算法，是一个设计确定型算法的尝试；（3）改进了 Galbraith-Ruprai 求解区间离散对数问题的算法，影响实际参数的选取；（4）研究了特征 p 椭圆曲线上p-群的离散对数问题，使用了提升的方法；（5）解决了部分 Reed-Solomon 码深洞的刻画。

内容获取失败，请点击重试