You are looking at a specific version 20140221:173330 of this paper. See the latest version.

Paper 2014/119

Breaking `128-bit Secure' Supersingular Binary Curves (or how to solve discrete logarithms in $\F_{2^{4 \cdot 1223}}$ and $\F_{2^{12 \cdot 367}}$)

Robert Granger and 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 quasi-polynomial time algorithm, due to Barbulescu, Gaudry, Joux and Thomé. Using these developments, Adj, Menezes, Oliveira and Rodríguez-Henrí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. At the $128$-bit security level, they suggested that the new algorithms have no impact on the security of a genus one curve over $\F_{2^{1223}}$, and reduce the security of a genus two curve over $\F_{2^{367}}$ to $94.6$ bits. In this paper we propose a new field representation and efficient descent principles, which together demonstrate that the new techniques can be made practical at the 128-bit security level. In particular, we show that the aforementioned genus one curve offers only $59$ bits of security, and we report a total break of the genus two curve. Since these techniques are widely applicable, we conclude that small characteristic pairings should henceforth be considered completely insecure.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Discrete logarithm problemfinite fieldssupersingular binary curvespairings
Contact author(s)
robbiegranger @ gmail com
History
2014-06-12: last of 2 revisions
2014-02-21: received
See all versions
Short URL
https://ia.cr/2014/119
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.