University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Breaking '128-bit Secure' Supersingular Binary Curves

Granger, Robert, Kleinjung, Thorsten and Zumbrägel, Jens (2014) Breaking '128-bit Secure' Supersingular Binary Curves In: 34th Annual Cryptology Conference - Advances in Cryptology (CRYPTO 2014), 17-21 Aug 2014, Santa Barbara, CA, USA.

RG_Final_eprint.pdf - Accepted version Manuscript

Download (463kB) | Preview


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, 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 F21223 , and reduce the security of a genus two curve over F2367 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 ‘128-bit 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

Item Type: Conference or Workshop Item (Conference Paper)
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
Kleinjung, Thorsten
Zumbrägel, Jens
Date : 17 August 2014
DOI : 10.1007/978-3-662-44381-1_8
Copyright Disclaimer : © International Association for Cryptologic Research 2014
Uncontrolled Keywords : Discrete logarithm problem; Supersingular binary curves; Pairings; Finite fields
Depositing User : Clive Harris
Date Deposited : 07 Feb 2019 11:27
Last Modified : 17 Apr 2019 09:05

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800