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)
- 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
-
CC BY