AMC
Discrete logarithm like problems and linear recurring sequences
Santos González Llorenç Huguet Consuelo Martínez Hugo Villafañe
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.
keywords: hardness assumptions. public key cryptography Discrete logarithm problem linear recurring sequences Diffie Hellman problem compact representation

Year of publication

Related Authors

Related Keywords

[Back to Top]