Abstract
Pairings in elliptic curve cryptography are functions which map a pair of elliptic curve points to a non-zero element of a finite field. In recent years, many useful cryptographic protocols based on pairings have been proposed. The fast implementations of pairings have become a subject of active research areas in cryptology.
In this paper, we give the geometric interpretation of the group law on Hessian curves. Furthermore, we propose the first algorithm for computing the Tate pairing on elliptic curves in Hessian form. Analysis indicates that it is faster than all algorithms of Tate pairing computation known so far for Weierstrass and Edwards curves excepted for the very special elliptic curves with a 4 = 0, a 6 = b 2.
This work was supported by Specialized Research Fund for the Doctoral Program of Higher Education (No. 200802480019) and National Natural Science Foundation of China (No. 61073150).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arène, C., Lange, T., Naehrig, M., Ritzenthaler, C.: Faster Computation of Tate Pairings, Cryptology ePrint Archive, Report 2009/155, http://eprint.iacr.org/2009/155.pdf
Bernstein, D.J., Lange, T.: Analysis and optimization of elliptic-curve single-scalar multiplication. In: Mullen, G.L., Panario, D., Shparlinski, I.E. (eds.) Finite fields and applications, Contemp. Math., vol. 461, pp. 1–19. American Mathematical Society, Providence (2008)
Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)
Boneh, D., Shacham, H.: Group signatures with verifier-local revocation. In: Atluri, V., Pfitzmann, B., McDaniel, P. (eds.) ACM CCS 2004, pp. 168–177. ACM Press, New York (2004)
Chatterjee, S., Sarkar, P., Barua, R.: Efficient computation of Tate pairing in projective coordinate over general characteristic fields. In: Park, C., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 168–181. Springer, Heidelberg (2005)
Cheng, Z., Nistazakis, M.: Implementing pairing-based cryptosystems. In: 3rd International Workshop on Wireless Security Technologies IWWST 2005, London, UK (April 2005)
Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. Appl. Math. 7(4), 385–434 (1986)
Costello, C., Hisil, H., Boyd, C., Nieto, J.M.G., Wong, K.K.H.: Faster pairings on special weierstrass curves. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol. 5671, pp. 89–101. Springer, Heidelberg (2009)
Frey, G., Rück, H.G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comp. 62, 865–874 (1994)
Hisil, H., Carter, G., Dawson, E.: New formulae for efficient elliptic curve arithmetic. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 138–151. Springer, Heidelberg (2007)
Ionica, S., Joux, A.: Another approach to pairing computation in edwards coordinates. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 400–413. Springer, Heidelberg (2008)
Joux, A.: The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002, Part V. LNCS, vol. 2369, pp. 18–20. Springer, Heidelberg (2002)
Joux, A.: A one round protocol for tripartite Diffie-Hellman. J. Cryptol. 17(4), 263–276 (2004)
Joye, M., Quisquater, J.-J.: Hessian elliptic curves and side-channel attacks. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 402–410. Springer, Heidelberg (2001)
Koblitz, N., Menezes, A.: Pairing-based cryptography at high security levels. In: Smart, P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005)
Miller, V.S.: Short Programs for Functions on Curves, IBM Watson, T.J. Research Center (1986), http://crypto.stanford.edu/miller/miller.ps
Miller, V.S.: The Weil pairing and its efficient calculation. J. Cryptol. 17(4), 235–261 (2004)
Smart, N.P.: The Hessian form of an elliptic curve. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 118–125. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gu, H., Gu, D., Xie, W. (2011). Efficient Pairing Computation on Elliptic Curves in Hessian Form. In: Rhee, KH., Nyang, D. (eds) Information Security and Cryptology - ICISC 2010. ICISC 2010. Lecture Notes in Computer Science, vol 6829. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24209-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-24209-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24208-3
Online ISBN: 978-3-642-24209-0
eBook Packages: Computer ScienceComputer Science (R0)