Forgot your password?
typodupeerror
Math Encryption

Discrete Logarithm Problem Partly Solved -- Time To Drop Some Crypto Methods? 114

Posted by Soulskill
from the now-let's-be-paranoid-that-the-NSA-solved-it-years-ago dept.
An anonymous reader points out this Science Daily report: "Researchers ... have solved one aspect of the discrete logarithm problem. This is considered to be one of the 'holy grails' of algorithmic number theory, on which the security of many cryptographic systems used today is based. They have devised a new algorithm that calls into question the security of one variant of this problem, which has been closely studied since 1976. The result ... discredits several cryptographic systems that until now were assumed to provide sufficient security safeguards. Although this work is still theoretical, it is likely to have repercussions especially on the cryptographic applications of smart cards, RFID chips , etc."
This discussion has been archived. No new comments can be posted.

Discrete Logarithm Problem Partly Solved -- Time To Drop Some Crypto Methods?

Comments Filter:
  • by l2718 (514756) on Saturday May 17, 2014 @12:46AM (#47023429)
    TFA links to the published version on SpringerLink, which is paywalled. A free preprint is available on the arXiv [arxiv.org].
  • by Sun (104778) <shachar@shemesh.biz> on Saturday May 17, 2014 @12:58AM (#47023455) Homepage

    Posted it as a question there already.

    Here's the thing, however. From reading the article, it seems that DH was not, itself, broken. Here's the problem, however: DH is used for forward reference security. It is used to ensure that an adversary that captured the encrypted communication cannot be decrypted later, even if the RSA key is later compromised

    Which means that whether DH has already been broken is a moot question. The real question is whether it is likely to be broken in the near future (where what "near" means depends on what you're actually encrypting).

    Here is what Schneier usually has to say about that: Attacks always get better over time.

    Of course, the main problem with replacing DH is that we don't really have anything better on hand.

    Shachar

  • It's still NP. (Score:5, Informative)

    by mark-t (151149) <markt@@@lynx...bc...ca> on Saturday May 17, 2014 @01:28AM (#47023565) Journal
    As I understand it, they've simplified the problem to a compiexity of O(n^log(n))... this is still non-polynomial time... but the rate of complexity growth is effectively polynomial. If I understand correctly, that means that the additional security that was formerly thought to be obtained by merely doubling cryptographic key length must now be obtained by squaring it.
  • Re:It's still NP. (Score:1, Informative)

    by WoOS (28173) on Saturday May 17, 2014 @03:22AM (#47023915)

    Please note that the algortihm is not O(n^log(n)) but n^O(log(n)). This puts the constant factor in the exponent which is a bit worse.

  • Re:It's still NP. (Score:4, Informative)

    by l2718 (514756) on Saturday May 17, 2014 @03:32AM (#47023953)
    Squaring key lengths would be entirely impractical. That said, the improvements only apply to a case of discrete log which isn't actually in use. Cryptographic algorithms generally depend on hardness of discrete log mod p (p a large prime), not in the field with p^k (p fixed, k large).

Top Ten Things Overheard At The ANSI C Draft Committee Meetings: (8) I'm on the committee and I *still* don't know what the hell #pragma is for.

Working...