4 ms·

Heuristically speaking, this problem is at least as hard as the P != NP question, which is one of the millenium problems for which the Clay institute has awarde

Heuristically speaking, this problem is at least as hard as the P != NP question, which is one of the millenium problems for which the Clay institute has awarded one million dollars to whoever resolves it. From a theory point of view, breaking a crypto-system typically means something like being able to do the following fast (i.e., in polynomial time): Given two plaintexts and a ciphertext which is the encryption of one of those two plaintexts, decide which of the plaintexts it is. Of course you could flip a coin, so the essential condition is that your success probability must be larger than 1/2. So to show that a crypto-system is secure, you have to show that the problem of breaking it cannot be solved in polynomial time. We simply do not know how to show that any useful problem cannot be solved in polynomial time (we do know that P != EXPTIME, but we don't know any problems in EXPTIME that would be useful for cryptography). Hence the lack of provable security.

YZF 13y ago
I think the complexity class of discrete log or integer factorization are not known. No one has proved there isn't a polynomial time algorithm but if one is found it does not mean P = NP.
- nhaehnle 13y ago
  This is true. However, this actually means that the type of proof that kazagistar asked for is harder than a proof that P != NP. After all, if you prove that factorization cannot be done in polynomial time, then a corollary of this result is that P != NP. Intuitively, NP-hard problems are believed to be harder than factorization and discrete log. And so it should be easier to prove that an NP-hard problem is not in P. What you are referring to is the opposite direction of the implication, which is very relevant in a discussion of why people have failed to find faster algorithms for integer factorization. However, the question I replied to is essentially why people have failed to prove that integer factorization (and discrete log) are hard problems. Edit: After re-reading my previous comment, perhaps this clarifies it best: Integer factorization and discrete log are probably less hard than NP-hard problems. However, the meta-problem "prove that integer factorization or discrete log is really, unconditionally hard" is at least as difficult as the meta-problem "prove P != NP".

YZF 13y ago

I think the complexity class of discrete log or integer factorization are not known. No one has proved there isn't a polynomial time algorithm but if one is found it does not mean P = NP.

nhaehnle 13y ago
This is true. However, this actually means that the type of proof that kazagistar asked for is harder than a proof that P != NP. After all, if you prove that factorization cannot be done in polynomial time, then a corollary of this result is that P != NP. Intuitively, NP-hard problems are believed to be harder than factorization and discrete log. And so it should be easier to prove that an NP-hard problem is not in P. What you are referring to is the opposite direction of the implication, which is very relevant in a discussion of why people have failed to find faster algorithms for integer factorization. However, the question I replied to is essentially why people have failed to prove that integer factorization (and discrete log) are hard problems. Edit: After re-reading my previous comment, perhaps this clarifies it best: Integer factorization and discrete log are probably less hard than NP-hard problems. However, the meta-problem "prove that integer factorization or discrete log is really, unconditionally hard" is at least as difficult as the meta-problem "prove P != NP".