Discrete logarithm like problems and linear recurring sequences
Discrete logarithm like problems and linear recurring sequences
复制标题
DOI：
10.3934/amc.2013.7.187
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
S. González;Llorenç Huguet i Rotger;C. Martínez;Hugo Villafañe
中科院分区：
文献类型：
--
作者：
S. González;Llorenç Huguet i Rotger;C. Martínez;Hugo Villafañe
本文从尽可能一般的角度研究了有限域上线性递归序列中定义的某些类离散对数问题的困难性。这些问题的难解性对基于线性递归序列的公钥密码构造的安全性起着关键作用。对于任意有限域中极小多项式不可约的非平凡线性递归序列，我们定义了新的离散对数、Diffie-Hellman和判定性Diffie-Hellman问题.然后证明了这些问题在极小多项式的任意根所生成的子群中多项式等价于离散对数问题、Diffie-Hellman问题和判定Diffie-Hellman问题.
In this paper we study the hardness of some discrete logarithm like problems defined in linear recurring sequences over finite fields from a point of view as general as possible. The intractability of these problems plays a key role in the security of the class of public key cryptographic constructions based on linear recurring sequences. We define new discrete logarithm, Diffie-Hellman and decisional Diffie-Hellman problems for any nontrivial linear recurring sequence in any finite field whose minimal polynomial is irreducible. Then, we prove that these problems are polynomially equivalent to the discrete logarithm, Diffie-Hellman and decisional Diffie-Hellman problems in the subgroup generated by any root of the minimal polynomial of the sequence.