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

*Takuya Hayashi and Takeshi Shimoyama and 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.

**Category / Keywords: **public-key cryptography / pairing-based cryptosystems, $\eta_T$ pairing, discrete logarithm problems, function filed sieve

**Date: **received 17 Jun 2012

**Contact author: **t-hayashi at math kyushu-u ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20120622:195420 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]