Bounds in Various Generalized Settings of the Discrete Logarithm Problem
Bounds in Various Generalized Settings of the Discrete Logarithm Problem
复制标题
离散对数问题的各种广义设置中的界限
DOI：
10.1007/978-3-319-61204-1_25
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Ying Jason H. M. and Kunihiro Noboru
中科院分区：
文献类型：
--
作者：
Nakamura Kengo;Sadakane Kunihiko;仲谷英夫;Ying Jason H. M. and Kunihiro Noboru
本文研究了广义多重离散对数问题的一般困难性，其中求解者必须针对离散对数问题的各种设置求解kout个实例。对于generickandn，我们引入两种技术来建立这个计算复杂度的下限。一种方法可以实现渐近紧界的小输入在经典的设置。另一种方法实现了更大输入的边界，并且能够适应其他离散对数设置中的应用。在后者中，我们得到的广义下界通过应用分区的，进一步表明，我们所选择的分区方法达到最佳的界限。本文的工作可以看作是对Yun（EUROWITPT '15）所分析的多重离散对数问题的困难性的推广和扩展。并计算出了各变量关于托卡的显式界。
This paper examines the generic hardness of the generalized multiple discrete logarithm problem, where the solver has to solvekout ofninstances for various settings of the discrete logarithm problem. For generickandn, we introduce two techniques to establish the lower bounds for this computational complexity. One method can be shown to achieve asymptotically tight bounds for small inputs in the classical setting. The other method achieves bounds for larger inputs as well as being able to adapt for applications in other discrete logarithm settings. In the latter, we obtain the generalized lower bounds by applying partitions ofnand furthermore show that our chosen method of partition achieves the best bounds. This work can be regarded as a generalization and extension on the hardness of the multiple discrete logarithm problem analyzed by Yun (EUROCRYPT ’15). Some explicit bounds for variousnwith respect tokare also computed.