Discrete logarithm like problems and linear recurring sequences

Previous Article
Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions
AMC Home
This Issue
Next Article
A new class of majority-logic decodable codes derived from polarity designs

May 2013, 7(2): 187-195. doi: 10.3934/amc.2013.7.187

Discrete logarithm like problems and linear recurring sequences

Santos González ^1, , Llorenç Huguet ^2, , Consuelo Martínez ^1, and Hugo Villafañe ^2,

1.	Departamento de Matemáticas, Universidad de Oviedo, C/ Calvo Sotelo s/n, 33007 Oviedo, Spain, Spain
2.	Departament de Ciènces Matemàtiques i Informàtica, Universitat de les Illes Balears, Ctra. de Valldemossa km 7, 5, 07122 Palma de Mallorca, Spain, Spain

Received October 2012 Published May 2013

Abstract
Related Papers

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.

Mathematics Subject Classification: Primary: 11T71; Secondary: 94A5.

Citation: Santos González, Llorenç Huguet, Consuelo Martínez, Hugo Villafañe. Discrete logarithm like problems and linear recurring sequences. Advances in Mathematics of Communications, 2013, 7 (2) : 187-195. doi: 10.3934/amc.2013.7.187

References:

[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$¹⁰$)$, 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$^_2^4m and $\mathbb F$^_3^6m, 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.

show all references

References:

[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$¹⁰$)$, 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$^_2^4m and $\mathbb F$^_3^6m, 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.

[1]	Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281
[2]	Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489
[3]	Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022031
[4]	Violetta Weger, Karan Khathuria, Anna-Lena Horlemann, Massimo Battaglioni, Paolo Santini, Edoardo Persichetti. On the hardness of the Lee syndrome decoding problem. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022029
[5]	Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023
[6]	Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2-party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 87-92. doi: 10.3934/amc.2011.5.87
[7]	Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046
[8]	Yu-Chi Chen. Security analysis of public key encryption with filtered equality test. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021053
[9]	Alar Leibak. On the number of factorizations of $ t $ mod $ N $ and the probability distribution of Diffie-Hellman secret keys for many users. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021029
[10]	Andreu Ferré Moragues. Properties of multicorrelation sequences and large returns under some ergodicity assumptions. Discrete and Continuous Dynamical Systems, 2021, 41 (6) : 2809-2828. doi: 10.3934/dcds.2020386
[11]	Yong-Kum Cho. A quadratic Fourier representation of the Boltzmann collision operator with an application to the stability problem. Kinetic and Related Models, 2012, 5 (3) : 441-458. doi: 10.3934/krm.2012.5.441
[12]	Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete and Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[13]	Hongyan Yan, Yun Sun, Yuanguo Zhu. A linear-quadratic control problem of uncertain discrete-time switched systems. Journal of Industrial and Management Optimization, 2017, 13 (1) : 267-282. doi: 10.3934/jimo.2016016
[14]	Shengbing Deng, Zied Khemiri, Fethi Mahmoudi. On spike solutions for a singularly perturbed problem in a compact riemannian manifold. Communications on Pure and Applied Analysis, 2018, 17 (5) : 2063-2084. doi: 10.3934/cpaa.2018098
[15]	Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215
[16]	Mikko Orispää, Markku Lehtinen. Fortran linear inverse problem solver. Inverse Problems and Imaging, 2010, 4 (3) : 485-503. doi: 10.3934/ipi.2010.4.485
[17]	Marcelo Disconzi. On a linear problem arising in dynamic boundaries. Evolution Equations and Control Theory, 2014, 3 (4) : 627-644. doi: 10.3934/eect.2014.3.627
[18]	Thomas R. Cameron, Sebastian Charmot, Jonad Pulaj. On the linear ordering problem and the rankability of data. Foundations of Data Science, 2021, 3 (2) : 133-149. doi: 10.3934/fods.2021010
[19]	V.N. Malozemov, A.V. Omelchenko. On a discrete optimal control problem with an explicit solution. Journal of Industrial and Management Optimization, 2006, 2 (1) : 55-62. doi: 10.3934/jimo.2006.2.55
[20]	Davide Bellandi. On the initial value problem for a class of discrete velocity models. Mathematical Biosciences & Engineering, 2017, 14 (1) : 31-43. doi: 10.3934/mbe.2017003

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Santos González Llorenç Huguet Consuelo Martínez Hugo Villafañe
on Google Scholar
Santos González Llorenç Huguet Consuelo Martínez Hugo Villafañe

[Back to Top]