18 ms·

Factoring may be easier than we think

89 points by vinchuco 10y ago

eschutte2 10y ago
In addition to which, of those 100, some of the ones with the strongest incentive to crack factoring work for places with a strong disincentive to publish their results. EDIT: Missed the sentence in the article where this is hinted at.
eximius 10y ago
He's not wrong, but that doesn't make him right.
- Animats 10y ago
  He makes the good point that factoring is already below exponential time, and there's been progress over the years in speeding it up. Even if someone doesn't develop a polynomial time algorithm, there still could be substantial progress. There's also the possibility of new algorithms which are fast for some products of two primes, but not all. There are lots of problems, such as linear programming, where the worst case is exponential but the average case is far faster. Even something that allowed easy factoring of only 1% of products of two primes would be useful to an attacker.
  - eximius 10y ago
    I'm not too terribly worried. There are enough efforts to look for post-quantum crypto algorithms that I think by the time we come up with something that actually threatens factoring, we'll have alternatives. If quantum stuff comes first, then we can go to lattice based systems (which are the leading candidate as far as I know - please correct me otherwise, I am familiar with lattice based systems but have not done research for a better base). If factoring is solved first, we can stick with elliptic curves.
    - coldtea 10y ago
      >I'm not too terribly worried. There are enough efforts to look for post-quantum crypto algorithms that I think by the time we come up with something that actually threatens factoring, we'll have alternatives. That's hardly a consolation, since all that we've encrypted and shared until then will be trivial to break as long as people have them in encrypted form (which is very easy to do).
      - eximius 10y ago
        That is sort of inevitable, I think. Best case, it is never broken and we never get quantum computers, but I hope that doesn't come to pass. So the next best case is that most of the details recovered by such breakage are irrelevent to those still alive. I think thats far more likely anyway.
- coldtea 10y ago
  He doesn't maintain he is right, so that's beside the point. His main claim is that others that say it's hard are not necessarily right either, and have no proof for that.
mofreek 10y ago
tl;dr: I don't have any evidence this is true, but there's no counter evidence either.
tokenadult 10y ago
"Of course, I have no real evidence for my views; if I had any good ideas for factoring, I'd be working on them instead of writing this. On the other hand, the people who talk about the great difficulty of factoring have equally little evidence. The net result is that it's reasonable to hope that factoring is difficult, but you should regard that as a provisional hypothesis rather than a certainty." I see the article kindly submitted here is the equivalent of an amateur blog post, just a note posted to one personal webpage that happens to be served up by the MIT server. This is a case when the Hacker News protocol for displaying a domain for the submitted article was misleading rather than helpful. The author is gainfully employed and highly educated in related disciplines, http://math.mit.edu/~cohn/ http://math.mit.edu/~cohn/ but he hasn't worked for a long time in this aspect of number theory, so the note is just thinking out loud, nothing more.
- Cieplak 10y ago
  > but he hasn't worked for a long time in this aspect of number theory, so the note is just thinking out loud, nothing more. Dismissing his ideas because of his lack of credentials? How many software stories are upvoted despite their authors lacking PhDs in computer science? > the Hacker News protocol for displaying a domain for the submitted article was misleading rather than helpful Dr. Cohn is a professor at MIT in the department of mathematics.
raverbashing 10y ago
Number theory is a fascinating subject, but it's more or less like taking a text in English and trying to make sense of the text by reading columns and not lines Most factorization algorithms require you to find either a loop or a quadratic congruence (mod n). What changes is the way they try to find these
sunstone 10y ago
You can be sure that our numerate friends at the NSA have spent some quality time trying to find an efficient factoring algorithm over the past few decades. As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. And given the stakes it's really not likely to be the possibly untested problem that this author speculates about.
- leereeves 10y ago
  Decades of research don't prove that there's no solution. It took mathematicians 357 years to prove Fermat's Last Theorem.
  - _asummers 10y ago
    And that required about 357 years of mathematics to be able to prove it, as well. With the recentish GI announcement, I'm hopeful factoring and discrete log will fall within the next decade or two, but it's likely going to involve a bunch of subtle perspective shifts on several different fronts combined with new machinery in math to show.
    - kazinator 10y ago
      3 x 7 x 17 = 357 years, by the way.
      - Retra 10y ago
        I see you're not a physicist...
- feral 10y ago
  >As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. "assume with good confidence" - this is very naive. They're not going to advertise their super secret breakthrough by acting like they no longer care about encryption. Such a secret is going to be compartmentalized in the organization etc.
heyrhett 10y ago
.
- jstanley 10y ago
  > Quantum computer researchers that receive government funding are no longer allowed to publish results over 9 qbits. Very interesting. One must assume this is because they know something the rest of us don't about what is possible with over 9 qbits.
  - jessriedel 10y ago
    Not true. 10 qubits is trivial to simulate classically.
  - nickpsecurity 10y ago
    They know what the rest of us do know: advances in quantum computing could hurt national security. So, they're using their default method of countering future advances by restricting sharing of ideas or tech. I'm not sure how effective it will be as it depends on how much funding comes from how many sources. Emanation attacks and TEMPEST security is still restricted to a handful of countries after decades of them discovering it. So, there's some precedent for the approach working.
- machrider 10y ago
  There are crypto functions that are not amenable to quick solutions with quantum computers, right? Is there any reason why we wouldn't start migrating to those functions today? It seems foolish to wait until technology matures and present-day crypto is completely invalidated before we react defensively. Is anyone working on this?
  - _asummers 10y ago
    The NSA and NIST have already called for the beginning of what they call "post quantum crypto". https://www.schneier.com/blog/archives/2016/05/nist_starts_pla.html https://www.schneier.com/blog/archives/2016/05/nist_starts_p...
ajamesm 10y ago
This article makes it seem so easy to leap in and take a crack at it, but it seems like Step One is to either not value your own autonomy or to not rely on a wage. I'm not a professional mathematician (recreational learner, at best) and part of the reason I didn't pursue a career of interesting problems like this is because I don't want to do so as a cog in academia or a spook at the NSA. Am I wrong? Are there people who've had experiences that contradict my cynical perceptions?
- Paul-ish 10y ago
  I think you are, in fact, being cynical. Every year I see articles stating that mathematician is the happiest/best paid career. http://blogs.wsj.com/atwork/2014/04/15/best-jobs-of-2014-congratulations-mathematicians/ http://blogs.wsj.com/atwork/2014/04/15/best-jobs-of-2014-con... http://www.npr.org/templates/story/story.php?storyId=100142849 http://www.npr.org/templates/story/story.php?storyId=1001428...
  - pavel_lishin 10y ago
    Does that NPR job survey count people who tried their hand at being mathematicians, and hated it so much that they quit, or were unable to find jobs as mathematicians?
    - vinchuco 10y ago
      ... are you trying your hand at being a mathematician by asking that question? :)
      - pavel_lishin 10y ago
        Comment for the job you want, not the job you have!
        deleted 10y ago
        [deleted]
tptacek 10y ago
A reason, and not the best one, to stop using RSA and conventional DH and switch to elliptic curves.
- pbsd 10y ago
  The argument laid out by Cohn also works against elliptic curves: the discrete log is not NP-hard either, and if anything even less people have tried to attack it than factorization (according to Cohn, subexponential factorization only happened in the 1970s, after centuries of trying; elliptic curves are not that old). Some lattice problems, on the other hand, are known to be NP-hard. What does this tell us about their worthiness as cryptographic problems? Not a lot.
  - tptacek 10y ago
    Which do you think is going to happen first: progress against RSA that plausibly threatens 2048 (or 3072) bit keys, or progress against ECC that plausibly threatens Curve25519?
    - pbsd 10y ago
      I think progress against RSA is more likely, unless Shor happens first and kills everyone. I also hope to see a O(n^2) matrix multiplication algorithm within my lifetime. My point was not to defend RSA, but to point out that Cohn's argument could be reused for most of our current primitives.
      - tptacek 10y ago
        I figured that'd be your answer. I feel like the idea that you'd use ECC out of concern for advances in factoring or conventional discrete log isn't my own, but I'm not careful enough with this stuff to know the best thing to cite. As always, I comment on crypto stuff principally to see if I can goad you into correcting me. :)
        pbsd 10y ago
Cieplak 10y ago
The Lenstra elliptic curve factorization method is quite interesting: https://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization https://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factori...
nkoren 10y ago
Maybe much easier... http://blogs.discovermagazine.com/fire-in-the-mind/2013/02/25/oliver-sacks-and-the-amazing-twins/ http://blogs.discovermagazine.com/fire-in-the-mind/2013/02/2... ...or maybe not.
PeterWhittaker 10y ago
I truly understand neither a) why this piece of puff is on HN nor b) why it is so highly voted. As others have noted, I have no real evidence for my views. To me this is a total WTF? The author is ignorant of the subject and like so many experts outside their fields supposes that the field that has suddenly piqued their interest cannot, must not, be all that complex. Factoring some numbers is very, very easy. Factoring other numbers is computationally hard. The consensus in the field is that there are no shortcuts. See, e.g., [1] and [2]. [1] http://www.cs.virginia.edu/~kam6zx/is-it-secure/the-hardness-of-factoring/ http://www.cs.virginia.edu/~kam6zx/is-it-secure/the-hardness... [2] https://en.wikipedia.org/wiki/Integer_factorization https://en.wikipedia.org/wiki/Integer_factorization Next, I shall write a brief article declaring that warp drive is likely far easier than everyone thinks. Please upvote it when I submit it to HN....
nothinithit 10y ago
At a research lab I once worked for I knew a mathematician who was sure he was onto a way to break RSA. I won't go into the math involved but it got me thinking that often when one person has an idea, several other people have the same idea around the same time independently. I would not be surprized if some infamous security agency had broken RSA years ago and has since been pretending it hasn't.

89 points by vinchuco 10y ago

In addition to which, of those 100, some of the ones with the strongest incentive to crack factoring work for places with a strong disincentive to publish their results. EDIT: Missed the sentence in the article where this is hinted at.

eximius 10y ago

He's not wrong, but that doesn't make him right.

Animats 10y ago
He makes the good point that factoring is already below exponential time, and there's been progress over the years in speeding it up. Even if someone doesn't develop a polynomial time algorithm, there still could be substantial progress. There's also the possibility of new algorithms which are fast for some products of two primes, but not all. There are lots of problems, such as linear programming, where the worst case is exponential but the average case is far faster. Even something that allowed easy factoring of only 1% of products of two primes would be useful to an attacker.
- eximius 10y ago
  I'm not too terribly worried. There are enough efforts to look for post-quantum crypto algorithms that I think by the time we come up with something that actually threatens factoring, we'll have alternatives. If quantum stuff comes first, then we can go to lattice based systems (which are the leading candidate as far as I know - please correct me otherwise, I am familiar with lattice based systems but have not done research for a better base). If factoring is solved first, we can stick with elliptic curves.
  - coldtea 10y ago
    >I'm not too terribly worried. There are enough efforts to look for post-quantum crypto algorithms that I think by the time we come up with something that actually threatens factoring, we'll have alternatives. That's hardly a consolation, since all that we've encrypted and shared until then will be trivial to break as long as people have them in encrypted form (which is very easy to do).
    - eximius 10y ago
      That is sort of inevitable, I think. Best case, it is never broken and we never get quantum computers, but I hope that doesn't come to pass. So the next best case is that most of the details recovered by such breakage are irrelevent to those still alive. I think thats far more likely anyway.
coldtea 10y ago
He doesn't maintain he is right, so that's beside the point. His main claim is that others that say it's hard are not necessarily right either, and have no proof for that.

mofreek 10y ago

tl;dr: I don't have any evidence this is true, but there's no counter evidence either.

tokenadult 10y ago

"Of course, I have no real evidence for my views; if I had any good ideas for factoring, I'd be working on them instead of writing this. On the other hand, the people who talk about the great difficulty of factoring have equally little evidence. The net result is that it's reasonable to hope that factoring is difficult, but you should regard that as a provisional hypothesis rather than a certainty." I see the article kindly submitted here is the equivalent of an amateur blog post, just a note posted to one personal webpage that happens to be served up by the MIT server. This is a case when the Hacker News protocol for displaying a domain for the submitted article was misleading rather than helpful. The author is gainfully employed and highly educated in related disciplines, http://math.mit.edu/~cohn/ http://math.mit.edu/~cohn/ but he hasn't worked for a long time in this aspect of number theory, so the note is just thinking out loud, nothing more.

Cieplak 10y ago
> but he hasn't worked for a long time in this aspect of number theory, so the note is just thinking out loud, nothing more. Dismissing his ideas because of his lack of credentials? How many software stories are upvoted despite their authors lacking PhDs in computer science? > the Hacker News protocol for displaying a domain for the submitted article was misleading rather than helpful Dr. Cohn is a professor at MIT in the department of mathematics.

raverbashing 10y ago

Number theory is a fascinating subject, but it's more or less like taking a text in English and trying to make sense of the text by reading columns and not lines Most factorization algorithms require you to find either a loop or a quadratic congruence (mod n). What changes is the way they try to find these

sunstone 10y ago

You can be sure that our numerate friends at the NSA have spent some quality time trying to find an efficient factoring algorithm over the past few decades. As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. And given the stakes it's really not likely to be the possibly untested problem that this author speculates about.

leereeves 10y ago
Decades of research don't prove that there's no solution. It took mathematicians 357 years to prove Fermat's Last Theorem.
- _asummers 10y ago
  And that required about 357 years of mathematics to be able to prove it, as well. With the recentish GI announcement, I'm hopeful factoring and discrete log will fall within the next decade or two, but it's likely going to involve a bunch of subtle perspective shifts on several different fronts combined with new machinery in math to show.
  - kazinator 10y ago
    3 x 7 x 17 = 357 years, by the way.
    - Retra 10y ago
      I see you're not a physicist...
feral 10y ago
>As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. "assume with good confidence" - this is very naive. They're not going to advertise their super secret breakthrough by acting like they no longer care about encryption. Such a secret is going to be compartmentalized in the organization etc.

heyrhett 10y ago

jstanley 10y ago
> Quantum computer researchers that receive government funding are no longer allowed to publish results over 9 qbits. Very interesting. One must assume this is because they know something the rest of us don't about what is possible with over 9 qbits.
- jessriedel 10y ago
  Not true. 10 qubits is trivial to simulate classically.
- nickpsecurity 10y ago
  They know what the rest of us do know: advances in quantum computing could hurt national security. So, they're using their default method of countering future advances by restricting sharing of ideas or tech. I'm not sure how effective it will be as it depends on how much funding comes from how many sources. Emanation attacks and TEMPEST security is still restricted to a handful of countries after decades of them discovering it. So, there's some precedent for the approach working.
machrider 10y ago
There are crypto functions that are not amenable to quick solutions with quantum computers, right? Is there any reason why we wouldn't start migrating to those functions today? It seems foolish to wait until technology matures and present-day crypto is completely invalidated before we react defensively. Is anyone working on this?
- _asummers 10y ago
  The NSA and NIST have already called for the beginning of what they call "post quantum crypto". https://www.schneier.com/blog/archives/2016/05/nist_starts_pla.html https://www.schneier.com/blog/archives/2016/05/nist_starts_p...

ajamesm 10y ago

This article makes it seem so easy to leap in and take a crack at it, but it seems like Step One is to either not value your own autonomy or to not rely on a wage. I'm not a professional mathematician (recreational learner, at best) and part of the reason I didn't pursue a career of interesting problems like this is because I don't want to do so as a cog in academia or a spook at the NSA. Am I wrong? Are there people who've had experiences that contradict my cynical perceptions?

Paul-ish 10y ago
I think you are, in fact, being cynical. Every year I see articles stating that mathematician is the happiest/best paid career. http://blogs.wsj.com/atwork/2014/04/15/best-jobs-of-2014-congratulations-mathematicians/ http://blogs.wsj.com/atwork/2014/04/15/best-jobs-of-2014-con... http://www.npr.org/templates/story/story.php?storyId=100142849 http://www.npr.org/templates/story/story.php?storyId=1001428...
- pavel_lishin 10y ago
  Does that NPR job survey count people who tried their hand at being mathematicians, and hated it so much that they quit, or were unable to find jobs as mathematicians?
  - vinchuco 10y ago
    ... are you trying your hand at being a mathematician by asking that question? :)
    - pavel_lishin 10y ago
      Comment for the job you want, not the job you have!
      - deleted 10y ago
        [deleted]

tptacek 10y ago

A reason, and not the best one, to stop using RSA and conventional DH and switch to elliptic curves.

pbsd 10y ago
The argument laid out by Cohn also works against elliptic curves: the discrete log is not NP-hard either, and if anything even less people have tried to attack it than factorization (according to Cohn, subexponential factorization only happened in the 1970s, after centuries of trying; elliptic curves are not that old). Some lattice problems, on the other hand, are known to be NP-hard. What does this tell us about their worthiness as cryptographic problems? Not a lot.
- tptacek 10y ago
  Which do you think is going to happen first: progress against RSA that plausibly threatens 2048 (or 3072) bit keys, or progress against ECC that plausibly threatens Curve25519?
  - pbsd 10y ago
    I think progress against RSA is more likely, unless Shor happens first and kills everyone. I also hope to see a O(n^2) matrix multiplication algorithm within my lifetime. My point was not to defend RSA, but to point out that Cohn's argument could be reused for most of our current primitives.
    - tptacek 10y ago
      I figured that'd be your answer. I feel like the idea that you'd use ECC out of concern for advances in factoring or conventional discrete log isn't my own, but I'm not careful enough with this stuff to know the best thing to cite. As always, I comment on crypto stuff principally to see if I can goad you into correcting me. :)
      - pbsd 10y ago

Cieplak 10y ago

The Lenstra elliptic curve factorization method is quite interesting: https://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization https://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factori...

nkoren 10y ago

Maybe much easier... http://blogs.discovermagazine.com/fire-in-the-mind/2013/02/25/oliver-sacks-and-the-amazing-twins/ http://blogs.discovermagazine.com/fire-in-the-mind/2013/02/2... ...or maybe not.

PeterWhittaker 10y ago

I truly understand neither a) why this piece of puff is on HN nor b) why it is so highly voted. As others have noted, I have no real evidence for my views. To me this is a total WTF? The author is ignorant of the subject and like so many experts outside their fields supposes that the field that has suddenly piqued their interest cannot, must not, be all that complex. Factoring some numbers is very, very easy. Factoring other numbers is computationally hard. The consensus in the field is that there are no shortcuts. See, e.g., [1] and [2]. [1] http://www.cs.virginia.edu/~kam6zx/is-it-secure/the-hardness-of-factoring/ http://www.cs.virginia.edu/~kam6zx/is-it-secure/the-hardness... [2] https://en.wikipedia.org/wiki/Integer_factorization https://en.wikipedia.org/wiki/Integer_factorization Next, I shall write a brief article declaring that warp drive is likely far easier than everyone thinks. Please upvote it when I submit it to HN....

nothinithit 10y ago

At a research lab I once worked for I knew a mathematician who was sure he was onto a way to break RSA. I won't go into the math involved but it got me thinking that often when one person has an idea, several other people have the same idea around the same time independently. I would not be surprized if some infamous security agency had broken RSA years ago and has since been pretending it hasn't.