Are there public key cryptography algorithms that are provably NP-hard to defeat? [closed]

Question

Should practical quantum computing become a reality, I am wondering if there are any public key cryptographic algorithms that are based on NP-complete problems, rather than integer factorization or discrete logarithms.

Edit:

Please check out the "Quantum computing in computational complexity theory" section of the wiki article on quantum computers. It points out that the class of problems quantum computers can answer (BQP) is believed to be strictly easier than NP-complete.

Edit 2:

'Based on NP-complete' is a bad way of expressing what I'm interested in.

What I intended to ask is for a Public Key encryption algorithm with the property that any method for breaking the encryption can also be used to break the underlying NP-complete problem. This means breaking the encryption proves P=NP.

Nogood

I'm sorry, this got closed. But at least we have: cs.stackexchange.com/questions/356/… – Zellner

Answer 1

I am responding to this old thread because it is a very common and important question, and all of the answers here are inaccurate.

The short answer to the original question is an unequivocal "NO". There are no known encryption schemes (let alone public-key ones) that are based on an NP-complete problem (and hence all of them, under polynomial-time reductions). Some are "closer" that others, though, so let me elaborate.

There is a lot to clarify here, so let's start with the meaning of "based on an NP-complete problem." The generally agreed upon interpretation of this is: "can be proven secure in a particular formal model, assuming that no polynomial-time algorithms exist for NP-complete problems". To be even more precise, we assume that no algorithm exists that always solves an NP-complete problem. This is a very safe assumption, because that's a really hard thing for an algorithm to do - it's seemingly a lot easier to come up with an algorithm that solves random instances of the problem with good probability.

No encryption schemes have such a proof, though. If you look at the literature, with very few exceptions (see below), the security theorems read like the following:

Theorem: This encryption scheme is provably secure, assuming that no polynomial-time algorithm exists for solving random instances of some problem X.

Note the "random instances" part. For a concrete example, we might assume that no polynomial-time algorithm exists for factoring the product of two random n-bit primes with some good probability. This is very different (less safe) from assuming that no polynomial-time algorithm exists for always factoring all products of two random n-bit primes.

The "random instances" versus "worst case instances" issue is what is tripped up several responders above. The McEliece-type encryption schemes are based on a very special random version of decoding linear codes - and not on the actual worst-case version which is NP-complete.

Pushing beyond this "random instances" issue has required some deep and beautiful research in theoretical computer science. Starting with the work of Miklós Ajtai, we have found cryptographic algorithms where the security assumption is a "worst case" (safer) assumption instead of a random case one. Unfortunately, the worst case assumptions are for problems that are not known to be NP complete, and some theoretical evidence suggests that we can't adapt them to use NP-complete problems. For the interested, look up "lattice based cryptography".

Warta

There are a few problems in TCS that are believed to be hard on random instances with non-negligible probability. Planted clique comes to mind... – Johnajohnath

Isn't Merkle-Hellman based on the binary knapsack problem (which is a subset sum problem subject to shortest vector attacks)? – Nodarse

Okay, perhaps a bit late to the party by eight years, but reading this arouses a question : as mentioned @ShreevatsaR’s answers quoting Scott Aaronson’s Lecture 16, cryptographic protocols based on NP-complete Problems are about if “there exists a message that’s hard to decode”. So therefore, a cryptosystem based on a co-NP problem is about “if all messages are hard to decode”. Isn’t this more provably secure than even a crypto system based on a problem “if random instances of it are hard to solve”? – Decipher

Answer 2

Some cryptosystems based on NP-hard problems have been proposed (such as the Merkle-Hellman cryptosystem based on the subset-sum problem, and the Naccache-Stern knapsack cryptosystem based on the knapsack problem), but they have all been broken. Why is this? Lecture 16 of Scott Aaronson's Great Ideas in Theoretical Computer Science says something about this, which I think you should take as definitive. What it says is the following:

Ideally, we would like to construct a [Cryptographic Pseudorandom Generator] or cryptosystem whose security was based on an NP-complete problem. Unfortunately, NP-complete problems are always about the worst case. In cryptography, this would translate to a statement like “there exists a message that’s hard to decode”, which is not a good guarantee for a cryptographic system! A message should be hard to decrypt with overwhelming probability. Despite decades of effort, no way has yet been discovered to relate worst case to average case for NP-complete problems. And this is why, if we want computationally-secure cryptosystems, we need to make stronger assumptions than P≠NP.

Besought

..."based on NP-hard problems"... sorta like a work of fiction "based on a true story"... – Fleeting

@Fleeting In what way? – Besought

Most likely there are some subset-sum instances that can never be generated as Merkle-Hellman keys, so being able to solve every Merkle-Hellman key in polytime doesn't necessarily imply the ability to solve random subset-sum instances in polytime. Furthermore, potentially a significant number of "duplicate" keys exist, leaving even more grey area between random knapsacks and Merkle-Hellman knapsacks. – Fleeting

@Fleeting Ah yes. That point, that random instances (and of the crypto-related subset at that) may not be hard, is something I agree with (and wrote about in the answer); I just hadn't understood your analogy. :-) Now I do. – Besought

Answer 3

This was an open question in 1998:

On the possibility of basing Cryptography on the assumption that P != NP by Oded Goldreich, Rehovot Israel, Shafi Goldwasser

From the abstract: "Our conclusion is that the question remains open".

--I wonder if that's changed in the last decade?

Edit:

As far as I can tell the question is still open, with recent progress toward an answer of no such algorithm exists.

Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz published this paper in the ACM in 2006: On basing one-way functions on NP-hardness "Our main findings are the following two negative results"

The stanford site Complexity Zoo is helpful in decripting what those two negative results mean.

Nogood

Answer 4

While many forms have been broken, check out Merkle-Hellman, based on a form of the NP-complete 'Knapsack Problem'.

Wideangle

Wikipedia says Merkle-Hellman was broken. ... If it is already broken that doesn't bode well for it standing up to a quantum attack. – Nogood

Dude you asked if there were cryptographic algorithms based on NP-complete problems. There are. – Wideangle

You are correct, I'll update my question as 'based' is a bit weak. – Nogood

Answer 5

Lattice cryptography offers the (over)generalized take-home message that indeed one can design cryptosystems where breaking the average case is as hard as solving a particular NP-hard problem (typically the Shortest Vector Problem or the Closest Vector Problem).

I can recommend reading the introduction section of http://eprint.iacr.org/2008/521 and then chasing references to the cryptosystems.

Also, see the lecture notes at http://www.cs.ucsd.edu/~daniele/CSE207C/, and chase links for a book if you want.

Polanco

Answer 6

Googling for NP-complete and Public key encryption finds False positives ... that are actually insecure. This cartoonish pdf appears to show a public key encyption algorithm based on the minimium dominating set problem. Reading further it then admits to lying that the algorithm is secure ... the underlying problem is NP-Complete but it's use in the PK algorithm does not preserve the difficulty.

Another False positive Google find: Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto '97. From the abstract:

At Crypto '97, Goldreich, Goldwasser and Halevi proposed a public-key cryptosystem based on the closest vector problem in a lattice, which is known to be NP-hard. We show that there is a major flaw in the design of the scheme which has two implications: any ciphertext leaks information on the plaintext, and the problem of decrypting ciphertexts can be reduced to a special closest vector problem which is much easier than the general problem.

Nogood

Answer 7

There is a web site that may be relevant to your interests: Post-Quantum Cryptography.

Foulmouthed

Answer 8

Here is my reasoning. Correct me if I'm wrong.

(i) ``Breaking'' a cryptosystem is necessarily a problem in NP and co-NP. (Breaking a cryptosystem involves inverting the encryption function, which is one-to-one and computable in polynomial-time. So, given the ciphertext, the plaintext is a certificate that can be verified in polynomial time. Thus querying the plaintext based on the ciphertext is in NP and in co-NP.)

(ii) If there is an NP-hard problem in NP and co-NP, then NP = co-NP. (This problem would be NP-complete and in co-NP. Since any NP language is reducible to this co-NP language, NP is a subset of co-NP. Now use symmetry: any language L in co-NP has -L (its compliment) in NP, whence -L is in co-NP---that is L = --L is in NP.)

(iii) I think that it is generally believed that NP != co-NP, as otherwise there are polynomial-sized proofs that boolean formulas are not satisfiable.

Conclusion: Complexity-theoretic conjectures imply that NP-hard cryptosystems don't exist.

(Otherwise, you have an NP-hard problem in NP and co-NP, whence NP = co-NP---which is believed to be false.)

Mithraism

Answer 9

While RSA and other widely-used cryptographic algorithms are based on the difficulty of integer factorization (which is not known to be NP-complete), there are some public key cryptography algorithms based on NP-complete problems too. A google search for "public key" and "np-complete" will reveal some of them.

(I incorrectly said before that quantum computers would speed up NP-complete problems, but this is not true. I stand corrected.)

Verlie

Actually I don't believe Quantum computers can directly solve NP-complete problems. They solve BPQ problems which encompass integer factorization and discrete log, but not 3SAT. – Nogood

Ack BQP: "bounded error, quantum, polynomial time". Check out : en.wikipedia.org/wiki/Quantum_computer – Nogood

So I have been doing the google search which does answer my original question. Unfortunately it doesn't seem to answer if there one that is known (or at least believed) to be NP-hard to defeat. – Nogood

Answer 10

As pointed out by many other posters, it is possible to base cryptography on NP-hard or NP-complete problems.

However, the common methods for cryptography are going to be based on difficult mathematics (difficult to crack, that is). The truth is that it is easier to serialize numbers as a traditional key than to create a standardized string that solves an NP-hard problem. Therefore, practical crypto is based on mathematical problems that are not yet proven to be NP-hard or NP-complete (so it is conceivable that some of these problems are in P).

In ElGamal or RSA encryption, breaking it requires the cracking the discrete logarithm, so look at this wikipedia article.

No efficient algorithm for computing general discrete logarithms logbg is known. The naive algorithm is to raise b to higher and higher powers k until the desired g is found; this is sometimes called trial multiplication. This algorithm requires running time linear in the size of the group G and thus exponential in the number of digits in the size of the group. There exists an efficient quantum algorithm due to Peter Shor however (http://arxiv.org/abs/quant-ph/9508027).

Computing discrete logarithms is apparently difficult. Not only is no efficient algorithm known for the worst case, but the average-case complexity can be shown to be at least as hard as the worst case using random self-reducibility.

At the same time, the inverse problem of discrete exponentiation is not (it can be computed efficiently using exponentiation by squaring, for example). This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries have been exploited in the construction of cryptographic systems.

The widespread belief is that these are NP-complete, but maybe can't be proven so. Note that quantum computers may break crypto efficiently!

Travel

Now that I think more about it, the reasoning is lacking. It seems fine to serialize the solution to an NP-complete problem (3-sat is just 01100010...) So either I'm looking at the wrong problems OR a number is just the most space efficient way to transfer a key (from information theory) – Travel

These are not believed to be NP hard. Discrete log and factoring are believed to be outside of P, but not actually hard for NP. – It

Factoring has not been shown to the NP-complete. There is no known method to transform 3SAT into a factoring problem in polynomial time. – Limoli

Answer 11

Since nobody really answered the question I have to give you the hint: "McEliece". Do some searches on it. Its a proven NP-Hard encryption algorithm. It needs O(n^2) encryption and decryption time. It has a public key of size O(n^2) too, which is bad. But there are improvements which lower all these bounds.

Pademelon

Hmmm: Search "McEliece". en.wikipedia.org/wiki/McEliece_cryptosystem and it looks like it was cracked w/o a Quantum computer: scientificblogging.com/news_releases/… This defintely seems to indicate it is still an open research topic. – Nogood

Ah ha! ... and on closer reading the paper that published the attack also published a fix! I hope somone with edit capablity can fix McElise-> McEliece in the original answer. This means there is a proposed encryption scheme that meets the parameters with no currently known successful attacks. – Nogood

This answer looks wrong. I'm not aware of any proof that breaking McEliece is NP-hard. Decoding general codes is NP-hard, but McEliece is based on decoding Coppa-codes. – Halfmast

1978 Cryptosystem Resists Quantum Attack: technologyreview.com/blog/arxiv/25629 This article indicates McEliece resists known quantum Attacks. "However, it's worth pointing out that while the new work guanratees safety against all known quantum attacks, it does nothing of the sort for future quantum attacks." I believe this is still the closest answer to the question. – Nogood

middleware.internet2.edu/idtrust/2009/papers/… – Nogood

@Steve Steiner: Resisting quantum attacks does not imply anything about NP-hardness. So this answer looks wrong to me too. – Besought