You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

ciphergoth comments on Bullying the Integers - Less Wrong Discussion

13 Post author: sixes_and_sevens 15 December 2010 05:40PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (33)

You are viewing a single comment's thread. Show more comments above.

Comment author: ciphergoth 15 December 2010 08:37:14PM *  5 points [-]

I believe RSA can only be cracked by prime factorisation with the same certainty that I believe the primes are infinite. The only scenario in which they are false is one in which I am insane.

WHAT? Why do you believe this? Rabin is known to be secure if integer factorization is hard, but the same is NOT true of RSA.

Comment author: benelliott 15 December 2010 08:42:26PM *  0 points [-]

Can I have a source for this? I was under the impression RSA was provably secure. If it is not then I will edit my previous post.

Comment author: ciphergoth 15 December 2010 09:05:10PM *  10 points [-]

See Wikipedia on the RSA problem and in particular Breaking RSA may not be equivalent to factoring - which actually shows it's a lot less likely than you might think that anyone is going to prove breaking RSA equivalent to integer factorization.

No cryptosystem that can be cracked given unbounded computing power can currently be "proven secure" since we're a long way from showing that any useful problem is computationally hard. The best you can do is show that it's hard given some assumption.

Not wishing to be rude, but what caused such incredible overconfidence that you would say

I believe RSA can only be cracked by prime factorisation with the same certainty that I believe the primes are infinite. The only scenario in which they are false is one in which I am insane.

without personally understanding a proof to that effect? I do personally understand a proof that certain Rabin-based cryptosystems are as hard as integer factorization to break, and I'm still less confident of their theoretical security than I am of the infinitude of primes.

EDITED TO ADD: I should put a massive caveat on my assertions about Rabin before anyone gets the wrong impression: the proof that the cryptosystem is as hard as factoring depend on what is known as the "random oracle model", which is a very useful but unrealistically strong assumption about our hash functions.

Comment author: benelliott 15 December 2010 10:04:28PM 5 points [-]

The cause of my overconfidence was a combination of exaggeration, arrogance and thinking I had a proof to the effect. As I said above, I had read that the problem was easy and so when I found a 'proof' I assumed it to be correct.

It was, as you point out, a huge error. I will aim never to repeat it.

Comment author: ciphergoth 15 December 2010 10:13:48PM 3 points [-]

Fair enough, thanks for answering! If you're interested in this stuff, the proof that integer factorization is reducible to finding square roots modulo the composite isn't too hard to get into.

Comment author: benelliott 15 December 2010 10:16:46PM *  1 point [-]

Thanks for pointing it out!

This may actually be an example of qualitative difference between maths arguments and fiscal policy arguments that the OP talked about. My error was mathematical, so once it was pointed I had no wiggle room to rationalize. If you had corrected me on a point of fiscal policy I'm not sure it would have been so easy for me to just say oops.

Comment author: khafra 15 December 2010 10:24:48PM 2 points [-]

I will aim never to repeat it.

Will you also dramatically reduce your belief in your own sanity?

Comment author: benelliott 15 December 2010 10:48:36PM 3 points [-]

If extreme overconfidence counts as insanity then yes I will.

Comment author: gwern 24 May 2011 01:53:23AM 0 points [-]

I am strongly reminded by this whole conversation of http://www.spaceandgames.com/?p=27 & http://lesswrong.com/lw/mo/infinite_certainty/

Comment author: jsalvatier 15 December 2010 08:53:05PM 1 point [-]

just edit it.