Gaussian elimination in split unitary groups with an application to public-key cryptography

Year 2017, Volume: 4 Issue: 3, 247 - 260, 15.09.2017

Ayan Mahalanobis , Anupam Singh

https://doi.org/10.13069/jacodesmath.327373

Abstract

Gaussian elimination is used in special linear groups to
solve the word problem. In this paper, we extend Gaussian
elimination to split unitary groups. These algorithms
have an application in building a public-key cryptosystem, we demonstrate
that.

Keywords

Unitary groups, Gaussian elimination, Row-column operations

References

• [1] S. Ambrose, S. Murray, C. E. Praeger, C. Schneider, Constructive membership testing in black–box classical groups, Proceedings of The Third International Congress on Mathematical Software, LNCS 6327 (2011) 54–57.
• [2] H. Bäärnhielm, D. Holt, C. R. Leedham-Green, E. A. O’Brien, A practical model for computation with matrix groups, J. Symb. Comput. 68 (2015) 27–60.
• [3] W. Bosma, J. Cannon, C. Playoust, The Magma algebra system. I: The user language, J. Symb. Comput. 24(3-4) (1997) 235–265.
• [4] P. Brooksbank, Constructive recognition of classical groups in their natural representation, J. Symb. Comput. 35(2) (2003) 195–239.
• [5] P. Brooksbank, Fast constructive recognition of black–box unitary groups, LMS J. Comput. Math. 6 (2003) 162–197.
• [6] R. Carter, Simple Groups of Lie Type, New York: John Wiley and Sons, 1972.
• [7] A. M. Cohen, S. H. Murray, D. E. Taylor, Computing in groups of Lie type, Math. Comput. 73 (2004) 1477–1498.
• [8] E. Costi, Constructive Membership Testing in Classical Groups, Ph.D. thesis, Queen Mary, Univ. of London, 2009.
• [9] J. Dieudonne, On the automorphisms of the classical groups. with a supplement by Loo-Keng Hua, Mem. Amer. Math. Soc. 2 (1951) vi+122.
• [10] J. F. Grcar, Mathematicians of Gaussian elimination, Notices Amer. Math. Soc. 58(6) (2011) 782–792.
• [11] L. C. Grove, Classical Groups and Geometric Algebra, vol. 39, American Mathematical Society, Graduate Studies in Mathematics, 2002.
• [12] N. Jacobson, Basic Algebra I, W. H. Freeman and Company, New York, 1985.
• [13] W. Kantor À. Seress, Black box classical groups, vol. 149, Mem. Amer. Math. Soc. 149 (2001) viii+168.
• [14] C. R. Leedham–Green, E. A. O’Brien, Constructive recognition of classical groups in odd characteristic, J. Algebra 322(3) (2009) 833–881.
• [15] A. Mahalanobis, A simple generalization of the ElGamal cryptosystem to non–abelian groups II, Commun. Algebra 40(9) (2012) 3583–3596.
• [16] C. Monico, Cryptanalysis of matrix–based MOR system, Commun. Algebra 44(1) (2016) 218–227.
• [17] A. C. Niemeyer, C. E. Praeger, A recognition algorithm for classical groups over finite fields, Proc. London Math. Soc. 77(1) (1998) 117–169.
• [18] E. A. O’Brien, Algorithms for matrix groups, Groups St. Andrews 2009 in Bath, II, London Math. Soc. Lecture Note Ser., 388 (Cambridge Univ. Press, Cambridge, 2011), 297–323.
• [19] SH. Paeng, KC. Ha, J. H. Kim, S. Chee, C. Park, New public key cryptosystem using finite non–abelian groups, Crypto 2001 (J. Kilian, ed.), LNCS, vol. 2139, Springer–Verlag, (2001) 470–485.
• [20] Á. Seress, An introduction to computational group theory, Notices Amer. Math. Soc. 44(6) (1997) 671–679.
• [21] R. Steinberg, Variations on a theme of Chevalley, Pacific J. Math. 9 (1959) 875–891.