nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Solving 114-Bit ECDLP for a Barreto-Naehrig Curve

verfasst von : Takuya Kusaka, Sho Joichi, Ken Ikuta, Md. Al-Amin Khandaker, Yasuyuki Nogami, Satoshi Uehara, Nariyoshi Yamai, Sylvain Duquesne

Erschienen in: Information Security and Cryptology – ICISC 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The security of cryptographic protocols which are based on elliptic curve cryptography relies on the intractability of elliptic curve discrete logarithm problem (ECDLP). In this paper, the authors describe techniques applied to solve 114-bit ECDLP in Barreto-Naehrig (BN) curve defined over the odd characteristic field. Unlike generic elliptic curves, BN curve holds an especial interest since it is well studied in pairing-based cryptography. Till the date of our knowledge, the previous record for solving ECDLP in a prime field was 112-bit by Bos et al. in Certicom curve ‘secp112r1’. This work sets a new record by solving 114-bit prime field ECDLP of BN curve using Pollard’s rho method. The authors utilized sextic twist property of the BN curve to efficiently carry out the random walk of Pollard’s rho method. The parallel implementation of the rho method by adopting a client-server model, using 2000 CPU cores took about 6 months to solve the ECDLP.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Recipient Revocable Broadcast Encryption with Dealership

Nächstes Kapitel On the Computational Complexity of ECDLP for Elliptic Curves in Various Forms Using Index Calculus

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_22 CrossRef

Bernstein, D.J., Engels, S., Lange, T., Niederhagen, R., Paar, C., Schwabe, P., Zimmermann, R.: Faster elliptic-curve discrete logarithms on FPGAs. Technical report, Cryptology eprint Archive, Report 2016/382 (2016)

Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_30 CrossRef

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 CrossRef

Bos, J.W., Kaihara, M.E., Kleinjung, T., Lenstra, A.K., Montgomery, P.L.: Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction. IJACT 2(3), 212–228 (2012). https://doi.org/10.1504/IJACT.2012.045590 MathSciNetCrossRefMATH

Certicom: the Certicom ECC challenge. https://www.certicom.com/content/dam/certicom/images/pdfs/challenge-2009.pdf. Accessed 10 Aug 2017

Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005)CrossRefMATH

Gallant, R., Lambert, R., Vanstone, S.: Improving the parallelized pollard lambda search on anomalous binary curves. Math. Comput. Am. Math. Soc. 69(232), 1699–1705 (2000)MathSciNetCrossRefMATH

Kajitani, S., Nogami, Y., Miyoshi, S., Austin, T., Al-Amin, K.M., Begum, N., Duquesne, S.: Web-based volunteer computing for solving the elliptic curve discrete logarithm problem. Int. J. Netw. Comput. 6(2), 181–194 (2016)CrossRef

10.

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_20 CrossRef

11.

Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1), 3–30 (1998). https://doi.org/10.1145/272991.272995 CrossRefMATH

12.

Miyoshi, S., Nogami, Y., Kusaka, T., Yamai, N.: Solving 94-bit ECDLP with 70 computers in parallel. Int. J. Comput. Electr. Autom. Control Inf. Eng. 9(8), 1966–1969 (2015)

13.

Montgomery, P.: Modular multiplication without trial division. Math. Comput. 44, 519–521 (1985)MathSciNetCrossRefMATH

14.

Montgomery, P.L.: Speeding the pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)MathSciNetCrossRefMATH

15.

Nogami, Y., Sakemi, Y., Okimoto, T., Nekado, K., Akane, M., Morikawa, Y.: Scalar multiplication using frobenius expansion over twisted elliptic curve for ate pairing based cryptography. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 92–A(1), 182–189 (2009)CrossRef

16.

Pollard, J.M.: Monte carlo methods for index computation (mod p). Math. Comput. 32(143), 918–924 (1978)MathSciNetMATH

17.

Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_27 CrossRef

18.

Sakai, R., Kasahara, M.: Id based cryptosystems with pairing on elliptic curve. IACR Cryptology ePrint Archive 2003, 54 (2003)

19.

Sakemi, Y., Nogami, Y., Okeya, K., Kato, H., Morikawa, Y.: Skew Frobenius map and efficient scalar multiplication for pairing–based cryptography. In: Franklin, M.K., Hui, L.C.K., Wong, D.S. (eds.) CANS 2008. LNCS, vol. 5339, pp. 226–239. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89641-8_16 CrossRef

20.

Van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999)MathSciNetCrossRefMATH

21.

Wenger, E., Wolfger, P.: Solving the discrete logarithm of a 113-bit Koblitz curve with an FPGA cluster. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 363–379. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13051-4_22 CrossRef

Titel: Solving 114-Bit ECDLP for a Barreto-Naehrig Curve
verfasst von: Takuya Kusaka
Sho Joichi
Ken Ikuta
Md. Al-Amin Khandaker
Yasuyuki Nogami
Satoshi Uehara
Nariyoshi Yamai
Sylvain Duquesne
Verlag: Springer International Publishing
Buch: Information Security and Cryptology – ICISC 2017
Print ISBN: 978-3-319-78555-4

Electronic ISBN: 978-3-319-78556-1

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78556-1_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"