The question stems from the fact that foundations of crypto states: suppose breaking an encryption scheme is NP-complete, then P != NP implies that this encryption is hard to break in the worst case, but does not rule out the possibility that it can be broken almost always. How can this be true, if the encryption is NP-complete breaking should take super-polynomial time no?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
The Merkle–Hellman knapsack cryptosystem (Wikipedia article) is the canonical example of this. It was designed to rely on the difficulty of the subset sum problem, which is NP-complete. However, while NP-complete means, under the P ≠ NP hypothesis, that there is no polynomial-time algorithm to guarantee a solution for every input, that doesn't mean the legitimate user can efficiently generate keys or ciphertexts for which all polynomial-time algorithms to decrypt ciphertexts or recover keys will fail with nonnegligible probability. And it turns out that the knapsack cryptosystem is easily breakable.
Now, it is not always the case that cryptosystems with relations to NP-complete or NP-hard problems are practically breakable. For example, the McEliece cryptosystem (Wikipedia article), whose decryption is related to the NP-hard problem of decoding general linear codes, has withstood scrutiny of decades, and modern parametrizations are not known to be breakable even with a quantum computer.
For more about P = NP and crypto, see also an earlier post I wrote on the usefulness of asymptotic cost analyses versus concrete cost analyses. The brief summary is that even if P = NP, that fact may nevertheless have no practical consequences for cryptography.
answered Nov 3, 2017 at 23:43
-
4$\begingroup$ Actually, I believe that it is unproven whether either Knapsack or McEliece are really based on a NP-hard problem, in the sense that it is unproven that the hard problems they are based on, limited to the subset of instances that Knapsack/McEliece can actually generate, remain NP-hard. It is not enough that one be able to express the hard problem as an instance of an NP-hard problem; one could express RSA as a 3SAT problem; however, that doesn't mean that RSA is NP-hard. $\endgroup$– ponchoCommented Nov 4, 2017 at 3:14
-
$\begingroup$ If you read carefully, you'll see I didn't commit to claiming that! I said ‘[knapsack crypto] was designed to rely on the difficulty of the subset sum problem, which is NP-complete’ and that ‘[decrypting] McEliece… is related to the NP-hard problem of decoding general linear codes’. $\endgroup$ Commented Nov 4, 2017 at 3:52
$\begingroup$
$\endgroup$
2
I'd like to add my two cents to this. Squeamish Ossifrage's answer is correct and interesting as it points to the historical attempts of basing cryptography on problems related to NP-hard problems, but as pointed out by poncho, this does not fully answer OP's question. So, I'd like to add a more formal answer to the initial question:
Is it possible to construct an encryption scheme for which breaking is NP complete but there nearly always exists an efficient breaking algorithm
The answer to this question is no, or rather, answering yes to this question would have extremely surprising consequences. In fact, it would be extremely surprising if we could construct an encryption scheme for which breaking is NP complete, independently of whether there exists an efficient breaking algorithm in practice.
To see this, let us first make the question slightly more formal: "breaking a cryptosystem" is a search problem, while NP is about decision problem. So, let's take a decision version of the task of breaking a cryptosystem (any should do, without changing the answer much): let us consider the decision problem "does this ciphertext encrypt an odd message" (or, put otherwise, the task is to find the least significant bit of the plaintext). Now, this gives you a language $\mathcal{L}$, and given a ciphertext, you have to decide membership to $\mathcal{L}$.
Now, the crucial observation is the following: there is a witness which allows to check membership to $\mathcal{L}$ in polynomial time, but there is also a witness which allows to check non-membership to $\mathcal{L}$ in polynomial time: in both cases, it is just the secret key of the scheme (take the secret key, decrypt, and check whether the decrypted message is odd or even). Stated in complexity-theoretic terms, this means that $\mathcal{L}$ is in NP, but also in co-NP. Therefore, if $\mathcal{L}$ was NP-complete, we would have found an NP-complete language in NP $\cap$ co-NP, implying that co-NP = NP. This, in turn, would imply a collapse of the entire polynomial hierarchy to its first level -- or, put more simply, this would be almost as surprising as a proof of P $=$ NP to any researcher in computational complexity. This would have a considerable number of consequences, and proving (or disproving) this is one of the biggest open problems in the field.
So, it is very unlikely that anyone can construct a cryptosystem for which breaking would provably be NP-complete (and indeed, as pointed out by poncho, breaking the cryptosystem mentioned in Squeamish Ossifrage's answer is not proven to be NP-hard, although it is "related" to NP-hard problems).
Squeamish Ossifrage
49.5k3 gold badges118 silver badges227 bronze badges
answered Nov 4, 2017 at 14:57
-
1$\begingroup$ I'm not certain whether $\mathcal{L}$ always allows negative witnesses. One example of such an $\mathcal{L}$ is "is there a key that converts this plaintext to this ciphertext"; there's an obvious positive witness, but no obvious negative one. In your example (is the lsbit of the decryption a 0), you somehow need to eliminate the possibility of someone producing an incorrect key as a (possibly lying) witness, and it's not immediately obvious how to do that in general. $\endgroup$– ponchoCommented Nov 4, 2017 at 21:29
-
1$\begingroup$ Woops, I had completely forgotten to answer this. You are right, my answer only applies to most common cryptosystems that we know of and that satisfy some additional properties (e.g. that you cannot produce fake secret keys that decrypt a given ciphertext to a wrong message). All classical public key cryptosystems we use satisfy these properties (e.g. ElGamal, Paillier, RSAOAEP...), but that is indeed not necessarily the case - a counter example is deniable encryption. $\endgroup$ Commented Dec 21, 2017 at 11:58