Skip to main content
Top
Published in: Applicable Algebra in Engineering, Communication and Computing 4/2023

30-08-2021 | Original Paper

On the security of DLCSP over \(GL_n(\mathbb {F}_q[S_r])\)

Authors: Atul Pandey, Indivar Gupta, Dhiraj Kumar Singh

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 4/2023

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Discrete logarithm problem (DLP) and Conjugacy search problem (CSP) are two important tools for designing public key protocols. However DLP is used over commutative as well as non-commutative platforms but CSP is used only over non-commutative platforms. To harden the security of cryptosystems using DLP and CSP as base problems, various authors have combined these two problems to form a new problem called Discrete logarithm with conjugacy search problem (DLCSP). It has been used to design key exchange protocols and signature schemes over the general linear group with entries from group ring, that is, \(GL_n(\mathbb {F}_q[S_r])\). In this paper, we show that, if someone can solve DLP in polynomial time over some finite extension of \(\mathbb {F}_q\), then DLCSP over \(GL_n(\mathbb {F}_q[S_r])\) can also be solved in polynomial time with non-negligible probability.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Menezes, A.J., Wu, Y.: The discrete logarithm problem in \(GL_n(\mathbb{F}_q)\). Ars Combinatorica 47, 23–32 (1997) Menezes, A.J., Wu, Y.: The discrete logarithm problem in \(GL_n(\mathbb{F}_q)\). Ars Combinatorica 47, 23–32 (1997)
2.
go back to reference Myasnikov, A.D., Ushakov, A.: Quantum algorithm for the discrete logarithm problem for matrices over finite group rings. Groups Complex. Cryptol. 6, 31–36 (2014)MathSciNetCrossRefMATH Myasnikov, A.D., Ushakov, A.: Quantum algorithm for the discrete logarithm problem for matrices over finite group rings. Groups Complex. Cryptol. 6, 31–36 (2014)MathSciNetCrossRefMATH
3.
go back to reference Menezes, A.J., Vanstone, S.A.: A note on cyclic groups, finite fields and the discrete logarithm problem. Appl. Algeb. Eng. Commun. Comput. 3, 67–74 (1992)MathSciNetCrossRefMATH Menezes, A.J., Vanstone, S.A.: A note on cyclic groups, finite fields and the discrete logarithm problem. Appl. Algeb. Eng. Commun. Comput. 3, 67–74 (1992)MathSciNetCrossRefMATH
4.
go back to reference Menezes, A.J., Vanstone, S.A., Oorschot, P.C.V.: Handbook of Applied Cryptography. CRC Press (1997)MATH Menezes, A.J., Vanstone, S.A., Oorschot, P.C.V.: Handbook of Applied Cryptography. CRC Press (1997)MATH
5.
go back to reference Kahrobaei, D., Koupparis, C., Shpilrain, V.: Public key exchange using matrices over group rings. Groups Complex. Cryptol. 5, 97–115 (2013)MathSciNetCrossRefMATH Kahrobaei, D., Koupparis, C., Shpilrain, V.: Public key exchange using matrices over group rings. Groups Complex. Cryptol. 5, 97–115 (2013)MathSciNetCrossRefMATH
6.
go back to reference Moldovyan, D.N., Moldovyan, N.A.: A new hard problem over noncommutative finite groups for cryptographic protocols. Lecture Notes in Comput. Sci. 6258, 183–194 (2010)CrossRef Moldovyan, D.N., Moldovyan, N.A.: A new hard problem over noncommutative finite groups for cryptographic protocols. Lecture Notes in Comput. Sci. 6258, 183–194 (2010)CrossRef
7.
go back to reference Sakalauskas, E., Tvarijonas, P., Raulynaitis, A.: Key agreement protocol using conjugacy search problem and discrete logarithm problem in group representation level. Informatica 18, 115–124 (2007)CrossRefMATH Sakalauskas, E., Tvarijonas, P., Raulynaitis, A.: Key agreement protocol using conjugacy search problem and discrete logarithm problem in group representation level. Informatica 18, 115–124 (2007)CrossRefMATH
8.
11.
go back to reference Ko, K. H., Lee, S. J., Cheon, J. H., Han, J. W., Kang, J., Park, C.: New public-key cryptosystem using braid groups. Advances in cryptology—CRYPTO 2000 (Santa Barbara, CA), 166–183, Lecture Notes in Comput. Sci. 1880, Springer, Berlin (2000) Ko, K. H., Lee, S. J., Cheon, J. H., Han, J. W., Kang, J., Park, C.: New public-key cryptosystem using braid groups. Advances in cryptology—CRYPTO 2000 (Santa Barbara, CA), 166–183, Lecture Notes in Comput. Sci. 1880, Springer, Berlin (2000)
12.
go back to reference Eftekhari, M.: A Diffie-Hellman key exchange protocol using matrices over non-commutative rings. Groups Complex. Cryptol. 4(1), 167–176 (2012)MathSciNetCrossRefMATH Eftekhari, M.: A Diffie-Hellman key exchange protocol using matrices over non-commutative rings. Groups Complex. Cryptol. 4(1), 167–176 (2012)MathSciNetCrossRefMATH
13.
go back to reference Kreuzer, M., Myasnikov, A. D., Ushakov, A.: A linear algebra attack to group-ring-based key exchange protocols. Applied Cryptography and Network Security (ACNS 2014), Lecture Notes in Comput. Sci. vol. 8479, pp. 37–43. Springer, Berlin (2014) Kreuzer, M., Myasnikov, A. D., Ushakov, A.: A linear algebra attack to group-ring-based key exchange protocols. Applied Cryptography and Network Security (ACNS 2014), Lecture Notes in Comput. Sci. vol. 8479, pp. 37–43. Springer, Berlin (2014)
14.
go back to reference Goel, N., Gupta, I., Dubey, M.K., Dass, B.K.: Undeniable signature scheme based over group ring. Appl. Algebra Engrg. Comm. Comput. 27(6), 523–535 (2016)MathSciNetCrossRefMATH Goel, N., Gupta, I., Dubey, M.K., Dass, B.K.: Undeniable signature scheme based over group ring. Appl. Algebra Engrg. Comm. Comput. 27(6), 523–535 (2016)MathSciNetCrossRefMATH
15.
go back to reference Odoni, R., Varadharajan, V., Sanders, R.: Public key distribution in matrix rings. Electron. Lett. 20, 386–387 (1984)CrossRef Odoni, R., Varadharajan, V., Sanders, R.: Public key distribution in matrix rings. Electron. Lett. 20, 386–387 (1984)CrossRef
16.
go back to reference Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and algebraic computation. LNCS, vol. 72, pp. 216–226. Springer, Heidelberg (1979) Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and algebraic computation. LNCS, vol. 72, pp. 216–226. Springer, Heidelberg (1979)
17.
go back to reference ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)MathSciNetCrossRefMATH ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)MathSciNetCrossRefMATH
Metadata
Title
On the security of DLCSP over
Authors
Atul Pandey
Indivar Gupta
Dhiraj Kumar Singh
Publication date
30-08-2021
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 4/2023
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-021-00523-6

Other articles of this Issue 4/2023

Applicable Algebra in Engineering, Communication and Computing 4/2023 Go to the issue

Premium Partner