Signature from Automorphism Group of Special Linear Group

doi:10.3969/j.issn.1006-2475.2017.06.020

Abstract

Abstract: Based on the discrete logarithm problem in the automorhoism group of special linear group, this paper proposes a signature scheme over the non-commutative group, and analyzes the difficulty ofthe discrete logarithm problem in the automorhoism group of special linear group. The paper shows that, by selecting proper parameters, the new scheme is much more secure than DSA in the finite field and is as secure as DSA over elliptic curves. The result shows the running efficiency of the new scheme is improved by adopting Leedham-Green algorithm to compute the power of matrices.

Key words: special linear group, diagonal automorphism, inner automorphism, discrete logarithm, signature

CLC Number:

TP309.7

PAN Ping, CAO Yang, HE Bin-tao. Signature from Automorphism Group of Special Linear Group[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.06.020.

References

[1] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997,26(5):1484-1509.

[2] Baumslag G, Fazio N, Nicolosi A R, et al. Generalized learning problems and applications to non-commutative cryptography[C]// Proceedings of the 5th International Conference on Provable Security. 2011:324-339.

[3] Myasnikov A G, Shpilrain V, Ushakov A. Non-commutative Cryptography and Complexity of Group-theoretic Problems[M]. American Mathematical Society, 2011.

[4] Hashimoto Y, Sakurai K. On Construction of Signature Schemes Based on Birational Permutations over Noncommutative Rings[DB/OL]. http://eprint.iacr.org/2008/340, 2008-08-04.

[5] Ogura N, Shigenori U. Cryptanalysis of the birational permutation signature scheme over a non-commutative ring[J]. JSIAM Letters, 2010,2:85-88.

[6] Ko K H, Choi D H, Cho M S, et al. New Signature Scheme Using Conjugacy Problem[DB/OL]. http://eprint.iacr.org/2002/168, 2002-11-11.

[7] Wang Licheng, Wang Lihua, Cao Zhenfu, et al. Conjugate adjoining problem in braid groups and new design of braid-based signatures[J]. Science China(Information Sciences), 2010,53(3):524-536.

[8] Paeng S H, Ha K C, Kim J H, et al. New public key cryptosystem using finite non Abelian groups[C]// Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology. 2001:470-485.

[9] Paeng S H. On the security of cryptosystem using automorphism groups[J]. Information Processing Letters, 2003,88(6):293-298.

[10] Tobias C. Security analysis of the MOR cryptosystem[C]// Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography. 2003:175-186.

[11] Korsten A. Cryptanalysis of MOR and discrete logarithms in inner automorphism groups[C]// Proceedings of the 2nd Western European Workshop on Research in Cryptology. 2008:78-89.

[12] Mahalanobis A. A simple generalization of the ElGamal cryptosystem to non-Abelian groups II[J]. Communications in Algebra, 2012,40(9):3583-3596.

[13] Mahalanobis A. The MOR cryptosystem and finite p-groups[J]. Contemporary Mathematics, 2015,633:81-95.

[14] Mahalanobis A. The MOR cryptosystem and extra-special p-groups[J]. Journal of Discrete Mathematical Sciences and Cryptography, 2011,18(3):201-208.

[15] Pan Ping, Wang Licheng, Yang Yixian, et al. Chameleon hash functions and one-time signature schemes from inner automorphism groups[J]. Fundamenta Informaticae, 2013,126(1):103-119.

[16] 徐明曜,曲海鹏. 有限p群[M].北京:北京大学出版社, 2010.

[17] Koblitz N, Menezes A, Vaustone S. The state of elliptic curve cryptography[J]. Designs, Codes and Cryptography, 2000,19(2-3):173-193.

[18] Hayashi T, Shinohara N, Wang Lihua, et al. Solving a 676-bit discrete logarithm problem in GF(3⁶ⁿ)[C]// Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography. 2010:351-367.

[19] Humphries S P. Generation of special linear groups by transvections[J]. Journal of Algebra, 1986,99(2):480-495.

[20] Leedham-Green C R, O’Brien E A. Constructive recognition of classical groups in odd characteristic[J]. Journal of Algebra, 2009,322(3):833-881.

[21] The GAP Group. GAP: Groups, Algorithms, Programming (Version 4.4)[EB/OL]. http://www.gap-system.org, 2006-11-24.