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

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."

arXiv link (to the technical paper)

[l2718]

TFA links to the published version on SpringerLink, which is paywalled. A free preprint is available on the arXiv [arxiv.org].

Re:Is Diffie Hellman at risk?

[Sun]

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.

[mark-t]

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.

[WoOS]

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.

[l2718]

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).