[math-fun] Discrete Logarithm Problem Partly Solved -- Time To Drop Some Crypto Methods?
http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-p... <http://beta.slashdot.org/%7ESoulskill>Soulskill posted yesterday | from the now-let's-be-paranoid-that-the-NSA-solved-it-years-ago dept. <http://beta.slashdot.org/index2.pl?fhfilter=math> Math <http://beta.slashdot.org/index2.pl?fhfilter=math> <http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-problem-partly-solved----time-to-drop-some-crypto-methods>97 An anonymous reader points out this Science Daily report: "Researchers ... have solved one aspect of the <http://modular.math.washington.edu/edu/124/lectures/lecture8/html/node5.html>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 <http://www.sciencedaily.com/releases/2014/05/140515163739.htm>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." --- co-chair http://ocjug.org/
http://eprint.iacr.org/2013/400.pdf On Sat, May 17, 2014 at 4:24 PM, Ray Tayek <rtayek@ca.rr.com> wrote:
http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-p...
<http://beta.slashdot.org/%7ESoulskill>Soulskill posted yesterday | from the now-let's-be-paranoid-that-the-NSA-solved-it-years-ago dept.
<http://beta.slashdot.org/index2.pl?fhfilter=math> Math
<http://beta.slashdot.org/index2.pl?fhfilter=math> <http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-problem-partly-solved----time-to-drop-some-crypto-methods>97
An anonymous reader points out this Science Daily report: "Researchers ... have solved one aspect of the <http://modular.math.washington.edu/edu/124/lectures/lecture8/html/node5.html>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 <http://www.sciencedaily.com/releases/2014/05/140515163739.htm>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."
--- co-chair http://ocjug.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
I don't think this is new. See: http://blog.cryptographyengineering.com/2013/08/is-cryptopocalypse-nigh.html for Schneier's comments. He observes that we'll know when there's something to worry about when cryptographers are running around like their hair is on fire. Regards, Jon
Schneier should now be smelling burnt hair: "In this [Joux2014] work, we present a new discrete logarithm algorithm, in the same vein as in [Joux2013] that uses an asymptotically more efficient descent approach. The main result gives a quasi-polynomial heuristic complexity for the DLP in finite fields of small characteristic. ... It remains super-polynomial in the size of the input, but offers a major asymptotic improvement compared to [Joux2013]." The cool thing about this research is the beautiful new mathematics. Although DLP's may not be useful for crypto much longer, I fully expect them to be useful for many other things in the future. At 09:11 AM 5/18/2014, Jon Ziegler wrote:
I don't think this is new. See: http://blog.cryptographyengineering.com/2013/08/is-cryptopocalypse-nigh.html for Schneier's comments. He observes that we'll know when there's something to worry about when cryptographers are running around like their hair is on fire.
I've seen various older references (Dickson 1931, Herstein & Kaplansky 1978), citing evidence that every positive integer is the sum of no more than 37 positive 5th powers (with, e.g., 223 requiring that many). But I haven't seen a claim that this has been proved. Can anyone please say whether this has been proved or not?* Thanks, Dan _________________________________________________________________________ * I'm also curious about the number proposed h(n) by Herstein & Kaplansky as the Waring number for all nth powers -- has this been proved to be the exact maximum number of nth powers needed to represent any positive integer? But for the moment I'm much more interested in 5th powers.
I did find a paper (undated, but with latest reference from 2001) stating that the fifth power problem had been solved by 1964, by Chen Jing-Run: As the result of the work of many mathematicians we now know that g(k) [the number of positive kth powers necessary to represent any positive integer] is determined by: (*) g(k) = 2^k + [(3/2)^k] - 2 provided that (**) 2^k {(3/2)^k} + [(3/2)^k] <= 2^k; if this fails, then g(k) = 2^k + [(3/2)^k] + [(4/3)^k] - theta where theta is 2 or 3 according as the quantity [(4/3)^k] [(3/2)^k] + [(4/3)^k] + [(3/2)^k] equals or exceeds 2^k. It is conjectured that (**) always holds, in which case (*) would always hold. It's known that (**) holds for k <= 471,600,000, and that there are at most a finite number of exceptions. To show that (**) always holds, says this paper, it would suffice to prove that (***) {(3/4)^k} <= 1 - (3/4)^(k-1) . (Where {} is the fractional part, and [] is the greatest integer function.) Hmm, (***) sounds so deceptively simple! --Dan On May 18, 2014, at 10:44 AM, Dan Asimov <dasimov@earthlink.net> wrote:
I've seen various older references (Dickson 1931, Herstein & Kaplansky 1978), citing evidence that every positive integer is the sum of no more than 37 positive 5th powers (with, e.g., 223 requiring that many).
But I haven't seen a claim that this has been proved.
Can anyone please say whether this has been proved or not?*
Thanks,
Dan _________________________________________________________________________ * I'm also curious about the number proposed h(n) by Herstein & Kaplansky as the Waring number for all nth powers -- has this been proved to be the exact maximum number of nth powers needed to represent any positive integer?
But for the moment I'm much more interested in 5th powers.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On May 18, 2014, at 9:47 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Schneier should now be smelling burnt hair:
Seems he isn't: Despite headlines to the contrary, this does not have any cryptanalytic application -- unless they can generalize the result, which seems unlikely to me. See: https://www.schneier.com/blog/archives/2014/05/advances_in_sol.html Of course he might be wrong.... Regards, Jon
"In this [Joux2014] work, we present a new discrete logarithm algorithm, in the same vein as in [Joux2013] that uses an asymptotically more efficient descent approach. The main result gives a quasi-polynomial heuristic complexity for the DLP in finite fields of small characteristic. ... It remains super-polynomial in the size of the input, but offers a major asymptotic improvement compared to [Joux2013]."
The cool thing about this research is the beautiful new mathematics. Although DLP's may not be useful for crypto much longer, I fully expect them to be useful for many other things in the future.
At 09:11 AM 5/18/2014, Jon Ziegler wrote:
I don't think this is new. See: http://blog.cryptographyengineering.com/2013/08/is-cryptopocalypse-nigh.html for Schneier's comments. He observes that we'll know when there's something to worry about when cryptographers are running around like their hair is on fire.
All of this seems to be about solving the DLP in fields of order p^k, where p is small and k is large. The crypto systems I've seen that use DLP all use p large and k=1, so these new algorithms seem irrelevant to that case. Andy On Sat, May 17, 2014 at 6:24 PM, Ray Tayek <rtayek@ca.rr.com> wrote:
http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-p...
<http://beta.slashdot.org/%7ESoulskill>Soulskill posted yesterday | from the now-let's-be-paranoid-that-the-NSA-solved-it-years-ago dept.
<http://beta.slashdot.org/index2.pl?fhfilter=math> Math
<http://beta.slashdot.org/index2.pl?fhfilter=math> <http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-problem-partly-solved----time-to-drop-some-crypto-methods>97
An anonymous reader points out this Science Daily report: "Researchers ... have solved one aspect of the <http://modular.math.washington.edu/edu/124/lectures/lecture8/html/node5.html>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 <http://www.sciencedaily.com/releases/2014/05/140515163739.htm>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."
--- co-chair http://ocjug.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
That's my understanding as well: this is irrelevant to crypto because it doesn't apply to GF(p), just GF(p^k) for k large compared to log p. Charles Greathouse Analyst/Programmer Case Western Reserve University On Sun, May 18, 2014 at 2:10 PM, Andy Latto <andy.latto@pobox.com> wrote:
All of this seems to be about solving the DLP in fields of order p^k, where p is small and k is large. The crypto systems I've seen that use DLP all use p large and k=1, so these new algorithms seem irrelevant to that case.
Andy
On Sat, May 17, 2014 at 6:24 PM, Ray Tayek <rtayek@ca.rr.com> wrote:
http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-p...
<http://beta.slashdot.org/%7ESoulskill>Soulskill posted yesterday |
from the
now-let's-be-paranoid-that-the-NSA-solved-it-years-ago dept.
<http://beta.slashdot.org/index2.pl?fhfilter=math> Math
<http://beta.slashdot.org/index2.pl?fhfilter=math> < http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-p... 97
An anonymous reader points out this Science Daily report: "Researchers ... have solved one aspect of the < http://modular.math.washington.edu/edu/124/lectures/lecture8/html/node5.html 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 <http://www.sciencedaily.com/releases/2014/05/140515163739.htm>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."
--- co-chair http://ocjug.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (7)
-
Andy Latto -
Charles Greathouse -
Dan Asimov -
Henry Baker -
Jon Ziegler -
Mike Stay -
Ray Tayek