Paper 2014/119
Breaking `128bit Secure' Supersingular Binary Curves (or how to solve discrete logarithms in ${\mathbb F}_{2^{4 \cdot 1223}}$ and ${\mathbb F}_{2^{12 \cdot 367}}$)
Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel
Abstract
In late 2012 and early 2013 the discrete logarithm problem (DLP) in finite fields of small characteristic underwent a dramatic series of breakthroughs, culminating in a heuristic quasipolynomial time algorithm, due to Barbulescu, Gaudry, Joux and Thomé. Using these developments, Adj, Menezes, Oliveira and RodríguezHenríquez analysed the concrete security of the DLP, as it arises from pairings on (the Jacobians of) various genus one and two supersingular curves in the literature, which were originally thought to be $128$bit secure. In particular, they suggested that the new algorithms have no impact on the security of a genus one curve over ${\mathbb F}_{2^{1223}}$, and reduce the security of a genus two curve over ${\mathbb F}_{2^{367}}$ to $94.6$ bits. In this paper we propose a new field representation and efficient general descent principles which together make the new techniques far more practical. Indeed, at the `128bit security level' our analysis shows that the aforementioned genus one curve has approximately $59$ bits of security, and we report a total break of the genus two curve.
Note: This is the full version of the CRYPTO 2014 paper.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 Discrete logarithm problemfinite fieldssupersingular binary curvespairings
 Contact author(s)
 robbiegranger @ gmail com
 History
 20140612: last of 2 revisions
 20140221: received
 See all versions
 Short URL
 https://ia.cr/2014/119
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/119, author = {Robert Granger and Thorsten Kleinjung and Jens Zumbrägel}, title = {Breaking `128bit Secure' Supersingular Binary Curves (or how to solve discrete logarithms in ${\mathbb F}_{2^{4 \cdot 1223}}$ and ${\mathbb F}_{2^{12 \cdot 367}}$)}, howpublished = {Cryptology ePrint Archive, Paper 2014/119}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/119}}, url = {https://eprint.iacr.org/2014/119} }