Welcome to the resource topic for 2012/345
Title:
Breaking pairing-based cryptosystems using \eta_T pairing over GF(3^{97})
Authors: Takuya Hayashi, Takeshi Shimoyama, Naoyuki Shinohara, 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 \eta_T pairing defined over a supersingular elliptic curve E on the finite field GF(3^n) for a positive integer n. The embedding degree of the \eta_T pairing is 6; thus, we can reduce the DLP over E on GF(3^n) to that over the finite field GF(3^{6n}). In this paper, for breaking the \eta_T pairing over GF(3^n), we discuss solving the DLP over GF(3^{6n}) 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 n=97 because it has been intensively used in benchmarking tests for the implementation of the \eta_T pairing, and the order (923-bit) of GF(3^{6\cdot 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 (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 GF(3^{6\cdot 97}). 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 \eta_T pairing.
ePrint: https://eprint.iacr.org/2012/345
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .