Paper 2012/345

Breaking pairing-based cryptosystems using $\eta_T$ pairing over $GF(3^{97})$

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 $\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.