IEICE TRANSACTIONS on Fundamentals
Key Length Estimation of Pairing-Based Cryptosystems Using ηT Pairing over GF(3n)
Summary :
The security of pairing-based cryptosystems is determined by the difficulty of solving the discrete logarithm problem (DLP) over certain types of finite fields. One of the most efficient algorithms for computing a pairing is the ηT pairing over supersingular curves on finite fields of characteristic 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. Since the embedding degree of the ηT pairing is 6, we deal with the difficulty of solving a DLP over the finite field GF(36n), 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, and 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 ηT pairing.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.1 pp.236-244
- Publication Date
- 2014/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.236
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
- Foundations
Authors
Naoyuki SHINOHARA
National Institute of Information and Communications Technology
Takeshi SHIMOYAMA
FUJITSU LABORATORIES Ltd.
Takuya HAYASHI
Kyushu University
Tsuyoshi TAKAGI
Kyushu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Naoyuki SHINOHARA, Takeshi SHIMOYAMA, Takuya HAYASHI, Tsuyoshi TAKAGI, "Key Length Estimation of Pairing-Based Cryptosystems Using ηT Pairing over GF(3n)" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 1, pp. 236-244, January 2014, doi: 10.1587/transfun.E97.A.236.
Abstract: The security of pairing-based cryptosystems is determined by the difficulty of solving the discrete logarithm problem (DLP) over certain types of finite fields. One of the most efficient algorithms for computing a pairing is the ηT pairing over supersingular curves on finite fields of characteristic 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. Since the embedding degree of the ηT pairing is 6, we deal with the difficulty of solving a DLP over the finite field GF(36n), 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, and 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 ηT pairing.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.236/_p
Copy
@ARTICLE{e97-a_1_236,
author={Naoyuki SHINOHARA, Takeshi SHIMOYAMA, Takuya HAYASHI, Tsuyoshi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Key Length Estimation of Pairing-Based Cryptosystems Using ηT Pairing over GF(3n)},
year={2014},
volume={E97-A},
number={1},
pages={236-244},
abstract={The security of pairing-based cryptosystems is determined by the difficulty of solving the discrete logarithm problem (DLP) over certain types of finite fields. One of the most efficient algorithms for computing a pairing is the ηT pairing over supersingular curves on finite fields of characteristic 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. Since the embedding degree of the ηT pairing is 6, we deal with the difficulty of solving a DLP over the finite field GF(36n), 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, and 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 ηT pairing.},
keywords={},
doi={10.1587/transfun.E97.A.236},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Key Length Estimation of Pairing-Based Cryptosystems Using ηT Pairing over GF(3n)
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 236
EP - 244
AU - Naoyuki SHINOHARA
AU - Takeshi SHIMOYAMA
AU - Takuya HAYASHI
AU - Tsuyoshi TAKAGI
PY - 2014
DO - 10.1587/transfun.E97.A.236
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2014
AB - The security of pairing-based cryptosystems is determined by the difficulty of solving the discrete logarithm problem (DLP) over certain types of finite fields. One of the most efficient algorithms for computing a pairing is the ηT pairing over supersingular curves on finite fields of characteristic 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. Since the embedding degree of the ηT pairing is 6, we deal with the difficulty of solving a DLP over the finite field GF(36n), 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, and 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 ηT pairing.
ER -
English
