# Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. I wonder, why has there not been an encryption algorithm which is based on an known NP-hard problem. It sounds (at least in theory) like it would make a better encryption algorithm than a one which is not proven to be NP-hard.

## 6 Answers

Worst-case Hardness of NP-complete problems is not sufficient for cryptography. Even if NP-complete problems are hard in the worst-case ($P \ne NP$), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using the $P \ne NP$ assumption is a major open problem.

An excellent read is the classic by Russell Impagliazzo, A Personal View of Average-Case Complexity, 1995.

An excellent survey is Average-Case Complexity by Bogdanov and Trevisan, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106

• Don't we need hardness in the best case, too? After all, all of our keys should be secure. Or can we effectively (and efficiently) prevent the best case from happening? – Raphael Mar 14 '12 at 10:37
• moreover, we should be able to generate hard instances in reasonable time. In short, we need much more than just $\sf{NP\text{-}hard}$ness. – Kaveh Mar 14 '12 at 13:49
• @Raphael, it should be enough if the probability to get an undesirable "good" case is small enough. If it's say smaller than the probability to guess the correct key of a desirable "bad" case, this risk should be considered acceptable IMHO. – quazgar Feb 10 '14 at 13:37

There have been.

One such example is McEliece cryptosystem which is based on hardness of decoding a linear code.

A second example is NTRUEncrypt which is based on the shortest vector problem which I believe is known to be NP-Hard.

Another is Merkle-Hellman knapsack cryptosystem which has been broken.

Note: I have no clue if the first two are broken/how good they are. All I know is that they exist, and I got those from doing a web search.

• For the purposes of cryptanalysis, McEliece probably shouldn't be considered just one crytosystem; for each class of efficiently decodeable linear codes you plug in, you necessarily have to come up with a different strategy to break it. It's been broken for some classes of codes, but (as the Wikipedia article says) not for Goppa codes, which were McEliece's original suggestion. – Peter Shor Mar 19 '12 at 12:26
• From that list I'd say NTRU looks the most promising, it has yet to be extensively tested the way RSA was tested based on what I have read about so far. – Ken Li Mar 20 '12 at 4:21
• Merkle-Hellman cryptosystem is not an appropriate example. The Merkle-Hellman knapsack verctors are only a subset of all knapsack vectors so the Merkle-Hellman knapsack problem may not be NP hard. I don't think that it is NP-hard, at least I am not aware of any paper that shows this. – miracle173 Feb 10 '14 at 21:16

I can think of four major hurdles which are not entirely independent:

• NP-hardness only gives you information about complexity in the limit. For many NP-complete problems, algorithms exist that solve all instances of interest (in a certain scenario) reasonably fast. In other words, for any fixed problem size (e.g. a given "key"), the problem is not necessarily hard just because it is NP-hard.
• NP-hardness only considers worst-case time. Many, even most of all instances may be easy to solve with existing algorithms. Even if we knew how to characterise the hard instances (afaik, we don't), we'd still have to find them.
• You need to have huge instances that are hard to solve. Searching for (products of) large prime numbers is easy in the sense that the search space is flat: one number is either suited or not. Imagine using graphs: out of all $2^{n(n-1)}$ graphs of size $n$ for large $n$, you have to find those that have nice properties.
• You need some kind of reversability. For example, any integer is uniquely described by its prime factorisation. Image we would want to use TSP as encryption method; given all shortest tours, can you (re)construct the graph they came from uniquely?

Note that I have no expertise in cryptography; these are merely algorithmic resp. complexity-theoretic objections.

• Excellent summary. But note that BQP-hardness has the same caveats as your first two points. – Mitch Jul 14 '17 at 17:02

Public-key cryptography as we know it today is built on one-way trapdoor permutations, and the trapdoor is essential.

For a protocol to be publicly secure, you need a key available to anyone, and a way to encrypt a message using this key. Obviously, once encrypted, it should be hard to recover the original message knowing only its cipher and the public key : the cipher must only be decipherable with some extra information, namely your private key.

With that in mind, it's easy to build a primitive crypto system based on any one-way trapdoor permutation.

1. Alice gives the one-way permutation to the public, and keep the trapdoor to herself.
2. Bob put its input in the permutation, and transmit the output to Alice.
3. Alice uses the trapdoor to invert the permutation with Bob's output.

The difficulty now is to find actual one-way trapdoor permutations, and there's a bunch of function we think are good candidates (RSA, Discrete logarithm, some variations on the lattice problem). However, if we can find with certainty a one-way function, then we also prove that $\mathsf{P} \ne \mathsf{NP}$, so actually proving that a function is one-way is intractable.

The other way around, if we prove that $\mathsf{P} \ne \mathsf{NP}$, we also prove that there is a class in between called $\mathsf{NPI}$ (intermediate), of the problems in $\mathsf{NP}$ but not $\mathsf{NP}$-hard. Some good candidates for problems in $\mathsf{NPI}$ are also the candidates for one-way permutations, as we've not yet been able to prove that they are $\mathsf{NP}$-hard.

So to answer your question, we don't use $\mathsf{NP}$-hard problems because we need one-way permutation with trapdoors, and these special functions probably live in a class between $\mathsf{NP}$ and $\mathsf{NP}$-hard.

• RSA, yes it's a trapdoor function. I am not sure that dlog is TDF (is one way) – 111 Apr 1 '17 at 2:12
• If an NP-intermediate problem were NP-hard, they'd be NP-complete, a contradiction. – Myria Jan 25 '19 at 23:48

Merkle-Hellman cryptosystems are based on binary knapsack problems (subset sum).

• Can you give a reference? – Raphael May 12 '14 at 8:29
• "en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem" and also the monography: Postquantum Cryptography (Springer). – user13675 Jun 8 '14 at 22:36
• Shamir, Adi (1984). "A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem". IEEE Transactions on Information Theory. 30 (5): 699–704. doi:10.1109/SFCS.1982. – Mohammad Al-Turkistany May 26 '20 at 11:29

Just to give a heuristic argument, based on practical experience.

Almost all instances, of almost all NP-complete problems, are easy to solve. There are problems where this isn't true, but they are hard to find, and it's hard to be positive you have sound such a class.

This has come up in practice several times when people try to write random problem generators for some famous NP-complete class, such as Constraint Programming, SAT or Travelling Salesman. At some later date someone finds a method of solving almost all the instances that random generator produces trivially. Of course, if that was the case for an encryption system we would be in serious trouble!