Top

Published in:

2020 | OriginalPaper | Chapter

Curves with Fast Computations in the First Pairing Group

Authors : Rémi Clarisse, Sylvain Duquesne, Olivier Sanders

Published in: Cryptology and Network Security

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Pairings are a powerful tool to build advanced cryptographic schemes. The most efficient way to instantiate a pairing scheme is through Pairing-Friendly Elliptic Curves.

Because a randomly picked elliptic curve will not support an efficient pairing (the embedding degree will usually be too large to make any computation practical), a pairing-friendly curve has to be carefully constructed. This has led to famous curves, e.g. Barreto-Naehrig curves.

However, the computation of the Discrete Logarithm Problem on the finite-field side has received much interest and its complexity has recently decreased. Hence the need to propose new curves has emerged.

In this work, we give one new curve that is specifically tailored to be fast over the first pairing-group, which is well suited for several cryptographic schemes, such as group signatures, and their variants, or accumulators.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Optimized and Secure Pairing-Friendly Elliptic Curves Suitable for One Layer Proof Composition

next chapter Revisiting ECM on GPUs

Abe, M., Hoshino, F., Ohkubo, M.: Design in type-I, run in type-III: fast and scalable bilinear-type conversion using integer programming. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 387–415. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_14CrossRefMATH

AlLee, G.: EPID for IoT Identity (2016). https://img.en25.com/Web/McAfeeE10BuildProduction/a6dd7393-63f8-4c08-b3aa-89923182a7e5_EPID_Overview_Public_2016-02-08.pdf

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

Barbulescu, R., Duquesne, S.: Updating key size estimations for pairings. J. Cryptol. 32, 1298–1336 (2019)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. LNCS, vol. 9056, pp. 129–155. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_6CrossRefMATH

Barki, A., Desmoulins, N., Gharout, S., Traoré, J.: Anonymous attestations made practical. In: ACM WiSec 2017, pp. 87–98. ACM (2017)

Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing elliptic curves with prescribed embedding degrees. In: Cimato, S., Persiano, G., Galdi, C. (eds.) SCN 2002. LNCS, vol. 2576, pp. 257–267. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36413-7_19CrossRef

Barreto, P.S.L.M., 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). https://doi.org/10.1007/11693383_22CrossRef

Bernstein, D.J., Lange, T., Schwabe, P.: On the correct use of the negation map in the Pollard rho method. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 128–146. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_8CrossRef

10.

Bichsel, P., Camenisch, J., Neven, G., Smart, N.P., Warinschi, B.: Get shorty via group signatures without encryption. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 381–398. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15317-4_24CrossRef

11.

Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Cryptogr. 37, 133–141 (2005)MathSciNetCrossRefMATH

12.

Brickell, E.F., Camenisch, J., Chen, L.: Direct anonymous attestation. In: ACM CCS 2004, pp. 132–145. ACM (2004)

13.

Brickell, E., Li, J.: Enhanced privacy ID from bilinear pairing for hardware authentication and attestation. Int. J. Inf. Priv. Secur. Integr. 2 1, 3–33 (2011). IEEE Computer Society, In IEEE SocialCom

14.

Brickell, E., Li, J.: Enhanced privacy ID: a direct anonymous attestation scheme with enhanced revocation capabilities. IEEE Trans. Dependable Secur. Comput. 9(3), 345–360 (2012)CrossRef

15.

Camenisch, J., Kohlweiss, M., Soriente, C.: An accumulator based on bilinear maps and efficient revocation for anonymous credentials. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 481–500. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00468-1_27CrossRef

16.

Chatterjee, S., Menezes, A.: Type 2 structure-preserving signature schemes revisited. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 286–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_13CrossRef

17.

Cheon, J.H., Han, K., Lee, C., Ryu, H., Stehlé, D.: Cryptanalysis of the CLT13 multilinear map. J. Cryptol. 32, 547–565 (2019)MathSciNetCrossRefMATH

18.

Cheon, J.H., Lee, C., Ryu, H.: Cryptographic multilinear maps and their cryptanalysis. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 101, 12–18 (2018)CrossRef

19.

Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 476–493. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_26CrossRef

20.

Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptol. 23, 224–280 (2010)MathSciNetCrossRefMATH

21.

Freeman, D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 44–61. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_3CrossRef

22.

Fuchsbauer, G., Hanser, C., Slamanig, D.: Structure-preserving signatures on equivalence classes and constant-size anonymous credentials. J. Cryptol. 32(2), 498–546 (2019)MathSciNetCrossRefMATH

23.

Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Discret. Appl. Math. 156, 3113–3121 (2008)MathSciNetCrossRefMATH

24.

Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_11CrossRef

25.

Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_1CrossRef

26.

Guillevic, A.: Comparing the pairing efficiency over composite-order and prime-order elliptic curves. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 357–372. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38980-1_22CrossRef

27.

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.) PKC 2020. LNCS, vol. 12111, pp. 535–564. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_19CrossRef

28.

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), 1–35 (2020)MathSciNetCrossRefMATH

29.

Guillevic, A., Morain, F.: Discrete Logarithms. In: Guide to Pairing-Based Cryptography. CRC Press - Taylor and Francis Group (2016)

30.

Joux, A.: A one round protocol for tripartite Diffie-Hellman. J. Cryptol. 17, 263–276 (2004)MathSciNetCrossRefMATH

31.

Kachisa, E.J., Schaefer, E.F., Scott, M.: Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 126–135. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85538-5_9CrossRefMATH

32.

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. LNCS, vol. 9814, pp. 543–571. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_20CrossRef

33.

Kim, T., Jeong, J.: Extended tower number field sieve with application to finite fields of arbitrary composite extension degree. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10174, pp. 388–408. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54365-8_16CrossRef

34.

Kim, T., Kim, S., Cheon, J.H.: On the final exponentiation in Tate pairing computations. IEEE Trans. Inf. Theory 59(6), 4033–4041 (2013)MathSciNetCrossRefMATH

35.

Menezes, A., Vanstone, S.A., Okamoto, T.: Reducing elliptic curve logarithms to logarithms in a finite field. In: ACM STOC (1991)

36.

Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF (p) and its cryptographic significance (Corresp.). IEEE Trans. Inf. Theory 24, 106–110 (1978)CrossRefMATH

37.

Pointcheval, D., Sanders, O.: Short randomizable signatures. In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 111–126. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29485-8_7CrossRef

38.

Pollard, J.M.: Monte Carlo methods for index computation \((\text{ mod }~p)\). Math. Comput. 32, 918–924 (1978)MATH

39.

Sarkar, P., Singh, S.: New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 429–458. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_17CrossRef

40.

Shanks, D.: Class number, a theory of factorization, and genera. In: 1969 Number Theory Institute, pp. 415–440. American Mathematical Society (1971)

41.

Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_18CrossRef

42.

Smart, N.P.: Algorithms, key size and protocols report, ECRYPT - CSA (2018). http://www.ecrypt.eu.org/csa/documents/D5.4-FinalAlgKeySizeProt.pdf

43.

TCG (2015). https://trustedcomputinggroup.org/authentication/

44.

Vercauteren, F.: Optimal pairings. IEEE Trans. Inf. Theory 56, 455–461 (2010)MathSciNetCrossRefMATH

Title: Curves with Fast Computations in the First Pairing Group
Authors: Rémi Clarisse
Sylvain Duquesne
Olivier Sanders
Publisher: Springer International Publishing
Book: Cryptology and Network Security
Print ISBN: 978-3-030-65410-8

Electronic ISBN: 978-3-030-65411-5

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-65411-5_14

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"