6
$\begingroup$

First of all, I only understand the P versus NP debate on a rather shallow level as I am not a computer scientist. So perhaps the answer to the question is straightforward but if not, I would be interested to know more.

I believe the consensus amongst computer scientists, complexity theorists, and programmers today is inclined more towards P $\neq$ NP than the equality. Nonetheless, I also find that the Internet is rife with doomsday pictures if

  1. the P = NP conjecture were indeed proven true, or/and
  2. large scale quantum computers (running Shor's algorithm) do become a reality.

To tackle the 2nd problem, the field of post-quantum cryptography has been developing ciphers that are resistant to cryptanalysis by Shor's algorithm and variants. However, I have not been able to find any convincing answer to the question: Do the post-quantum ciphers also automag/tically address the 1st problem?

As such, I checked the elementary description of a few ciphers, e.g., the McEliece cryptosystem, which are explored under the banner of post-quantum cryptography. Some of them are apparently based on NP-hard problems (such as the shortest vector problem) which means that these ciphers won't become vulnerable (even in theory) even if the P =NP conjecture holds true. But is that the also case with all current as well as future post-quantum cryptographic mechanisms?

$\endgroup$
12
$\begingroup$

Do the post-quantum ciphers also automag/tically address the 1st problem?

Not really, however to explore that in any detail, we need to explore what the 1st problem is.

If $P=NP$ is proven true, what does that practically mean? Well, it might have absolutely no practical ramifications, or it might mean that virtually all known cryptographical systems can be trivially broken.

Why is this? Well, for two reasons: one, if we know $P=NP$ is true, we know that any problem within NP can be solved in polynomial time; it doesn't say we know how it can do it. If the proof of $P=NP$ doesn't give an algorithm (e.g. the proof shows that $P \ne NP$ leads to a contradiction), the knowledge that there is a polytime algorithm doesn't help us to solve any particular problem.

Secondly, even if we knew a polytime algorithm to solving an arbitrary problem within $NP$, it doesn't say that it runs in any sort of practical time. If the algorithm runs in $O(N^{1000})$ time, it is infeasible to run against any realistic problem, and hence does not practically impact the security of any cryptographical system at all.

On the other hand, what $P=NP$ might mean is that there is a practical algorithm for solving any reasonably sized problem; by practical, I mean that it is feasible to run the algorithm against a reasonable sized problem. If this were the case, all but a handful of cryptographical algorithms would be broken.

Here's why: known cryptographical systems are based on one of three security assumptions:

  • Informational security; the attacker literally does not have enough information to recover the plaintext; an example of this is One Time Pad (OTP)

  • Quantum security; the laws of physics prohibit the attacker from listening into the message without detectably disturbing in; Quantum Cryptography (QC) is in this category

  • Computational security; the attacker has all the information he needs; however recovering the plaintext would require more computation than he has; virtually all cryptographical systems are in this category

A practical way to solve an arbitrary $NP$ problem would invalidate everything in the computational security category, as everything in that category can be reduced to a series of $NP$ problems. Hence, in the absolute worse case scenario, we'd be left with OTP, QC and not much else.

So, in summary, just saying $P=NP$ doesn't give us enough information about what the practical aspects would be. However, 'post-quantum' algorithms, that is, algorithms that cannot be practically broken, even given access to the algorithms that can be run on a quantum computer, don't bring anything special to the table.

Now, you state that:

Some of them are apparently based on $NP$-hard problems (such as the shortest vector problem) which means that these ciphers won't become vulnerable (even in theory) even if the $P=NP$ conjecture holds true.

Actually, you misunderstand what $NP$-hard means; it doesn't mean that the problem is harder than an $NP$ problem; what it means is that if you can solve that problem, you can solve any problem in $NP$ (and so it is at least as hard as any $NP$ problem). However, it doesn't state whether it goes the other way; if you can solve an $NP$-complete problem, you may or may not be able to solve your $NP$-hard problem. In practice, we often dub a problem as $NP$-hard (and not $NP$-complete) if the problem is not a decision problem (that is, the answer to the problem isn't limited to "Yes" or "No"), and so pedantically not within $NP$ (and hence not within the set of $NP$-complete problems).

$\endgroup$
  • 5
    $\begingroup$ I just wanted to add that there is a common misconception that quantum computers can somehow solve all problems in NP in poly time. This is not (known to be) the case. They just happen to be able to efficiently solve some NP problems we usually base cryptography on (like factoring, which is not NP-complete). There are other NP problems that are not known to be in P or to be more efficiently solvable on a quantum computer. These are the type problems that post-quantum cryptography is based on. So this is why post-quantum crypto does not really address the P=NP case. They simply dont have to. $\endgroup$ – Guut Boy Nov 12 '14 at 20:29
  • $\begingroup$ "Doesn't not" under information-theoretical security should just be "doesn't" (or "does not"). $\endgroup$ – cpast Dec 1 '14 at 19:30

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.