3 ms·

Computing Discrete Logarithms [pdf]

49 points by nanis 5y ago

userbinator 5y ago
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.
doomrobo 5y ago
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.
tptacek 5y ago
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. † ie: not

49 points by nanis 5y ago

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.

doomrobo 5y ago

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.

tptacek 5y ago

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. † ie: not