Paper 2012/345

Breaking pairing-based cryptosystems using ηT pairing over GF(397)

Takuya Hayashi, Takeshi Shimoyama, Naoyuki Shinohara, and Tsuyoshi Takagi

Abstract

There are many useful cryptographic schemes, such as ID-based encryption, short signature, keyword searchable encryption, attribute-based encryption, functional encryption, that use a bilinear pairing. It is important to estimate the security of such pairing-based cryptosystems in cryptography. The most essential number-theoretic problem in pairing-based cryptosystems is the discrete logarithm problem (DLP) because pairing-based cryptosystems are no longer secure once the underlining DLP is broken. One efficient bilinear pairing is the pairing defined over a supersingular elliptic curve on the finite field for a positive integer . The embedding degree of the pairing is ; thus, we can reduce the DLP over on to that over the finite field . In this paper, for breaking the pairing over , we discuss solving the DLP over by using the function field sieve (FFS), which is the asymptotically fastest algorithm for solving a DLP over finite fields of small characteristics. We chose the extension degree because it has been intensively used in benchmarking tests for the implementation of the pairing, and the order (923-bit) of 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 (JL06-FFS), and propose several improvements of the FFS, for example, the lattice sieve for JL06-FFS and the filtering adjusted to the Galois action. Finally, we succeeded in solving the DLP over . The entire computational time of our improved FFS requires about 148.2 days using 252 CPU cores. Our computational results contribute to the secure use of pairing-based cryptosystems with the pairing.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
pairing-based cryptosystems pairingdiscrete logarithm problemsfunction filed sieve
Contact author(s)
t-hayashi @ math kyushu-u ac jp
History
2012-06-22: received
Short URL
https://ia.cr/2012/345
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/345,
      author = {Takuya Hayashi and Takeshi Shimoyama and Naoyuki Shinohara and Tsuyoshi Takagi},
      title = {Breaking pairing-based cryptosystems using $\e{ta_T}$ pairing over ${GF}(3^{97})$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/345},
      year = {2012},
      url = {https://eprint.iacr.org/2012/345}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.