Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Breaking Pairing-Based Cryptosystems UsingηT Pairing overGF(397)

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 7658))

  • 3991Accesses

  • 28Citations

Abstract

In this paper, we discuss solving the DLP overGF(36·97) by using the function field sieve (FFS) for breaking paring-based cryptosystems using theηT pairing overGF(397). The extension degree 97 has been intensively used in benchmarking tests for the implementation of theηT pairing, and the order (923-bit) ofGF(36·97) is substantially larger than the previous world record (676-bit) of solving the DLP by using the FFS. We implemented the FFS for the medium prime case, and proposed several improvements of the FFS. Finally, we succeeded in solving the DLP overGF(36·97). The entire computational time requires about 148.2 days using 252 CPU cores.

The full-version of this paper is appeared in [19].

Similar content being viewed by others

Keywords

References

  1. Adleman, L.M.: The Function Field Sieve. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol. 877, pp. 108–121. Springer, Heidelberg (1994)

    Chapter  Google Scholar 

  2. Adleman, L.M., Huang, M.-D.A.: Function field sieve method for discrete logarithms over finite fields. Inform. and Comput. 151, 5–16 (1999)

    Article MathSciNet MATH  Google Scholar 

  3. Ahmadi, O., Hankerson, D., Menezes, A.: Software Implementation of Arithmetic in\(F_{3^m}\). In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547, pp. 85–102. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  4. Aoki, K., Shimoyama, T., Ueda, H.: Experiments on the Linear Algebra Step in the Number Field Sieve. In: Miyaji, A., Kikuchi, H., Rannenberg, K. (eds.) IWSEC 2007. LNCS, vol. 4752, pp. 58–73. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  5. Barreto, P.S.L.M., Galbraith, S., ÓhÉigeartaigh, C., Scott, M.: Efficient pairing computation on supersingular Abelian varieties. Des., Codes Cryptogr. 42(3), 239–271 (2007)

    Article MathSciNet MATH  Google Scholar 

  6. Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient Algorithms for Pairing-Based Cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 354–368. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  7. Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E.: Arithmetic Operators for Pairing-Based Cryptography. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 239–255. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  8. Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E., Shirase, M., Takagi, T.: Algorithms and arithmetic operators for computing theηT pairing in characteristic three. IEEE Trans. Comput. 57(11), 1454–1468 (2008)

    Article MathSciNet  Google Scholar 

  9. Beuchat, J.-L., Brisebarre, N., Shirase, M., Takagi, T., Okamoto, E.: A Coprocessor for the Final Exponentiation of theηT Pairing in Characteristic Three. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547, pp. 25–39. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  10. 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)

    Chapter  Google Scholar 

  11. 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)

    Chapter  Google Scholar 

  12. 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)

    Google Scholar 

  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)

    Chapter  Google Scholar 

  14. 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. International Journal of Applied Cryptography 2(3), 212–228 (2012)

    Article MathSciNet MATH  Google Scholar 

  15. Cavallar, S.: Strategies in Filtering in the Number Field Sieve. In: Bosma, W. (ed.) ANTS-IV. LNCS, vol. 1838, pp. 209–231. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  16. Gordon, D.M., McCurley, K.S.: Massively Parallel Computation of Discrete Logarithms. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 312–323. Springer, Heidelberg (1993)

    Google Scholar 

  17. Granger, R., Page, D., Stam, M.: Hardware and software normal basis arithmetic for pairing-based cryptography in characteristic three. IEEE Trans. Comput. 54(7), 852–860 (2005)

    Article  Google Scholar 

  18. Hankerson, D., Menezes, A., Scott, M.: Software implementation of pairings. In: Identity-Based Cryptography, pp. 188–206 (2009)

    Google Scholar 

  19. Hayashi, T., Shimoyama, T., Shinohara, N., Takagi, T.: Breaking pairing-based cryptosystems usingηT pairing overGF(397). Cryptology ePrint Archive, Report 2012/345 (2012)

    Google Scholar 

  20. Hayashi, T., Shinohara, N., Wang, L., Matsuo, S., Shirase, M., Takagi, T.: Solving a 676-bit Discrete Logarithm Problem inGF(36n). In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 351–367. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  21. Joux, A.: A One Round Protocol for Tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS-IV. LNCS, vol. 1838, pp. 385–394. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  22. Joux, A., et al.: Discrete logarithms in GF(2607) and GF(2613). Posting to the Number Theory List (2005),http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0509&L=nmbrthry&T=0&P=3690

  23. Joux, A., Lercier, R.: The Function Field Sieve Is Quite Special. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol. 2369, pp. 431–445. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  24. Joux, A., Lercier, R.: The Function Field Sieve in the Medium Prime Case. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 254–270. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  25. Kawahara, Y., Aoki, K., Takagi, T.: Faster Implementation ofηT Pairing overGF(3m) Using Minimum Number of Logical Instructions forGF(3)-addition. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 282–296. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  26. 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., 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)

    Google Scholar 

  27. Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. IT 39(5), 1639–1646 (1993)

    Article MathSciNet MATH  Google Scholar 

  28. Okamoto, T., Takashima, K.: Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 191–208. Springer, Heidelberg (2010)

    Google Scholar 

  29. Pollard, J.M.: The lattice sieve. In: The development of the number field sieve. LNIM, vol. 1554, pp. 43–49 (1993)

    Google Scholar 

  30. Sahai, A., Waters, B.: Fuzzy Identity-Based Encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  31. Shinohara, N., Shimoyama, T., Hayashi, T., Takagi, T.: Key Length Estimation of Pairing-Based Cryptosystems usingηT Pairing. In: Ryan, M.D., Smyth, B., Wang, G. (eds.) ISPEC 2012. LNCS, vol. 7232, pp. 228–244. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Kyushu University, Japan

    Takuya Hayashi & Tsuyoshi Takagi

  2. FUJITSU LABORATORIES Ltd., Japan

    Takeshi Shimoyama

  3. National Institute of Information and Communications Technology, Japan

    Naoyuki Shinohara

Authors
  1. Takuya Hayashi
  2. Takeshi Shimoyama
  3. Naoyuki Shinohara
  4. Tsuyoshi Takagi

Editor information

Editors and Affiliations

  1. Tsinghua University, 30 Shuangqing Road, 100084, Beijing, China

    Xiaoyun Wang

  2. Central Research Laboratories, NEC, 1754 Shimonumabe Nakahara, 211-8666, Kawasaki, Japan

    Kazue Sako

Rights and permissions

Copyright information

© 2012 International Association for Cryptologic Research

About this paper

Cite this paper

Hayashi, T., Shimoyama, T., Shinohara, N., Takagi, T. (2012). Breaking Pairing-Based Cryptosystems UsingηT Pairing overGF(397). In: Wang, X., Sako, K. (eds) Advances in Cryptology – ASIACRYPT 2012. ASIACRYPT 2012. Lecture Notes in Computer Science, vol 7658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34961-4_5

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp