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

Discrete logarithm like problems and linear recurring sequences

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

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.
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.

[2]

A. Brouwer, R. Pellikaan and E. Verheul, Doing more with fewer bits,, in, (1999), 321.

[3]

W. Diffie and M. Hellman, New directions in cryptography,, IEEE Trans. Inform. Theory, 22 (1976), 644.

[4]

C. M. Fiduccia, An efficient formula for linear recurring sequences,, SIAM J. Comput., 14 (1985), 106.

[5]

J. von zur Gathen and J. Gerhard, "Modern Computer Algebra,'', Cambridge Univ. Press, (2003).

[6]

K. Giuliani and G. Gong, Analogues to the Gong-Harn and XTR cryptosystems,, in, (2003).

[7]

K. Giuliani and G. Gong, Efficient key agreement and signature schemes using compact representations in $GF(p$10$)$,, in, (2004).

[8]

K. Giuliani and G. Gong, New LFSR-based cryptosystems and the trace discrete logarithm problem (Trace-DLP),, in, (2005), 298.

[9]

G. Gong and L. Harn, Public-key cryptosystems based on cubic finite field extensions,, IEEE Trans. Inform. Theory, 45 (1999), 2601.

[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.

[11]

A. Lenstra, Using cyclotomic polynomials to construct efficient discrete logarithm cryptosystems over finite fields,, in, (1997), 127.

[12]

A. Lenstra and E. Verheul, The XTR public key system,, in, (2000), 1.

[13]

R. Lidl and H. Niederreiter, "Finite Fields,'', Addison-Wesley, (1983).

[14]

H. Niederreiter, A public-key cryptosystem based on shift-register sequences,, in, (1986), 35. 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.

[16]

C. P. Schnorr, Efficient signature generation by smart cards,, J. Cryptology, 4 (1991), 161.

[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.

[18]

P. Smith, LUC public-key encryption,, Dr. Dobb's J., (1994), 44.

[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, (1994), 14.

[20]

C. H. Tan, X. Yi and C. K. Siew, Signature schemes based on third order shift registers,, in, (2001), 445.

[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.

[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.

[23]

E. Verheul, Certificates of recoverability with scalable recovery agent security,, in, (2000), 258.

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.

[2]

A. Brouwer, R. Pellikaan and E. Verheul, Doing more with fewer bits,, in, (1999), 321.

[3]

W. Diffie and M. Hellman, New directions in cryptography,, IEEE Trans. Inform. Theory, 22 (1976), 644.

[4]

C. M. Fiduccia, An efficient formula for linear recurring sequences,, SIAM J. Comput., 14 (1985), 106.

[5]

J. von zur Gathen and J. Gerhard, "Modern Computer Algebra,'', Cambridge Univ. Press, (2003).

[6]

K. Giuliani and G. Gong, Analogues to the Gong-Harn and XTR cryptosystems,, in, (2003).

[7]

K. Giuliani and G. Gong, Efficient key agreement and signature schemes using compact representations in $GF(p$10$)$,, in, (2004).

[8]

K. Giuliani and G. Gong, New LFSR-based cryptosystems and the trace discrete logarithm problem (Trace-DLP),, in, (2005), 298.

[9]

G. Gong and L. Harn, Public-key cryptosystems based on cubic finite field extensions,, IEEE Trans. Inform. Theory, 45 (1999), 2601.

[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.

[11]

A. Lenstra, Using cyclotomic polynomials to construct efficient discrete logarithm cryptosystems over finite fields,, in, (1997), 127.

[12]

A. Lenstra and E. Verheul, The XTR public key system,, in, (2000), 1.

[13]

R. Lidl and H. Niederreiter, "Finite Fields,'', Addison-Wesley, (1983).

[14]

H. Niederreiter, A public-key cryptosystem based on shift-register sequences,, in, (1986), 35. 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.

[16]

C. P. Schnorr, Efficient signature generation by smart cards,, J. Cryptology, 4 (1991), 161.

[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.

[18]

P. Smith, LUC public-key encryption,, Dr. Dobb's J., (1994), 44.

[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, (1994), 14.

[20]

C. H. Tan, X. Yi and C. K. Siew, Signature schemes based on third order shift registers,, in, (2001), 445.

[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.

[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.

[23]

E. Verheul, Certificates of recoverability with scalable recovery agent security,, in, (2000), 258.

[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]

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

[4]

Yong-Kum Cho. A quadratic Fourier representation of the Boltzmann collision operator with an application to the stability problem. Kinetic & Related Models, 2012, 5 (3) : 441-458. doi: 10.3934/krm.2012.5.441

[5]

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

[6]

Hongyan Yan, Yun Sun, Yuanguo Zhu. A linear-quadratic control problem of uncertain discrete-time switched systems. Journal of Industrial & Management Optimization, 2017, 13 (1) : 267-282. doi: 10.3934/jimo.2016016

[7]

Mikko Orispää, Markku Lehtinen. Fortran linear inverse problem solver. Inverse Problems & Imaging, 2010, 4 (3) : 485-503. doi: 10.3934/ipi.2010.4.485

[8]

Marcelo Disconzi. On a linear problem arising in dynamic boundaries. Evolution Equations & Control Theory, 2014, 3 (4) : 627-644. doi: 10.3934/eect.2014.3.627

[9]

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

[10]

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

[11]

Senda Ounaies, Jean-Marc Bonnisseau, Souhail Chebbi, Halil Mete Soner. Merton problem in an infinite horizon and a discrete time with frictions. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1323-1331. doi: 10.3934/jimo.2016.12.1323

[12]

Xiao Lan Zhu, Zhi Guo Feng, Jian Wen Peng. Robust design of sensor fusion problem in discrete time. Journal of Industrial & Management Optimization, 2017, 13 (2) : 825-834. doi: 10.3934/jimo.2016048

[13]

V.N. Malozemov, A.V. Omelchenko. On a discrete optimal control problem with an explicit solution. Journal of Industrial & Management Optimization, 2006, 2 (1) : 55-62. doi: 10.3934/jimo.2006.2.55

[14]

Xiangtuan Xiong, Jinmei Li, Jin Wen. Some novel linear regularization methods for a deblurring problem. Inverse Problems & Imaging, 2017, 11 (2) : 403-426. doi: 10.3934/ipi.2017019

[15]

Qiang Du, M. D. Gunzburger, L. S. Hou, J. Lee. Analysis of a linear fluid-structure interaction problem. Discrete & Continuous Dynamical Systems - A, 2003, 9 (3) : 633-650. doi: 10.3934/dcds.2003.9.633

[16]

Shigeaki Koike, Hiroaki Morimoto, Shigeru Sakaguchi. A linear-quadratic control problem with discretionary stopping. Discrete & Continuous Dynamical Systems - B, 2007, 8 (2) : 261-277. doi: 10.3934/dcdsb.2007.8.261

[17]

Naoufel Ben Abdallah, Irene M. Gamba, Giuseppe Toscani. On the minimization problem of sub-linear convex functionals. Kinetic & Related Models, 2011, 4 (4) : 857-871. doi: 10.3934/krm.2011.4.857

[18]

Shaoyong Lai, Qichang Xie. A selection problem for a constrained linear regression model. Journal of Industrial & Management Optimization, 2008, 4 (4) : 757-766. doi: 10.3934/jimo.2008.4.757

[19]

Mathias Staudigl, Jan-Henrik Steg. On repeated games with imperfect public monitoring: From discrete to continuous time. Journal of Dynamics & Games, 2017, 4 (1) : 1-23. doi: 10.3934/jdg.2017001

[20]

Marek Galewski, Renata Wieteska. Multiple periodic solutions to a discrete $p^{(k)}$ - Laplacian problem. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2535-2547. doi: 10.3934/dcdsb.2014.19.2535

2016 Impact Factor: 0.8

Metrics

  • PDF downloads (0)
  • HTML views (0)
  • Cited by (0)

[Back to Top]