Abstract
In recent years there has been much interest in the development and the fast computation of bilinear pairings due to their practical and myriad applications in cryptography. Well known efficient examples are the Weil and Tate pairings and their variants such as the Eta and Ate pairings on the Jacobians of (hyper-)elliptic curves. In this paper, we consider the use of projective coordinates for pairing computations on genus 2 hyperelliptic curves over prime fields. We generalize Chatterjee et. al.’s idea of encapsulating the computation of the line function with the group operations to genus 2 hyperelliptic curves, and derive new explicit formulae for the group operations in projective and new coordinates in the context of pairing computations. When applying the encapsulated explicit formulae to pairing computations on supersingular genus 2 curves over prime fields, theoretical analysis shows that our algorithm is faster than previously best known algorithms whenever a field inversion is more expensive than about fifteen field multiplications. We also investigate pairing computations on non-supersingular genus 2 curves over prime fields based on the new formulae, and detail the various techniques required for efficient implementation.
Chapter PDF
Similar content being viewed by others
Keywords
References
Avanzi, R.M., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC, Boca Raton (2006)
Barreto, P.L.S.M., Galbraith, S., Ó hÉigeartaigh, C., Scott, M.: Efficient Pairing Computation on Supersingular Abelian Varieties. Design, Codes and Cryptography 42, 239–271 (2007)
Barreto, P.L.S.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient Algorithm for Pairing-Based Cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 354. Springer, Heidelberg (2002)
Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. SIAM Journal of Computing 32(3), 586–615 (2003)
Boneh, D., Lynn, B., Shacham, H.: Short Signatures from the Weil Pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)
Chatterjee, S., Sarkar, P., Barua, R.: Efficient Computation of Tate Pairing in Projective Coordinate over General Characteristic Fields. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 168–181. Springer, Heidelberg (2005)
Choie, Y., Lee, E.: Implementation of Tate Pairing on Hyperelliptic Curve of Genus 2. In: Lim, J.-I., Lee, D.-H. (eds.) ICISC 2003. LNCS, vol. 2971, pp. 97–111. Springer, Heidelberg (2004)
Cocks, C., Pinch, R.G.E.: Identity-based Cryptosystems Based on the Weil Pairing (Unpublished manuscript) (2001)
Duursma, I.M., Lee, H.-S.: Tate pairing implementation for hyperelliptic curves y 2 = x p− x + d. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 111–123. Springer, Heidelberg (2003)
Galbraith, S.D., McKee, J.F., Valença, P.C.: Ordinary Abelian Varieties Having Small Embedding Degree. Finite Fields and Their Applications 13(4), 800–814 (2007)
Freeman, D.: Constructing Pairing-Friendly Genus 2 Curves over Prime Fields with Ordinary Jacobians. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 152–176. Springer, Heidelberg (2007)
Frey, G., Lange, T.: Fast Bilinear Maps from The Tate-Lichtenbaum Pairing on Hyperelliptic Curves. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 466–479. Springer, Heidelberg (2006)
Frey, G., Rück, H.-G.: A Remark Concerning m-Divisibility and the Discrete Logarithm Problem in the Divisor Class Group of Curves. Mathematics of Computation 62(206), 865–874 (1994)
Granger, R., Hess, F., Oyono, R., Thériault, N., Vercauteren, F.: Ate Pairing on Hyperelliptic Curves. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 430–447. Springer, Heidelberg (2007)
Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, New York (2004)
Ó hÉigeartaigh, C., Scott, M.: Pairing Calculation on Supersingular Genus 2 Curves. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 302–316. Springer, Heidelberg (2007)
Hess, F., Smart, N.P., Vercauteren, F.: The Eta Pairing Revisited. IEEE Transactions on Information Theory 52(10), 4595–4602 (2006)
Hitt, L.: Families of Genus 2 Curves with Small Embedding Degree, Cryptology ePrint Archive, Report 2007/001 (2007), http://eprint.iacr.org/2007/001
Joux, A.: A One-Round Protocol for Tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS 1838, vol. 1838, pp. 385–394. Springer, Heidelberg (2000)
Karatsuba, A., Ofman, Y.: Multiplication of Multidigit Numbers on Automata. Soviet Physics Doklady (English Translation) 7(7), 595–596 (1963)
Kawazoe, M., Takahashi, T.: Pairing-friendly Hyperelliptic Curves of Type y2 = x5 + ax, Cryptology ePrint Archive, Report 2008/026 (2008), http://eprint.iacr.org/2008/026
Lange, T.: Formulae for Arithmetic on Genus 2 Hyperelliptic Curves. Applicable Algebra in Engineering, Communication and Computing 15(5), 295–328 (2005)
Lee, E., Lee, H.-S., Lee, Y.: Eta Pairing Computation on General Divisors over Hyperelliptic Curves y 2 = x 7 − x ±1. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 349–366. Springer, Heidelberg (2007)
Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing Elliptic Curve Logarithms to a Finite Field. IEEE Transactions on Information Theory 39(5), 1639–1646 (1993)
Menezes, A., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. Chapman & Hall/CRC, Boca Raton (1997)
Miller, V.S.: Short Programs for Functions on Curves (Unpublished manuscript) (1986), http://crypto.stanford.edu/miller/miller.pdf
Miyamoto, Y., Doi, H., Matsuo, K., Chao, J., Tsujii, S.: A Fast Addition Algorithm of Genus Two Hyperelliptic Curve. In: The 2002 Symposium on Cryptography and Information Security - SCIS 2002, pp. 497–502 (2002) (in Japanese)
Mumford, D.: Tata Lectures on Theta II. In: Prog. Math., vol. 43. Birkhäuser (1984)
Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems Based on Pairings. In: Proceedings of the 2000 Symposium on Cryptography and Information Security - SCIS 2002, Okinawa, Japan, pp. 26–28 (2000)
Scott, M.: MIRACL (Multiprecision Integer and Rational Arithmetic C/C++ Library), http://www.shamus.ie/
Scott, M.: Scaling Security in Pairing-based Protocols, Cryptology ePrint Archive, Report 2005/139 (2005), http://eprint.iacr.org/2005/139
Solinas, J.: Generalized Mersenne Primes, Centre for Applied Cryptographic Research (CACR) Technical Reports, CORR 99-39, http://www.cacr.math.uwaterloo.ca/techreprots/1999/corr99-39.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fan, X., Gong, G., Jao, D. (2009). Efficient Pairing Computation on Genus 2 Curves in Projective Coordinates. In: Avanzi, R.M., Keliher, L., Sica, F. (eds) Selected Areas in Cryptography. SAC 2008. Lecture Notes in Computer Science, vol 5381. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04159-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-04159-4_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04158-7
Online ISBN: 978-3-642-04159-4
eBook Packages: Computer ScienceComputer Science (R0)