Article Contents
Article Contents

# Discrete logarithm like problems and linear recurring sequences

• 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.
Mathematics Subject Classification: Primary: 11T71; Secondary: 94A55.

 Citation:

•  [1] A. Agnew, R. C. Mullin, I. M. Onyszchuk and S. A. Vanstone, An implementation for a fast public-key cryptosystem, J. Cryptology, 3 (1991), 63-79. [2] A. Brouwer, R. Pellikaan and E. Verheul, Doing more with fewer bits, in "Advances in Cryptology - ASIACRYPT'99,'' Springer-Verlag, (1999), 321-332. [3] W. Diffie and M. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, 22 (1976), 644-654. [4] C. M. Fiduccia, An efficient formula for linear recurring sequences, SIAM J. Comput., 14 (1985), 106-112. [5] J. von zur Gathen and J. Gerhard, "Modern Computer Algebra,'' Cambridge Univ. Press, Cambridge, 2003. [6] K. Giuliani and G. Gong, Analogues to the Gong-Harn and XTR cryptosystems, in "Combinatorics and Optimization Research Report,'' Univ. Waterloo, 2003. [7] K. Giuliani and G. Gong, Efficient key agreement and signature schemes using compact representations in $GF(p$10$)$, in "Proceedings of the 2004 IEEE International Symposium on Information Theory - ISIT'04,'' Chicago, (2004), 13. [8] K. Giuliani and G. Gong, New LFSR-based cryptosystems and the trace discrete logarithm problem (Trace-DLP), in "Sequences and Their Applications'04,'' Springer-Verlag, (2005), 298-312. [9] G. Gong and L. Harn, Public-key cryptosystems based on cubic finite field extensions, IEEE Trans. Inform. Theory, 45 (1999), 2601-2605. [10] K. Karabina, Factor-4 and 6 compression of cyclotomic subgroups of $\mathbb F$*24m and $\mathbb F$*36m, J. Math. Crypt., 4 (2010), 1-42. [11] A. Lenstra, Using cyclotomic polynomials to construct efficient discrete logarithm cryptosystems over finite fields, in "Proceedings of ACISP'97,'' Springer-Verlag, (1997), 127-138. [12] A. Lenstra and E. Verheul, The XTR public key system, in "Advances in Cryptology - CRYPTO'00,'' Springer-Verlag, (2000), 1-19. [13] R. Lidl and H. Niederreiter, "Finite Fields,'' Addison-Wesley, 1983. [14] H. Niederreiter, A public-key cryptosystem based on shift-register sequences, in "Advances in Cryptology - EUROCRYPT'85,'' Springer-Verlag, (1986), 35-39.doi: 10.1007/3-540-39805-8_4. [15] H. Niederreiter, Some new cryptosystems based on feedback shift register sequences, Math. J. Okayama Univ., 30 (1988), 121-149. [16] C. P. Schnorr, Efficient signature generation by smart cards, J. Cryptology, 4 (1991), 161-174. [17] M. Shirase, D. Han, Y. Hibin, H. Kim and T. Takagi, A more compact representation of XTR cryptosystem, IEICE T. Fund. Electr., E91-A (2008), 2843-2850. [18] P. Smith, LUC public-key encryption, Dr. Dobb's J., (1994), 44-49. [19] P. Smith and C. Skinner, A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms, in "Advances in Cryptology - ASIACRYPT'94,'' Springer-Verlag, (1994), 14-21. [20] C. H. Tan, X. Yi and C. K. Siew, Signature schemes based on third order shift registers, in "Information Security and Privacy,'' Springer-Verlag, (2001), 445-459. [21] C. H. Tan, X. Yi and C. K. Siew, On the n-th order shift register based discrete logarithm, IECE Trans. Fund., E86-A (2003), 1213-1216. [22] C. H. Tan, X. Yi and C. K. Siew, On Diffie-Hellman problems in 3rd order shift register, IECE Trans. Fund., E87-A (2004), 1206-1208. [23] E. Verheul, Certificates of recoverability with scalable recovery agent security, in "Proceedings of PKC 2000,'' Springer-Verlag, (2000), 258-275.