Paper 2016/914
Computing discrete logarithms in cryptographicallyinteresting characteristicthree finite fields
Gora Adj, Isaac CanalesMartínez, Nareli CruzCortés, Alfred Menezes, Thomaz Oliveira, Luis RiveraZamarripa, and Francisco RodríguezHenríquez
Abstract
Since 2013 there have been several developments in algorithms for computing discrete logarithms in smallcharacteristic finite fields, culminating in a quasipolynomial algorithm. In this paper, we report on our successful computation of discrete logarithms in the cryptographicallyinteresting characteristicthree finite field ${\mathbb F}_{3^{6 \cdot 509}}$ using these new algorithms; prior to 2013, it was believed that this field enjoyed a security level of 128 bits. We also show that a recent idea of Guillevic can be used to compute discrete logarithms in the cryptographicallyinteresting finite field ${\mathbb F}_{3^{6 \cdot 709}}$ using essentially the same resources as we expended on the ${\mathbb F}_{3^{6 \cdot 509}}$ computation. Finally, we argue that discrete logarithms in the finite field ${\mathbb F}_{3^{6 \cdot 1429}}$ can feasibly be computed today; this is significant because this cryptographicallyinteresting field was previously believed to enjoy a security level of 192 bits.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 discrete logarithm problembilinear pairingscryptanalysisimplementation
 Contact author(s)
 francisco @ cs cinvestav mx
 History
 20160922: received
 Short URL
 https://ia.cr/2016/914
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/914, author = {Gora Adj and Isaac CanalesMartínez and Nareli CruzCortés and Alfred Menezes and Thomaz Oliveira and Luis RiveraZamarripa and Francisco RodríguezHenríquez}, title = {Computing discrete logarithms in cryptographicallyinteresting characteristicthree finite fields}, howpublished = {Cryptology ePrint Archive, Paper 2016/914}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/914}}, url = {https://eprint.iacr.org/2016/914} }