Cryptology ePrint Archive: Report 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\"agel

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\'e. Using these developments, Adj, Menezes, Oliveira and Rodr\'iguez-Henr\'iquez 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.

Category / Keywords: public-key cryptography / Discrete logarithm problem, finite fields, supersingular binary curves, pairings

Date: received 14 Feb 2014, last revised 14 Feb 2014

Contact author: robbiegranger at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140221:173330 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]