I've learned that public key encryption is based on the problem of Discrete Log (as regard to group theory) which believed to be hard.

But, can we say that it doesn't matter on which problem our public encryption rely and say that it couldn't be CPA secure anyway?


There is no direct inference from $P = NP$ or $P \neq NP$ to security or insecurity of any particular encryption algorithm. As far as practical consequences are concerned, the "$P = NP$" problem is severely overhyped.

If $P = NP$ then any problem for which a solution can be verified in polynomial time can also be solved in polynomial time. "Polynomial time" does not automatically mean fast, for two reasons:

  • Complexity classes like $P$ and $NP$ are about asymptotic behaviour: they give us values for sufficiently large instances of the problem. Nothing tells us that a specific instance is large enough for the asymptotic behaviour to be an accurate description of the computational cost of solving that instance. For instance, asymptotically speaking, GNFS is a faster integer factorization algorithm than Quadratic Sieve; but, in practice, QS is faster than GNFS for integers of less than 300 bits. Proving $P = NP$ would imply that there exists a polynomial algorithm to solve integer factorization (or discrete logarithm), but it would not follow that this algorithm is indeed efficient for a 1024-bit integer.

  • "Polynomial" means "with cost proportional to $n^x$ for a problem of size $n$ and some constant integer $x$". Nothing guarantees that $x$ is small. A $O(n^{20})$ algorithm is completely polynomial, and completely out of reach of our technology for a size $n \geq 32$ bits...

  • $\begingroup$ In theory of cryptography a polynomial time algorithm does mean fast $\endgroup$ – Bush Feb 13 '15 at 16:26
  • 1
    $\begingroup$ @Bush: no, it doesn't; read what Thomas wrote. A polynomial algorithm means it doesn't slow down that much as the problem becomes larger; a polytime algorithm can take large multiples of the lifetime of the universe on any input (as long as the number of multiples doesn't increase that fast as we scale the size of the problem upwards). $\endgroup$ – poncho Feb 13 '15 at 17:39
  • 1
    $\begingroup$ In most of the theory literature, "fast" does mean "polynomial", but it's irrelevant here since the answer is clearly concerned with "practical consequences". $\endgroup$ – fkraiem Feb 13 '15 at 21:50

Actually, it's not true that public key encryption is based on Discrete Log; the ones in common use (DH, ECDH, ECDSA) are (and even RSA can be viewed as "based on Discrete Log", at least from the standpoint of "if you can solve the Discrete Log modulo a composite, you can break RSA").

However, we do have a number of public key systems (NTRU, McEliece) which are believed to be secure, and not known to be reducible to discrete logs. If you want to explore this, you might want to search on "Postquantum Cryptography"; that's the term for public key cryptosystems that would still be secure even if someone has a Quantum Computer (which can solve Discrete Log problems easily).

However, to your main question:

Can we say that if $P = NP$ there is no CPA secure public key encryption?

Well, no, just a proof that $P = NP$, or even an explicit procedure for solving an NP complete problem in polynomial time, would not necessarily imply that.

Whether a problem is in $P$ does not depend on how difficult a particular instance is; instead, it has all to do which how more difficult it gets as the inputs get larger; in particular, the difficultly has to be bouned by some polynomial $Cn^k$, for some values $C$ and $k$. Another way of looking at it is if you double the size of the inputs, the difficulty of the problem increases by no more than a factor of $M$ (for some $M$).

On the other hand, whether a system is "CPA secure" has to do with the difficulty of a specific instance of the problem; if we give the adversary a problem of size $n$, we don't care how much more difficult it would have been if we gave the adversary a problem of size $2n$. Instead, all we care about is "does the adversary have enough computational resources to solve this problem.

For example, suppose the adversary had an algorithm to break our public key system in $O(n^8)$ time; if we can work with $n=2^{16}$, then the adversary would take $O(2^{128})$ time, which is generally believed to be infeasible, and hence the system would be secure, even though the adversary has a polynomial time algorithm against our system.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.