**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.

**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 ]