Top

Designs, Codes and Cryptography

Published in:

07-03-2020

Cocks–Pinch curves of embedding degrees five to eight and optimal ate pairing computation

Authors: Aurore Guillevic, Simon Masson, Emmanuel Thomé

Published in: Designs, Codes and Cryptography | Issue 6/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Recent algorithmic improvements of discrete logarithm computation in special extension fields threaten the security of pairing-friendly curves used in practice. A possible answer to this delicate situation is to propose alternative curves that are immune to these attacks, without compromising the efficiency of the pairing computation too much. We follow this direction, and focus on embedding degrees 5 to 8; we extend the Cocks–Pinch algorithm to obtain pairing-friendly curves with an efficient ate pairing. We carefully select our curve parameters so as to thwart possible attacks by “special” or “tower” Number Field Sieve algorithms. We target a 128-bit security level, and back this security claim by time estimates for the DLP computation. We also compare the efficiency of the optimal ate pairing computation on these curves to \(k=12\) curves (Barreto–Naehrig, Barreto–Lynn–Scott), \(k=16\) curves (Kachisa–Schaefer–Scott) and \(k=1\) curves (Chatterjee–Menezes–Rodríguez-Henríquez).

previous article On the number of resolvable Steiner triple systems of small 3-rank

next article Predicting truncated multiple recursive generators with unknown parameters

Available only for authorised users

The approximation \(\mathbf{i} _1 \approx 25\mathbf{m} \) in Table 4 is clearly implementation-dependent. Since it has negligible bearing on the final cost anyway, we stick to that coarse estimate.

In particular, the line computations involve some sparse products, e.g. \((\sum a_ix^i)\times (\sum b_ix^i)\) in \(\mathbb {F}_{p^8}\) over \(\mathbb {F}_{p^2}\) with \(a_1=0\) (see [21]), which costs 8\(\mathbf{m} _2\) by Karatsuba. Note that [54] claims 7\(\mathbf{m} _2\) but with no explicit formula. We were not able to match this. The work [35, §3.3] obtained 7\(\mathbf{m} _2\) in favorable cases at a cost of extra precomputations.

The Edwards model is not available for a quartic or sextic twist because there is no 4-torsion point on these twists, only the quadratic twist can be in Edwards form [41]. The Jacobi quartic model is not available for a cubic or sextic twist because there is no 2-torsion point on the twist. The Hessian model is compatible with cubic twists but not sextic twists.

We depart from the conventional notation \(\rho \) for the Dickman rho function, to avoid confusion with \(\rho = \log p/\log r\).

For the RSA-768 record factorisation, we used the corrected value 46.7G instead of 47.7G, according to P. Zimmermann’s webpage https://members.loria.fr/PZimmermann/papers/#rsa768.

We mention that there was a typo in [7, Table 3]: in the factorisation of \(2^{1039}-1\), there were 66.7M rows after filtering, not 82.8M, and the reduction factor of the filtering step is 143, not 167.

Aoki K., Franke J., Kleinjung T., Lenstra A.K., Osvik D.A.: A kilobit special number field sieve factorization. In: Kurosawa K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 1–12. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76900-2_1.

Aranha D.F.: Pairings are not dead, just resting. Slides at ECC 2017 workshop. (2017). https://ecc2017.cs.ru.nl/.

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 2012. LNCS, vol. 7708, pp. 177–195. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36334-4_11.

Aranha D.F., Gouvêa C.P.L.: RELIC is an Efficient LIbrary for Cryptography. https://github.com/relic-toolkit/relic.

Aranha D.F., Karabina K., Longa P., Gebotys C.H., López-Hernández J.C.: 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). https://doi.org/10.1007/978-3-642-20465-4_5.

Bai S., Gaudry P., Kruppa A., Thomé E., Zimmermann P.: Factorization of RSA-220. Number Theory list (May 12 2016), https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;d17fe291.1605, http://www.loria.fr/~zimmerma/papers/rsa220.pdf.

Barbulescu R., Duquesne S.: Updating key size estimations for pairings. J. Cryptol. 32(4), 1298–1336 (2019). https://doi.org/10.1007/s00145-018-9280-5.MathSciNetCrossRefMATH

Barbulescu R., Gaudry P., Guillevic A., Morain F.: Improving NFS for the discrete logarithm problem in non-prime finite fields. In: Oswald E., Fischlin M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 129–155. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_6.

Barbulescu R., Gaudry P., Kleinjung T.: The tower number field sieve. In: Iwata T., Cheon J.H. (eds.) ASIACRYPT 2015, Part II. LNCS, vol. 9453, pp. 31–55. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48800-3_2.

10.

Barreto P.S.L.M., Costello C., Misoczki R., Naehrig M., Pereira G.C.C.F., Zanon G.: Subgroup security in pairing-based cryptography. In: Lauter K.E., Rodríguez-Henríquez F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 245–265. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-319-22174-8_14.

11.

Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Goldwasser, S. (ed.) ITCS 2012. pp. 326–349. ACM (Jan 2012). https://doi.org/10.1145/2090236.2090263

12.

Boneh D., Franklin M.K.: Identity-based encryption from the Weil pairing. In: Kilian J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_13.

13.

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). https://doi.org/10.1007/3-540-45682-1_30.

14.

Bouvier C., Gaudry P., Imbert L., Jeljeli H., Thomé E.: Discrete logarithms in GF\((p)\)—180 digits. Number Theory list, item 004703 (2014). https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;615d922a.1406.

15.

Bowe S.: BLS12-381: New zk-SNARK elliptic curve construction. Zcash blog (2017). https://blog.z.cash/new-snark-curve/.

16.

Chatterjee S., Menezes A., Rodríguez-Henríquez F.: On instantiating pairing-based protocols with elliptic curves of embedding degree one. IEEE Trans. Comput. 66(6), 1061–1070 (2017). https://doi.org/10.1109/TC.2016.2633340.MathSciNetCrossRefMATH

17.

Childers G.: Factorization of a 1061-bit number by the special number field sieve. Cryptology ePrint Archive, Report 2012/444 (2012). http://eprint.iacr.org/2012/444.

18.

Chuengsatiansup C., Martindale C.: Pairing-friendly twisted hessian curves. In: Chakraborty D., Iwata T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 228–247. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-05378-9_13.

19.

Chung J., Hasan M.A.: Asymmetric squaring formulae. In: 18th IEEE Symposium on Computer Arithmetic (ARITH ’07). pp. 113–122 (2007). https://doi.org/10.1109/ARITH.2007.11.

20.

Cohen H., Miyaji A., Ono T.: Efficient elliptic curve exponentiation using mixed coordinates. In: Ohta K., Pei D. (eds.) ASIACRYPT’98. LNCS, vol. 1514, pp. 51–65. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49649-1_6.

21.

Costello C., Lange T., Naehrig M.: Faster pairing computations on curves with high-degree twists. In: Nguyen P.Q., Pointcheval D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 224–242. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_14.

22.

Devegili A.J., Ó hÉigeartaigh C., Scott M., Dahab R.: Multiplication and squaring on pairing-friendly fields. Cryptology ePrint Archive, Report 2006/471 (2006). http://eprint.iacr.org/2006/471.

23.

Duquesne S., El Mrabet N., Fouotsa E.: Efficient computation of pairings on jacobi quartic elliptic curves. J. Math. Cryptol. 8(4), 331–362 (2014). https://doi.org/10.1515/jmc-2013-0033.MathSciNetCrossRefMATH

24.

Fotiadis G., Konstantinou E.: TNFS resistant families of pairing-friendly elliptic curves. Theroretical Comput. Sci. 800, 73–89 (2019). https://doi.org/10.1016/j.tcs.2019.10.017.MathSciNetCrossRefMATH

25.

Fotiadis G., Martindale C.: Optimal TNFS-secure pairings on elliptic curves with even embedding degree. Cryptology ePrint Archive, Report 2018/969 (2018). https://eprint.iacr.org/2018/969.

26.

Freeman D., Scott M., Teske E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptol. 23(2), 224–280 (2010). https://doi.org/10.1007/s00145-009-9048-z.MathSciNetCrossRefMATH

27.

Fried J., Gaudry P., Heninger N., Thomé E.: A kilobit hidden SNFS discrete logarithm computation. In: Coron J., Nielsen J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 202–231. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-56620-7_8.

28.

Gordon D.M.: Designing and detecting trapdoors for discrete log cryptosystems. In: Brickell E.F. (ed.) CRYPTO’92. LNCS, vol. 740, pp. 66–75. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_5.

29.

Granger R., Scott M.: Faster squaring in the cyclotomic subgroup of sixth degree extensions. In: Nguyen P.Q., Pointcheval D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 209–223. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_13.

30.

Guillevic A.: Simulating DL computation in \({{\rm GF}}(p^n)\) with the new variants of the Tower-NFS algorithm to deduce security level estimates (2017). Slides at ECC 2017 workshop. https://ecc2017.cs.ru.nl/.

31.

Joux A.: A one round protocol for tripartite Diffie-Hellman. J. Cryptol. 17(4), 263–276 (2004). https://doi.org/10.1007/s00145-004-0312-y.MathSciNetCrossRefMATH

32.

Joux A., Lercier R.: Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method. Math. Comput. 72(242), 953–967 (2003). https://doi.org/10.1090/S0025-5718-02-01482-5.MathSciNetCrossRefMATH

33.

Joux A., Pierrot C.: The special number field sieve in \(\mathbb{F}_{p^n}\)—application to pairing-friendly constructions. In: Cao Z., Zhang F. (eds.) PAIRING 2013. LNCS, vol. 8365, pp. 45–61. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-319-04873-4_3.

34.

Karabina K.: Squaring in cyclotomic subgroups. Math. Comput. 82(281), 555–579 (2013). https://doi.org/10.1090/S0025-5718-2012-02625-1.MathSciNetCrossRefMATH

35.

Khandaker M.A.A., Nanjo Y., Ghammam L., Duquesne S., Nogami Y.,Kodera Y.: Efficient optimal ate pairing at 128-bit security level. In: Patra A., Smart N.P. (eds.) INDOCRYPT 2017. LNCS, vol.10698, pp. 186–205. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-71667-1_10

36.

Kim T., Barbulescu R.: Extended tower number field sieve: a new complexity for the medium prime case. In: Robshaw M., Katz J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 543–571. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_20.

37.

Kiyomura Y., Inoue A., Kawahara Y., Yasuda M., Takagi T., Kobayashi T.: Secure and efficient pairing at 256-bit security level. In: Gollmann D., Miyaji A., Kikuchi H. (eds.) ACNS 17. LNCS, vol. 10355, pp. 59–79. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-61204-1_4.

38.

Kleinjung T., Aoki K., Franke J., Lenstra A.K., Thomé E., Bos J.W., Gaudry P., Kruppa A., Montgomery P.L., Osvik D.A., te Riele H.J.J., Timofeev A., Zimmermann P.: Factorization of a 768-bit RSA modulus. In: Rabin T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333–350. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_18.

39.

Kleinjung T., Diem C., Lenstra A.K., Priplata C., Stahlke C.: Computation of a 768-bit prime field discrete logarithm. In: Coron J., Nielsen J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 185–201. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-56620-7_7.

40.

Lewko A.B.: Tools for simulating features of composite order bilinear groups in the prime order setting. In: Pointcheval D., Johansson T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 318–335. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_20.

41.

Li L., Wu H., Zhang F.: Pairing computation on edwards curves with high-degree twists. In: Lin D., Xu S., Yung M. (eds.) Inscrypt, LNCS, vol. 8567, pp. 185–200. Springer, Guangzhou, China (2013). https://doi.org/10.1007/978-3-319-12087-4_12.

42.

Menezes A., Sarkar P., Singh S.: Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography. In: Phan R.C., Yung M. (eds.) Mycrypt Conference, LNCS, vol. 10311, pp. 83–108. Springer, Kuala Lumpur (2016). https://doi.org/10.1007/978-3-319-61273-7_5.

43.

Montgomery P.L.: Five, six, and seven-term Karatsuba-like formulae. IEEE Trans. Comput. 54, 362–369 (2005). https://doi.org/10.1109/TC.2005.49.CrossRefMATH

44.

National Institute of Standards and Technology: Recommendation Key Management (part 1: General); SP 800-57 Part 1, fourth revision (2016). https://doi.org/10.6028/NIST.SP.800-57pt1r4.

45.

Pereira G.C., Simplício M.A., Naehrig M., Barreto P.S.: A family of implementation-friendly BN elliptic curves. J. Syst. Softw. 84(8), 1319–1326 (2011). https://doi.org/10.1016/j.jss.2011.03.083.CrossRef

46.

Sarkar P., Singh S.: A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm. In: Cheon J.H., Takagi T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 37–62. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_2.

47.

Schirokauer O.: The number field sieve for integers of low weight. Math. Comput. 79(269), 583–602 (2010). https://doi.org/10.1090/S0025-5718-09-02198-X.MathSciNetCrossRefMATH

48.

Scott M.: Implementing cryptographic pairings (invited talk). In: Takagi T., Okamoto T., Okamoto E., Okamoto T. (eds.) PAIRING 2007. LNCS, vol. 4575, pp. 177–196. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73489-5.

49.

Semaev I.A.: Special prime numbers and discrete logs in finite prime fields. Math. Comput. 71(737), 363–377 (2002). https://doi.org/10.1090/S0025-5718-00-01308-9.MathSciNetCrossRefMATH

50.

Sutherland A.V.: Accelerating the CM method. LMS J. Comput. Math. 15, 172–204 (2012). https://doi.org/10.1112/S1461157012001015.MathSciNetCrossRefMATH

51.

Tanaka S., Nakamula K.: Constructing pairing-friendly elliptic curves using factorization of cyclotomic polynomials. In: Galbraith S.D., Paterson K.G. (eds.) PAIRING 2008. LNCS, vol. 5209, pp. 136–145. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85538-5_10.

52.

Vercauteren F.: Optimal pairings. IEEE Trans. Inform. Theory 56(1), 455–461 (2010). https://doi.org/10.1109/TIT.2009.2034881.MathSciNetCrossRefMATH

53.

Weber D., Denny T.F.: The solution of McCurley’s discrete log challenge. In: Krawczyk H. (ed.) CRYPTO’98. LNCS, vol. 1462, pp. 458–471. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055747.

54.

Zhang X., Lin D.: Analysis of optimum pairing products at high security levels. In: Galbraith S.D., Nandi M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 412–430. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34931-7_24.

Title: Cocks–Pinch curves of embedding degrees five to eight and optimal ate pairing computation
Authors: Aurore Guillevic
Simon Masson
Emmanuel Thomé
Publication date: 07-03-2020
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 6/2020
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-020-00727-w

Springer Professional

Cocks–Pinch curves of embedding degrees five to eight and optimal ate pairing computation

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 6/2020

On the number of resolvable Steiner triple systems of small 3-rank

Linear codes with few weights from cyclotomic classes and weakly regular bent functions

Relative generalized Hamming weights of affine Cartesian codes

Predicting truncated multiple recursive generators with unknown parameters

Block transitive codes attaining the Tsfasman–Vladut–Zink bound

Quantum attacks on some feistel block ciphers

Premium Partner