Paper 2012/042

Key Length Estimation of Pairing-based Cryptosystems using $\eta_T$ Pairing

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


The security of pairing-based cryptosystems depends on the difficulty of the discrete logarithm problem (DLP) over certain types of finite fields. One of the most efficient algorithms for computing a pairing is the $\eta_T$ pairing over supersingular curves on finite fields whose characteristic is $3$. Indeed many high-speed implementations of this pairing have been reported, and it is an attractive candidate for practical deployment of pairing-based cryptosystems. The embedding degree of the $\eta_T$ pairing is 6, so we deal with the difficulty of a DLP over the finite field $ GF(3^{6n})$, where the function field sieve (FFS) is known as the asymptotically fastest algorithm of solving it. Moreover, several efficient algorithms are employed for implementation of the FFS, such as the large prime variation. In this paper, we estimate the time complexity of solving the DLP for the extension degrees $n=97,163, 193,239,313,353,509$, when we use the improved FFS. To accomplish our aim, we present several new computable estimation formulas to compute the explicit number of special polynomials used in the improved FFS. Our estimation contributes to the evaluation for the key length of pairing-based cryptosystems using the $\eta_T$ pairing.

Note: Table 1 and 3 are edited.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. This is a full version of ISPEC 2012 paper.
pairing-based cryptosystemsdiscrete logarithm problemfinite fieldkey lengthsuitable values
Contact author(s)
shnhr @ nict go jp
2012-06-19: revised
2012-01-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Naoyuki Shinohara and Takeshi Shimoyama and Takuya Hayashi and Tsuyoshi Takagi},
      title = {Key Length Estimation of Pairing-based Cryptosystems using $\eta_T$ Pairing},
      howpublished = {Cryptology ePrint Archive, Paper 2012/042},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.