Hacker News new | past | comments | ask | show | jobs | submit login
Computing Discrete Logarithms [pdf] (iacr.org)
49 points by nanis 37 days ago | hide | past | favorite | 3 comments



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


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.


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: