[en] Pairings on genus 2 hyperelliptic curves are believed to be far less efficient compared to elliptic curve ones. The main reason is the structure of their Jacobian which leads to slower doubling and addition operations. However, genus 2 curves have attractive features that, when properly exploited, can counter the computationally expensive Jacobian operations. One of these features is that they admit twists of higher degrees than elliptic curves, allowing to map Jacobian operations to smaller extension fields. In this paper, we apply generalizations of elliptic curve constructions based on the Cocks–Pinch and Brezing–Weng methods to derive instances of efficient genus 2 pairings, focusing on curves with embedding degrees 8, 16, and 24 that admit degree 8 twists. We present a theoretical comparison with their elliptic curve counterparts, based on the number of prime field multiplications. Our examples target 128- and 192-bit security, considering the progress of STNFS attacks on the DLP in extension fields of composite degree. We propose the first STNFS-secure genus 2 pairings at 128-bit security, as well as more promising candidates for 192-bit security compared to previous works. Finally, we present a proof-of-concept implementation in SageMath that can serve as a baseline for future benchmarks and efficient implementations.
Disciplines :
Computer science
Author, co-author :
ARENAS CORREA, Monica Patricia ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > IRiSC
FOTIADIS, Georgios ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust > APSIA > Team Peter RYAN ; =nil, Foundation, Limassol, Cyprus
Konstantinou, Elisavet ; Department of Information and Communication Systems Engineering, University of the Aegean, Samos, Greece
External co-authors :
yes
Language :
English
Title :
Special TNFS-Secure Pairings on Ordinary Genus 2 Hyperelliptic Curves
Publication date :
July 2024
Event name :
Progress in Cryptology - AFRICACRYPT
Event organizer :
Serge Vaudenay and Christophe Petit
Event place :
Douala, Cameroon
Event date :
From 10 to 12 of July 2024
Audience :
International
Main work title :
Progress in Cryptology - AFRICACRYPT 2024 - 15th International Conference on Cryptology in Africa, 2024, Proceedings
Editor :
Vaudenay, Serge
Publisher :
Springer Science and Business Media Deutschland GmbH
The authors acknowledge the financial support from the Luxembourg National Research Fund (FNR) under the CORE project Privacy-Preserving Tokenisation of Artworks \u2013PABLO (C21/IS/16326754/PABLO) and the INTER project Secure and Verifiable Electronic Testing and Assessment Systems \u2013 SEVERITAS (INTER /ANR/20/14926102 ANR-20-CE39-009-03).
Aranha, D.F., Fuentes-Castañeda, L., Knapp, E., Menezes, A., Rodríguez-Henríquez, F.: Implementing pairings at the 192-bit security level. In: Abdalla, M., Lange, T. (eds.) Pairing-Based Cryptography-Pairing 2012-5th International Conference, Cologne, Germany, May 16-18, 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7708, pp. 177–195. Springer (2012). https://doi. org/10.1007/978-3-642-36334-4_11
Arenas, M., Fotiadis, G.: Hyperelliptic curve pairings code (2024). https://doi.org/10.5281/zenodo.11172005
Balakrishnan, J., Belding, J., Chisholm, S., Eisenträger, K., Stange, K.E., Teske, E.: Pairings on hyperelliptic curves. In: Cojocaru, A., Lauter, K.E., Pries, R., Scheidler, R. (eds.) WIN-Women in Numbers-Research Directions in Number Theory, Fields Institute Communications, vol. 60, pp. 87–120. American Mathematical Society (2011)
Balasubramanian, R., Koblitz, N.: The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-vanstone algorithm. J. Cryptology 11(2), 141–145 (1998). https://doi.org/10.1007/s001459900040
Barbulescu, R., Duquesne, S.: Updating key size estimations for pairings. J. Cryptology 32(4), 1298–1336 (2019). https://doi.org/10.1007/s00145-018-9280-5
Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing elliptic curves with prescribed embedding degrees. In: Cimato, S., Galdi, C., Persiano, G. (eds.) Security in Communication Networks, Third International Conference, SCN 2002, Amalfi, Italy, September 11-13, 2002. Revised Papers. Lecture Notes in Computer Science, vol. 2576, pp. 257–267. Springer (2002). https://doi.org/10.1007/3-540-36413-7_19
Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S.E. (eds.) Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11-12, 2005, Revised Selected Papers. Lecture Notes in Computer Science, vol. 3897, pp. 319–331. Springer (2005). https://doi.org/10.1007/11693383_22
Blake, I.F., Seroussi, G., Smart, N.P.: Advances in Elliptic Curve Cryptography, vol. 317. Cambridge University Press (2005)
Boneh, D., Franklin, M.K.: Identity-based encryption from the weil pairing. SIAM J. Comput. 32(3), 586–615 (2003). https://doi.org/10.1137/S0097539701398521
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. J. Cryptology 17(4), 297–319 (2004). https://doi.org/10.1007/s00145-004-0314-9
Bowe, S.: BLS12-381: New zk-SNARK elliptic curve construction. https://electriccoin.co/blog/new-snark-curve/(2017), march 11, 2017
Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Cryptogr. 37(1), 133–141 (2005). https://doi.org/10.1007/s10623-004-3808-4
Brickell, E., Chen, L., Li, J.: A new direct anonymous attestation scheme from bilinear maps. In: Lipp, P., Sadeghi, A., Koch, K. (eds.) Trusted Computing-Challenges and Applications, First International Conference on Trusted Computing and Trust in Information Technologies, Trust 2008, Villach, Austria, March 11-12, 2008, Proceedings. Lecture Notes in Computer Science, vol. 4968, pp. 166– 178. Springer (2008). https://doi.org/10.1007/978-3-540-68979-9_13
Cantor, D.G.: Computing in the Jacobian of a hyperelliptic curve. Math. Comput. 48(177), 95–101 (1987)
Chen, L., Morrissey, P., Smart, N.P.: Pairings in trusted computing. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing-Based Cryptography-Pairing 2008, Second International Conference, Egham, UK, September 1-3, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5209, pp. 1–17. Springer (2008). https://doi.org/10.1007/978-3-540-85538-5_1
Dryłlo, R.: Constructing pairing-friendly genus 2 curves with split Jacobian. In: Galbraith, S.D., Nandi, M. (eds.) Progress in Cryptology-INDOCRYPT 2012, 13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7668, pp. 431– 453. Springer (2012). https://doi.org/10.1007/978-3-642-34931-7_25
Dupont, R., Enge, A., Morain, F.: Building curves with arbitrary small MOV degree over finite prime fields. J. Cryptology 18(2), 79–89 (2005). https://doi.org/10.1007/s00145-004-0219-7
Fan, X., Gong, G., Jao, D.: Efficient pairing computation on genus 2 curves in projective coordinates. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) Selected Areas in Cryptography, 15th International Workshop, SAC 2008, Sackville, New Brunswick, Canada, August 14-15, Revised Selected Papers. Lecture Notes in Computer Science, vol. 5381, pp. 18–34. Springer (2008). https://doi.org/10.1007/978-3-642-04159-4_2
Fotiadis, G.: A short-list of pairing-friendly curves resistant to the special TNFS at 192-bit security level. https://members.loria.fr/AGuillevic/siam-ag23-elliptic-curves-and-pairings-in-cryptography-minisymposium/(2023), SIAM Conference on Applied Algebraic Geometry (AG23) Elliptic Curves and Pairings in Cryptography
Fotiadis, G., Konstantinou, E.: Ordinary pairing-friendly genus 2 hyperelliptic curves with absolutely simple Jacobians. In: Blömer, J., Kotsireas, I.S., Kutsia, T., Simos, D.E. (eds.) Mathematical Aspects of Computer and Information Sciences-7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10693, pp. 409–424. Springer (2017). https://doi.org/10.1007/978-3-319-72453-9_33
Fotiadis, G., Konstantinou, E.: Generating pairing-friendly elliptic curve parameters using sparse families. J. Math. Cryptology 12(2), 83–99 (2018). https://doi. org/10.1515/jmc-2017-0024
Freeman, D.: A generalized brezing-weng algorithm for constructing pairing-friendly ordinary abelian varieties. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing-Based Cryptography-Pairing 2008, Second International Conference, Egham, UK, September 1-3, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5209, pp. 146–163. Springer (2008). https://doi.org/10.1007/978-3-540-85538-5_11
Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptology 23(2), 224–280 (2010). https://doi.org/10.1007/s00145-009-9048-z
Freeman, D., Stevenhagen, P., Streng, M.: Abelian varieties with prescribed embedding degree. In: van der Poorten, A.J., Stein, A. (eds.) Algorithmic Number Theory, 8th International Symposium, ANTS-VIII, Banff, Canada, May 17-22, 2008, Proceedings. Lecture Notes in Computer Science, vol. 5011, pp. 60–73. Springer (2008). https://doi.org/10.1007/978-3-540-79456-1_3
Freeman, D.M., Satoh, T.: Constructing pairing-friendly hyperelliptic curves using Weil restriction. J. Number Theory 131(5), 959–983 (2011)
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.D., Hess, F., Vercauteren, F.: Hyperelliptic pairings. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing-Based Cryptography-Pairing 2007, First International Conference, Tokyo, Japan, July 2-4, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4575, pp. 108–131. Springer (2007). https://doi.org/10.1007/978-3-540-73489-5_7
Granger, R., Hess, F., Oyono, R., Thériault, N., Vercauteren, F.: Ate pairing on hyperelliptic curves. In: Naor, M. (ed.) Advances in Cryptology-EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4515, pp. 430–447. Springer (2007). https://doi.org/10.1007/978-3-540-72540-4_25
Guillevic, A.: A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) Public-Key Cryptography-PKC 2020-23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part II. Lecture Notes in Computer Science, vol. 12111, pp. 535–564. Springer (2020). https://doi.org/10.1007/978-3-030-45388-6_19
Guillevic, A., Masson, S., Thomé, E.: Cocks-pinch curves of embedding degrees five to eight and optimal ate pairing computation. Des. Codes Cryptogr. 88(6), 1047–1081 (2020). https://doi.org/10.1007/s10623-020-00727-w
Guillevic, A., Singh, S.: On the alpha value of polynomials in the tower number field sieve algorithm. IACR Cryptol. ePrint Arch. 2019, 885 (2019). https://eprint. iacr.org/2019/885
Guillevic, A., Vergnaud, D.: Genus 2 hyperelliptic curve families with explicit Jacobian order evaluation and pairing-friendly constructions. In: Abdalla, M., Lange, T. (eds.) Pairing-Based Cryptography-Pairing 2012-5th International Conference, Cologne, Germany, May 16-18, 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7708, pp. 234–253. Springer (2012). https://doi.org/10. 1007/978-3-642-36334-4_16
Hayashida, D., Hayasaka, K., Teruya, T.: Efficient final exponentiation via cyclotomic structure for pairings over families of elliptic curves. IACR Cryptol. ePrint Arch. p. 875 (2020). https://eprint.iacr.org/2020/875
Ishii, M.: Pairings on hyperelliptic curves with considering recent progress on the NFS algorithms. In: Takagi, T., Wakayama, M., Tanaka, K., Kunihiro, N., Kimoto, K., Duong, D.H. (eds.) Mathematical Modelling for Next-Generation Cryptography: CREST Crypto-Math Project, pp. 81–96. Mathematics for Industry, Springer Singapore (2017). https://doi.org/10.1007/978-981-10-5065-7_5
Ishii, M., Inomata, A., Fujikawa, K.: A Construction of a twisted ate pairing on a family of Kawazoe-Takahashi curves at 192-bit security level and its cost estimate. In: Camp, O., Furnell, S., Mori, P. (eds.) Proceedings of the 2nd International Conference on Information Systems Security and Privacy, ICISSP 2016, Rome, Italy, February 19-21, 2016, pp. 432–439. SciTePress (2016). https://doi.org/10. 5220/0005742304320439
Joux, A.: A one round protocol for tripartite Diffie-Hellman. J. Cryptology 17(4), 263–276 (2004). https://doi.org/10.1007/s00145-004-0312-y
Kachisa, E.J.: Generating more Kawazoe-Takahashi genus 2 pairing-friendly hyperelliptic curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing-Based Cryptography-Pairing 2010-4th International Conference, Yamanaka Hot Spring, Japan, December 2010. Proceedings. Lecture Notes in Computer Science, vol. 6487, pp. 312–326. Springer (2010). https://doi.org/10.1007/978-3-642-17455-1_20
Kawazoe, M., Takahashi, T.: Pairing-friendly hyperelliptic curves with ordinary Jacobians of type y2 = x5 + ax. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing-Based Cryptography-Pairing 2008, Second International Conference, Egham, UK, September 1-3, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5209, pp. 164–177. Springer (2008). https://doi.org/10.1007/978-3-540-85538-5_12
Kim, T., Barbulescu, R.: Extended tower number field sieve: a new complexity for the medium prime case. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology-CRYPTO 2016-36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9814, pp. 543–571. Springer (2016). https://doi.org/10.1007/978-3-662-53018-4_20
Lauter, K.E., Shang, N.: Generating pairing-friendly parameters for the CM construction of genus 2 curves over prime fields. Des. Codes Cryptogr. 67(3), 341–355 (2013). https://doi.org/10.1007/s10623-012-9611-8
Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39(5), 1639–1646 (1993). https://doi.org/10.1109/18.259647
Milne, J.S.: Abelian varieties. In: Cornell, G., Silverman, J.H. (eds.) Arithmetic Geometry, pp. 103–150. Springer, New York, NY (1986). https://doi.org/10.1007/978-1-4613-8655-1_5
Oort, F.: Abelian varieties over finite fields. Nato Secur. Sci. Ser. D Inf. Commun. Secur. 16, 123 (2008)
Zhang, F.: Twisted ate pairing on hyperelliptic curves and applications. Sci. China Inf. Sci. 53(8), 1528–1538 (2010)
Zhao, C., Zhang, F., Huang, J.: A note on the ate pairing. Int. J. Inf. Sec. 7(6), 379–382 (2008). https://doi.org/10.1007/s10207-008-0054-1
