Fast Scalar Multiplications on the Curve v²= u^p − au − b over the Finite Field of Characteristic p

• Autorzy: You L. , Yang Y. , Gao S. , Sang Y.

Identyfikatory

DOI

10.3233/FI-2014-978

• Języki publikacji: EN

Abstrakty

EN

Hyperelliptic curves have been widely researched for cryptographic applications, and some special hyperelliptic curves are often considered for practical applications. For efficient implementation of hyperelliptic curve cryptosystems, it is crucial to have efficient scalar multiplication in the Jacobian groups. For the hyperelliptic curve C_q: v²= u^p − au − b over the field F_q with q a power of an odd prime p, Duursma and Sakurai (2000) presented a scalar multiplication algorithm for q = p, a = 1 and b ∈ F_p. In this paper, by introducing the concept of simple divisors, we prove that a general divisor can be decomposed into the sum of some simple divisors. Based on this fact, we present a formula for p-scalar multiplications for any reduced divisor, then we give two efficient algorithms to speed up scalar multiplications for any parameters a and b over any extension of F_p. Compared with the signed binary method, the computations of our algorithms cost 55% to 76% less.

Słowa kluczowe

EN

hyperelliptic curve; cryptosystem; scalar multiplications; divisor; Jacobian group

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 4
• Strony: 395--412
• Opis fizyczny: Bibliogr. 17 poz., tab.

Twórcy

autor

You L.

• College of Communication Engineering, Hangzhou Dianzi University Hangzhou 310018, China

autor

Yang Y.

• College of Communication Engineering, Hangzhou Dianzi University Hangzhou 310018, China

autor

Gao S.

• Department of Mathematical Sciences, Clemson University Clemson, SC 29634-0975, USA

autor

Sang Y.

• College of Communication Engineering, Hangzhou Dianzi University, Hangzhou, China

Bibliografia

• [1] Menezes, A. J., Wu, Y. H., Zuccherato, R. J.: An elementary introduction to hyperelliptic curves, Technical Report CORR-96-19, CACR, University of Waterloo,Waterloo, November 1996.
• [2] Cantor, D.: Computing in the Jacobian of a Hyperelliptic Curve, Mathematics of Computation, 17748, 1987, 95–101.
• [3] Koblitz, N.: Hyperelliptic cryptosystems, Journal of Cryptology, 1, 1989, 139–150.
• [4] Duursma I., Sakurai, K.: Efficient algorithms for the Jacobian variety of hyperelliptic curves y2 = xp − x+ 1 over a finite field of odd characteristic p, Proc. International Conference on Coding Theory, Cryptography and Related Areas(J. Buchmann, T. Høholdt, H. Stichtenoth, H. T. Recillas, Eds), Springer, Guanajuato, Mexico, 2000, 73–89.
• [5] Koblitz, N.: Algebraic aspects of cryptography, Springer-Verlag, Berlin, 1998.
• [6] Joachim, G., Jürgen, G.: Modern Computer Algebra, Cambridge University Press, Cambridge, 1999.
• [7] Enge, A.: The Extended Euclidean Algorithm on Polynomials, and the Computational Efficiency of Hyperelliptic Cryptosystems, Designs, Codes and Cryptography, 231, 2001, 53–74.
• [8] Blake, I.F.,Seroussi, G., Smart, N. P.: Elliptic Curves in Cryptography, LMS 265, Cambridge University Press, London, 1999, 72–73.
• [9] You, L., Gao, S. and Xue, H.: Characteristic polynomials of the curve v2 = up − au − b over finite fields of characteristic p, Finite Fields and Their Applications, 21, 2013, 35–49.
• [10] Pollard, J.: Monte Carlo methods for index computation (mod p), Mathematics of Computation, 32, 1978, 918–924.
• [11] Gaudry, P., Thomé, E., Thériault, N., Diem, C.: A double large prime variation for small genus hyperelliptic index calculus, Mathematics of Computation, 25776, 2007, 475–492.
• [12] Galbraith, S. D.: Supersingular Curves in Cryptography, Proc. Advances in Cryptology, LNCS 2248, Springer-Verlag, 2001, 495–513.
• [13] Joux, A.: A one round protocol for tripartite Diffie-Hellman, Proc. Algorithmic Number Theory Symposium, LNCS 1838, Springer-Verlag, 2000, 385–394.
• [14] Boneh D., Franklin, M.: Identity-based encryption from the Weil pairing, Proc. Advances in Cryptology, LNCS 2139, Springer-Verlag, 2001, 213–229.
• [15] Duursma I., Lee, H. S.: Tate pairing implementation for hyperelliptic curves y2 = xp−x+d, Proc. Advances in Cryptology, LNCS 2894, Springer-Verlag, 2003, 111–123.
• [16] Barreto, P. S. L.M., Galbraith, S., Oh Eigeartaigh C., Scott, M.: Efficient pairing computation on supersingular Abelian varieties, Designs, Codes and Cryptography, 42, 2007, 239–271.
• [17] Estibals, N.: Compact Hardware for Computing the Tate Pairing over 128-Bit-Security Supersingular Curves, Proc. Pairing-Based Cryptography - Pairing 2010, LNCS 6487, Springer-Verlag, 2010, 397–416