TY - CHAP

T1 - An experiment of number field sieve for discrete logarithm problem over GF(p12)

AU - Hayasaka, Kenichiro

AU - Aoki, Kazumaro

AU - Kobayashi, Tetsutaro

AU - Takagi, Tsuyoshi

PY - 2013

Y1 - 2013

N2 - The security of pairing-based cryptography is based on the hardness of the discrete logarithm problem (DLP) over finite field GF(pn). For example, the security of the optimal Ate pairing using BN curves, which is one of the most efficient algorithms for computing paring, is based on the hardness of DLP over GF(p12). Joux et al. proposed the number field sieve over GF(pn) as an extension of the number field sieve that can efficiently solve the DLP over prime field GF(p). Two implementations of the number field sieve over GF(p3) and GF(p6) have been proposed, but there is no report on that over GF(p12) of extension degree 12. In the sieving step of the number field sieve over GF(p) we perform the sieving of two dimensions, but we have to deal with more than two dimensions in the case of number field sieves over GF(p12). In this paper we construct a lattice sieve of more than two dimensions, and discuss its parameter sizes such as the dimension of sieving and the size of sieving region from some experiments of the multi-dimensional sieving. Using the parameters suitable for efficient implementation of the number field sieve, we have solved the DLP over GF(p12) of 203 bits in about 43 hours using a PC of 16 CPU cores.

AB - The security of pairing-based cryptography is based on the hardness of the discrete logarithm problem (DLP) over finite field GF(pn). For example, the security of the optimal Ate pairing using BN curves, which is one of the most efficient algorithms for computing paring, is based on the hardness of DLP over GF(p12). Joux et al. proposed the number field sieve over GF(pn) as an extension of the number field sieve that can efficiently solve the DLP over prime field GF(p). Two implementations of the number field sieve over GF(p3) and GF(p6) have been proposed, but there is no report on that over GF(p12) of extension degree 12. In the sieving step of the number field sieve over GF(p) we perform the sieving of two dimensions, but we have to deal with more than two dimensions in the case of number field sieves over GF(p12). In this paper we construct a lattice sieve of more than two dimensions, and discuss its parameter sizes such as the dimension of sieving and the size of sieving region from some experiments of the multi-dimensional sieving. Using the parameters suitable for efficient implementation of the number field sieve, we have solved the DLP over GF(p12) of 203 bits in about 43 hours using a PC of 16 CPU cores.

UR - http://www.scopus.com/inward/record.url?scp=84893372104&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893372104&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-42001-6_8

DO - 10.1007/978-3-642-42001-6_8

M3 - Chapter

AN - SCOPUS:84893372104

SN - 9783642420009

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 108

EP - 120

BT - Number Theory and Cryptography

A2 - Fischlin, Marc

A2 - Katzenbeisser, Stefan

ER -