A Non-abelian Group Based on Block Upper Triangular Matrices with Cryptographic Applications | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Non-abelian Group Based on Block Upper Triangular Matrices with Cryptographic Applications

  • Conference paper
Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5527))

Abstract

The aim of this article is twofold. In the first place, we describe a special non-abelian group of block upper triangular matrices, and verify that choosing properly certain parameters, the order of the subgroup generated by one of these matrices can be as large as needed. Secondly, we propose and implement a new key exchange scheme based on these primitives. The security of the proposed system is based on discrete logarithm problem although a non-abelian group of matrices is used. The primary advantadge of this scheme is that no prime numbers are used and the efficiency is guaranteed by the use of a quick exponentiation algorithm for this group of matrices.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Agnew, G.B., Mullin, R.C., Vanstone, S.A.: Fast Exponentiation in GF(2n). In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 251–255. Springer, Heidelberg (1988)

    Chapter  Google Scholar 

  2. Álvarez, R., Ferrández, F., Vicent, J.F., Zamora, A.: Applying quick exponentiation for block upper triangular matrices. Applied Mathematics and Computation 183, 729–737 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  3. Anshel, I., Anshel, M., Goldfeld, D.: An algebraic method for public-key cryptography. Mathematical Research Letters 6, 287–291 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Blake, I., Seroussi, G., Smart, N.: Elliptic Curves in Cryptography. London Mathematical Society. Lecture Notes, vol. 265. Cambridge University Press, Cambridge (1999)

    Book  MATH  Google Scholar 

  5. Climent, J.J., Gorla, E., Rosenthal, J.: Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications (AMC) 1, 1–11 (2006)

    MathSciNet  MATH  Google Scholar 

  6. Climent, J.J.: Propiedades espectrales de matrices: el índice de matrices triangulares por bloques. La raíz Perron de matrices cocíclicas no negativas. Ph.D Thesis, Valencia. Sapin (1993)

    Google Scholar 

  7. Coppersmith, D., Odlyzko, A., Schroeppel, R.: Discrete logarithms in GF(p). Algorithmica, 1–15 (1986)

    Google Scholar 

  8. Diffie, W., Hellman, M.: New directions In Cryptography. IEEE Trans. Information Theory 22, 644–654 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gathen, J.: Efficient and Optimal Exponentiation in Finite Fields. Computational Complexity 1, MR 94a:68061, 360–394 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  10. Gordon, D.M.: A Survey of Fast Exponentiation Methods. Journal of Algorithms 27, 129–146 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  11. Hoffman, K., Kunze, R.: Linear Algebra. Prentice-Hall, New Jersey (1971)

    MATH  Google Scholar 

  12. Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J.: New Public Key Cryptosystem Unsing Braid Groups. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 166–183. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  13. Koblitz, N.: A Course in Number Theory and Cryptography. Springer, Heidelberg (1987)

    Book  MATH  Google Scholar 

  14. Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge (1994)

    Book  MATH  Google Scholar 

  15. McCurley, K.: The discret logarithm problem. Cryptology and Computational Number Theory. In: Proceedings of Symposia in Applied Mathematics, vol. 42, pp. 49–74 (1990)

    Google Scholar 

  16. Menezes, A., Van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Florida (2001)

    MATH  Google Scholar 

  17. Menezes, A., Wu, Y.-H.: A polynomial representation for logarithms in GF(q). Acta arithmetica 47, 255–261 (1986)

    MathSciNet  Google Scholar 

  18. Menezes, A., Wu, Y.-H.: The Discrete Logarithm Problem in GL(n,q). Ars Combinatoria 47, 22–32 (1997)

    MathSciNet  Google Scholar 

  19. Odoni, R.W.K., Varadharajan, V., Sanders, P.W.: Public Key Distribution in Matrix Rings. Electronic Letters 20, 386–387 (1984)

    Article  Google Scholar 

  20. Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Trans. Info. Theory 24, 106–110 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  21. Shuhong, G., Gathen, J., Panario, D., Shoup, V.: Algorithms for Exponentiation in Finite Fields. Journal of Symbolic Computation 29-6, 879–889 (2000)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Ciencia de la Computación e Inteligencia Artificial, Universidad de Alicante, Campus de San Vicente, Ap. Correos 99, E–03080, Alicante, Spain

    Rafael Álvarez, Leandro Tortosa, José Vicent & Antonio Zamora

Authors
  1. Rafael Álvarez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Leandro Tortosa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. José Vicent
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Antonio Zamora
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Avinguda Països Catalans, 26, 43007, Tarragona, Spain

    Maria Bras-Amorós

  2. Department of Mathematics, The Technical University of Denmark, Building 303, 2800, Lyngby, Denmark

    Tom Høholdt

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Álvarez, R., Tortosa, L., Vicent, J., Zamora, A. (2009). A Non-abelian Group Based on Block Upper Triangular Matrices with Cryptographic Applications. In: Bras-Amorós, M., Høholdt, T. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 2009. Lecture Notes in Computer Science, vol 5527. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02181-7_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02181-7_13

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02180-0

  • Online ISBN: 978-3-642-02181-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation