The maths is a bit too dense for me to read through it all easily and understandingly, but in case anyone is wondering, this doesn't appear to be a new breakthrough or "ECDH is broken" or anything of that nature.
Abstract: We describe some cryptographically relevant discrete logarithm problems (DLPs) and present some of the key ideas and constructions behind the most efficient algorithms known that solve them. Since the topic encompasses such a large volume of literature, for the finite field DLP we limit ourselves to a selection of results reflecting recent advances in fixed characteristic finite fields.
This is a chapter of an academic book, and a survey of constructions and attacks on the various DLs (the most notable two classes of those constructions are multiplicative group "classic" Diffie Hellman and elliptic curves --- ECDH and ECC signatures). I'm less† familiar with Granger, but Joux is one of the most famous research cryptographers working on curves and discrete log problems more generally.
This is a pretty neat survey and includes a lot of stuff you're not going to run into in practical, deployed, conventional systems (it'll also give you some pointers to background behind things in SafeCurves).
A choice quote:
Progress in cryptanalytic algorithms, just as in science more
generally, usually evolves by small increments but with occasional
revolutionary steps forward [54]. One example of such a step
forward could arguably be the rapid development of efficient
algorithms for solving the DLP in finite fields of fixed
characteristic, that took place from late 2012 to mid 2014, thanks
to the present authors and their collaborators. Between these
times, the fastest algorithm for solving this problem went from
having complexity L(1/3) to being quasi-polynomial, rendering such
fields entirely unsuitable for discrete logarithm-based
cryptography, including pairing-based cryptography over small
characteristic supersingular curves. These events constitute a
perfect example of Prof. Lenstra’s (perhaps jocular, but no doubt
in part quite serious) contention that no problem based on number
theory should ever be considered truly secure, even if it has
remained impenetrable for several decades.
3 comments
[ 5.3 ms ] story [ 19.3 ms ] threadThis is a pretty neat survey and includes a lot of stuff you're not going to run into in practical, deployed, conventional systems (it'll also give you some pointers to background behind things in SafeCurves).
A choice quote:
† ie: not