Abstract
This article presents a novel pairing algorithm over supersingular genus-2 binary hyperelliptic curves. Starting from Vercauteren’s work on optimal pairings, we describe how to exploit the action of the 23m-th power Verschiebung in order to reduce the loop length of Miller’s algorithm even further than the genus-2 η T approach.
As a proof of concept, we detail an optimized software implementation and an FPGA accelerator for computing the proposed optimal Eta pairing on a genus-2 hyperelliptic curve over \(\mathbb{F}_{2^{367}}\), which satisfies the recommended security level of 128 bits. These designs achieve favourable performance in comparison with the best known implementations of 128-bit-security Type-1 pairings from the literature.
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
Aranha, D.F., Karabina, K., Longa, P., Gebotys, C., López, J.: Faster Explicit Formulas for Computing Pairings over Ordinary Curves. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 48–68. Springer, Heidelberg (2011)
Aranha, D.F., López, J., Hankerson, D.: Efficient Software Implementation of Binary Field Arithmetic using Vector Instruction Sets. In: Abdalla, M., Barreto, P. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 144–161. Springer, Heidelberg (2010)
Aranha, D.F., López, J., Hankerson, D.: High-Speed Parallel Software Implementation of the η T Pairing. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 89–105. Springer, Heidelberg (2010)
Aranha, D.F., Knapp, E., Menezes, A., Rodríguez-Henríquez, F.: Parallelizing the Weil and Tate pairings. In: Chen, L. (ed.) IMACC 2011. LNCS, vol. 7089, pp. 275–295. Springer, Heidelberg (2011)
Barreto, P., Galbraith, S., Héigeartaigh, C.Ó., Scott, M.: Efficient pairing computation on supersingular Abelian varieties. Des. Codes Crypt. 42, 239–271 (2007)
Barreto, P., Naehrig, M.: Pairing-Friendly Elliptic Curves of Prime Order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)
Beuchat, J.L., Díaz, J.G., Mitsunari, S., Okamoto, E., Rodríguez-Henríquez, F., Teruya, T.: High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 21–39. Springer, Heidelberg (2010)
Beuchat, J.L., López-Trejo, E., Martínez-Ramos, L., Mitsunari, S., Rodríguez-Henríquez, F.: Multi-Core Implementation of the Tate Pairing over Supersingular Elliptic Curves. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 413–432. Springer, Heidelberg (2009)
Beuchat, J.L., Detrey, J., Estibals, N., Okamoto, E., Rodríguez-Henríquez, F.: Fast architectures for the η T pairing over small-characteristic supersingular elliptic curves. IEEE Trans. Comput. 60(2), 266–281 (2011)
Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
Boneh, D., Gentry, C., Waters, B.: Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 258–275. Springer, Heidelberg (2005)
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)
Cantor, D.: Computing in the Jacobian of a hyperelliptic curve. Math. Comput. 48(177), 95–101 (1987)
Chatterjee, S., Hankerson, D., Menezes, A.: On the Efficiency and Security of Pairing-Based Protocols in the Type 1 and Type 4 Settings. In: Hasan, M.A., Helleseth, T. (eds.) WAIFI 2010. LNCS, vol. 6087, pp. 114–134. Springer, Heidelberg (2010)
Cheung, R., Duquesne, S., Fan, J., Guillermin, N., Verbauwhede, I., Yao, G.: FPGA Implementation of Pairings using Residue Number System and Lazy Reduction. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 421–441. Springer, Heidelberg (2011)
Cohen, H., Frey, G. (eds.): Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete Mathematics and its Applications. Chapman & Hall/CRC (2006)
Estibals, N.: Compact Hardware for Computing the Tate Pairing over 128-Bit-Security Supersingular Curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 397–416. Springer, Heidelberg (2010)
Frey, G., Rück, H.G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comput. 62(206), 865–874 (1994)
Galbraith, S., Paterson, K., Smart, N.: Pairings for cryptographers. Discrete Applied Mathematics 156, 3113–3121 (2008)
Galbraith, S.: Supersingular Curves in Cryptography. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 495–513. Springer, Heidelberg (2001)
Galbraith, S.D., Pujolàs, J., Ritzenthaler, C., Smith, B.: Distortion maps for genus two curves. J. Math. Cryptol. 3(1), 1–18 (2009)
Gaudry, P., Hess, F., Smart, N.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptol. 15(1), 19–46 (2001)
Ghosh, S., Roychowdhury, D., Das, A.: High Speed Cryptoprocessor for η T Pairing on 128-Bit Secure Supersingular Elliptic Curves over Characteristic two Fields. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 442–458. Springer, Heidelberg (2011)
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)
Granger, R., Page, D., Smart, N.: High Security Pairing-Based Cryptography Revisited. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 480–494. Springer, Heidelberg (2006)
Gueron, S., Kounavis, M.E.: Carry-less multiplication and its usage for computing the GCM mode. White paper (2010), http://software.intel.com/file/24918
Hess, F.: Pairing Lattices. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 18–38. Springer, Heidelberg (2008)
Hess, F., Smart, N., Vercauteren, F.: The Eta pairing revisited. IEEE Trans. Inf. Theory 52(10), 4595–4602 (2006)
Joux, A.: A One Round Protocol for Tripartite Diffie–Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–394. Springer, Heidelberg (2000)
Koblitz, N., Menezes, A.: Pairing-Based Cryptography at High Security Levels. In: Smart, N.P. (ed.) IMACC 2005. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005)
Lee, E., Lee, H.S., Park, C.M.: Efficient and generalized pairing computation on abelian varieties (2009)
Lee, E., Lee, Y.: Tate pairing computation on the divisors of hyperelliptic curves of genus 2. J. Korean Math. Soc. 45(4), 1057–1073 (2008)
Lubicz, D., Robert, D.: Efficient Pairing Computation with Theta Functions. In: Hanrot, G., Morain, F., Thomé, E. (eds.) ANTS-IX. LNCS, vol. 6197, pp. 251–269. Springer, Heidelberg (2010)
Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curves logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39(5), 1639–1646 (1993)
Miller, V.: Short programs for functions on curves (1986) (unpublished manuscript), http://crypto.stanford.edu/miller
Miller, V.: The Weil pairing, and its efficient calculation. J. Cryptol. 17(4), 235–261 (2004)
Mitsunari, S., Sakai, R., Kasahara, M.: A new traitor tracing. IEICE Trans. Fundamentals E85–A(2), 481–484 (2002)
Naehrig, M., Niederhagen, R., Schwabe, P.: New Software Speed Records for Cryptographic Pairings. In: Abdalla, M., Barreto, P. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 109–123. Springer, Heidelberg (2010)
Ronan, R., Héigeartaigh, C.Ó., Murphy, C., Scott, M., Kerins, T.: Hardware acceleration of the Tate pairing on a genus 2 hyperelliptic curve. J. Syst. Architect. 53, 85–98 (2007)
Rubin, K., Silverberg, A.: Using Abelian varieties to improve pairing-based cryptography. J. Cryptol. 22(3), 330–364 (2009)
Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: SCIS 2000, pp. 26–28 (2000)
Taverne, J., Faz-Hernández, A., Aranha, D.F., Rodríguez-Henríquez, F., Hankerson, D., López, J.: Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction. J. Cryptographic Engineering 1(3), 187–199 (2011)
Vercauteren, F.: Optimal pairings. IEEE Trans. Inf. Theory 56(1), 455–461 (2010)
Verheul, E.R.: Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. J. Cryptol. 17(4), 277–296 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aranha, D.F., Beuchat, JL., Detrey, J., Estibals, N. (2012). Optimal Eta Pairing on Supersingular Genus-2 Binary Hyperelliptic Curves. In: Dunkelman, O. (eds) Topics in Cryptology – CT-RSA 2012. CT-RSA 2012. Lecture Notes in Computer Science, vol 7178. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27954-6_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-27954-6_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-27953-9
Online ISBN: 978-3-642-27954-6
eBook Packages: Computer ScienceComputer Science (R0)