Paper 2015/1179
A construction of 3-dimensional lattice sieve for number field sieve over F_{p^n}
Kenichiro Hayasaka, Kazumaro Aoki, Tetsutaro Kobayashi, and Tsuyoshi Takagi
Abstract
The security of pairing-based cryptography is based on the hardness of solving the discrete logarithm problem (DLP) over extension field F_{p^n} of characteristic p and degree n. Joux et al. proposed an asymptotically fastest algorithm for solving DLP over F_{p^n} (JLSV06-NFS) as the extension of the number field sieve over prime field F _p (JL03-NFS). The lattice sieve is often used for a large-scaled experiment of solving DLP over F_p by the number field sieve. Franke and Kleinjung proposed a 2-dimensional lattice sieve which efficiently enumerates all the points in a given sieve region of the lattice. However, we have to consider a sieve region of more than 2 dimensions in the lattice sieve of JLSV06-NFS. In this paper, we extend the Franke-Kleinjung method to 3-dimensional sieve region. We construct an appropriate basis using the Hermite normal form, which can enumerate the points in a given sieve region of the 3-dimensional lattice. From our experiment on F_{p^{12}} of 303 bits, we are able to enumerate more than 90\% of the points in a sieve region in the lattice generated by special-q. Moreover, we implement the number field sieve using the proposed 3-dimensional lattice sieve. Our implementation of the JLSV06 over F_{p^6} of 240 bits is about as efficient as that of the current record over F_{p^6} using 3-dimensional line sieve by Zajac.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- number field sieve
- Contact author(s)
- takagi @ imi kyushu-u ac jp
- History
- 2015-12-10: received
- Short URL
- https://ia.cr/2015/1179
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/1179,
author = {Kenichiro Hayasaka and Kazumaro Aoki and Tetsutaro Kobayashi and Tsuyoshi Takagi},
title = {A construction of 3-dimensional lattice sieve for number field sieve over F_{p^n}},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/1179},
year = {2015},
url = {https://eprint.iacr.org/2015/1179}
}