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.
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.
(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.)
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.)
尚无已知的计算一般离散对数 logbg 的有效算法。 简单的算法是将 b 提高到越来越高的 k 次幂，直到找到所需的 g； 这有时称为试乘。 该算法需要的运行时间与组 G 的大小呈线性关系，因此与组大小的位数呈指数关系。 然而，由于 Peter Shor，存在一种有效的量子算法（http://arxiv.org/abs/ Quant-ph/9508027）。
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!
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.
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".
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.
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.
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.
发布评论
评论（11）
谷歌搜索 NP 完全加密和公钥加密发现误报......实际上是不安全的。 这个卡通pdf似乎显示基于最小支配集问题的公钥加密算法。 进一步阅读，它承认撒谎说该算法是安全的……潜在的问题是 NP 完全的，但它在 PK 算法中的使用并没有保留难度。
另一个误报 Google 发现：来自 Crypto '97 的 Goldreich-Goldwasser-Halevi 密码系统的密码分析。 摘要：
在 Crypto '97 上，Goldreich、Goldwasser 和 Halevi 提出了一种基于格中最接近向量问题的公钥密码系统，该系统被称为 NP 难问题。 我们证明该方案的设计存在一个重大缺陷，它有两个含义：任何密文都会泄漏明文的信息，并且解密密文的问题可以简化为一个特殊的最接近向量问题，该问题比一般问题容易得多。
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.
有一个网站可能与您的兴趣相关：后量子密码学。
There is a web site that may be relevant to your interests: Post-Quantum Cryptography.
这是我的推理。 如我错了请纠正我。
(i) “破解”密码系统必然是 NP 和 co-NP 中的一个问题。 （破解密码系统涉及反转加密函数，该函数是一对一且可在多项式时间内计算的。因此，给定密文，明文是可以在多项式时间内验证的证书。因此根据密文在 NP 和 co-NP 中。)
(ii) 如果 NP 和 co-NP 中存在 NP 难问题，则 NP = co-NP。 （这个问题将是 NP 完全且在 co-NP 中。由于任何 NP 语言都可以简化为该 co-NP 语言，因此 NP 是 co-NP 的子集。现在使用对称性：co-NP 中的任何语言 L 都有 -L （它的补语）在 NP 中，因此 -L 在 co-NP 中——即 L = --L 在 NP 中。）
(iii) 我认为人们普遍认为 NP ！ = co-NP，否则有多项式大小的证明表明布尔公式不可满足。
结论：复杂性理论猜想意味着 NP 难密码系统不存在。
（否则，您将在 NP 和 co-NP 中遇到 NP 难问题，因此 NP = co-NP——这被认为是错误的。）
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.)
虽然 RSA 和其他广泛使用的密码算法是基于整数分解的难度（不知道是否是 NP 完全问题），但也有一些公钥密码算法基于 NP 完全问题。 谷歌搜索“公钥”和“np-complete”将显示其中一些。
（我之前错误地说过，量子计算机会加速 NP 完全问题，但这不是事实。我纠正了。）
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.)
正如许多其他发帖者所指出的，密码学可以基于 NP 困难或 NP 完全问题。
然而，密码学的常用方法将基于困难的数学（即难以破解）。 事实是，将数字序列化为传统密钥比创建解决 NP 难题的标准化字符串更容易。 因此，实用的密码学是基于尚未被证明是 NP 困难或 NP 完全的数学问题（因此可以想象，其中一些问题在 P 中）。
在 ElGamal 或 RSA 加密中，破解它需要破解离散对数，因此请查看此 wikipedia文章。
人们普遍认为这些是 NP 完全的，但也许无法证明这一点。 请注意，量子计算机可以有效地破解密码！
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.
The widespread belief is that these are NP-complete, but maybe can't be proven so. Note that quantum computers may break crypto efficiently!
由于没有人真正回答这个问题，我必须给你提示：“McEliece”。 对其进行一些搜索。 它是一种经过验证的 NP-Hard 加密算法。 加密和解密需要O(n^2)时间。 它也有一个大小为 O(n^2) 的公钥，这很糟糕。 但有一些改进可以降低所有这些界限。
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.
我回应这个旧话题是因为这是一个非常常见且重要的问题，这里的所有答案都是不准确的。
对最初问题的简短回答是明确的“否”。 没有已知的加密方案（更不用说公钥方案）是基于 NP 完全问题（因此所有这些方案都在多项式时间约简下）。 不过，有些比其他“更接近”，所以让我详细说明一下。
这里有很多需要澄清的地方，所以让我们从“基于 NP 完全问题”的含义开始。 对此普遍同意的解释是：“假设对于 NP 完全问题不存在多项式时间算法，可以在特定的形式模型中证明安全”。 更准确地说，我们假设不存在总是解决 NP 完全问题的算法。 这是一个非常安全的假设，因为这对于算法来说是一件非常困难的事情 - 提出一种以良好的概率解决问题的随机实例的算法似乎要容易得多。
不过，没有任何加密方案有这样的证据。 如果您查看文献，除了极少数例外（见下文），安全定理如下所示：
请注意“随机实例”部分。 举一个具体的例子，我们可能假设不存在多项式时间算法来以一定的概率分解两个随机 n 位素数的乘积。 这与假设不存在用于始终因式分解两个随机 n 位素数的所有乘积的多项式时间算法有很大不同（不太安全）。
“随机实例”与“最坏情况实例”的问题是困扰上述几位响应者的问题。 McEliece 型加密方案基于解码线性码的非常特殊的随机版本，而不是基于 NP 完全的实际最坏情况版本。
超越这个“随机实例”问题需要在理论计算机科学方面进行一些深入而精彩的研究。 从 Miklós Ajtai 的工作开始，我们发现了密码算法，其中安全假设是“最坏情况”（更安全）假设，而不是随机情况假设。 不幸的是，最坏的情况假设是针对未知的 NP 完全问题，并且一些理论证据表明我们无法调整它们以使用 NP 完全问题。 对于感兴趣的人，请查找“基于格的密码学”。
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:
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".
一些基于NP难问题的密码系统已经被提出（例如Merkle-Hellman密码系统基于子集和问题，以及基于背包的 Naccache-Stern 背包密码系统问题），但它们都被破坏了。 为什么是这样？ Scott Aaronson 的第 16 讲理论计算机科学的伟大思想对此说了一些话，我认为你应该将其视为确定的。 它的内容如下：
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:
这是 1998 年的一个悬而未决的问题：
关于密码学基于的可能性假设 P != NP
作者：Oded Goldreich、Rehovot Israel、Shafi Goldwasser
摘要：“我们的结论是，问题仍然存在”。
——我想知道过去十年这种情况是否发生了变化？
编辑：
据我所知，这个问题仍然悬而未决，最近在回答不存在这样的算法方面取得了进展。
Adi Akavia、Oded Goldreich、Shafi Goldwasser 和 Dana Moshkovitz 于 2006 年在 ACM 上发表了这篇论文：基于 NP 硬度的单向函数 “我们的主要发现是以下两个负面结果”
斯坦福大学网站 复杂性动物园有助于描述这两个负面结果的含义。
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.
虽然许多形式已被破坏，但请查看 Merkle-Hellman，它基于以下形式： NP 完全的“背包问题”。
While many forms have been broken, check out Merkle-Hellman, based on a form of the NP-complete 'Knapsack Problem'.
格密码学提供了（过度）概括的重要信息，即人们确实可以设计出打破平均情况与解决特定 NP 难题（通常是最短向量问题或最近向量问题）一样困难的密码系统。
我建议您阅读 http://eprint.iacr.org/2008/521 然后追踪对密码系统的引用。
另请参阅 http://www.cs.ucsd.edu/~ 上的讲义daniele/CSE207C/，如果需要的话还可以追踪一本书的链接。
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.