Paper 2016/507

Solving discrete logarithms on a 170-bit MNT curve by pairing reduction

Aurore Guillevic, François Morain, and Emmanuel Thomé

Abstract

Pairing based cryptography is in a dangerous position following the breakthroughs on discrete logarithms computations in finite fields of small characteristic. Remaining instances are built over finite fields of large characteristic and their security relies on the fact the embedding field of the underlying curve is relatively large. How large is debatable. The aim of our work is to sustain the claim that the combination of degree 3 embedding and too small finite fields obviously does not provide enough security. As a computational example, we solve the DLP on a 170-bit MNT curve, by exploiting the pairing embedding to a 508-bit, degree-3 extension of the base field.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Discrete logarithmfinite fieldnumber field sieveMNT elliptic curve
Contact author(s)
aurore guillevic @ ucalgary ca
History
2016-05-25: received
Short URL
https://ia.cr/2016/507
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/507,
      author = {Aurore Guillevic and François Morain and Emmanuel Thomé},
      title = {Solving discrete logarithms on a 170-bit MNT curve by pairing reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2016/507},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/507}},
      url = {https://eprint.iacr.org/2016/507}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.