Given RSA, why do we not know if public-key cryptography is possible?

Problem Detail: 

I was on wikipedia on list of unsolved computer science problems and found this: Is public-key cryptography possible?

I thought RSA encryption was a form of public-key cryptography? Why is this a problem?

Asked By : Namster

Answered By : Yuval Filmus

We don't know for sure that RSA is safe. It could be that RSA can be broken in polynomial time, for example if factoring can be done efficiently. What is open is the existence of a a provably secure public-key cryptosystem. We don't know for sure that such a cryptosystem exists at all; for all we know, every cryptosystem could be broken efficiently.

A different, unrelated problem with RSA is that it can be broken by quantum computers. This is an unrelated problem since the definition of a secure public-key cryptosystem only requires that the cryptosystem not be breakable by classical (non-quantum) computers.

Practically speaking, though, RSA seems secure, and it is used all the time. This is due to the gap between theory and practice. While theoretically we don't know for sure that RSA is secure, practically speaking we have to use some public-key cryptosystem, and RSA is a good choice since people have tried to break it and failed. Generally speaking, a known cryptosystem that people care about is more secure than an obscure one, since it has resisted the attempts of cryptographers. This doesn't constitute a proof that it is secure – it might well not be – but it's the best we can do.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47222