是否有公钥密码算法，可证明NP难以击败？ [英] Are there public key cryptography algorithms that are provably NP-hard to defeat?

问题描述

如果实际的量子计算成为现实，我想知道是否有任何基于NP完全问题的公钥加密算法，而不是整数因式分解或离散对数。

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.

编辑：

请检查
关于量子计算机的维基文章它指出，量子计算机可以回答的问题（BQP）被认为是严格比NP-完成。

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.

编辑2：

'基于NP完成'是一种糟糕的表达方式感兴趣的。

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

我想要的是一个公共密钥加密算法的属性，任何破解加密的方法也可以用来打破底层的NP-完全问题。这意味着打破加密证明P = NP。

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.

推荐答案

我回应这个旧线程，因为它是一个非常常见和重要问题，这里的所有答案都不准确。

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

对原始问题的简短回答是一个明确的否。没有已知的基于NP完全问题的加密方案（更不用说公开密钥方案）（因此，所有这些方案都在多项式时间减少之下）。

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.

这里有很多要澄清的，所以让我们从基于NP的意义开始完成问题。对此的一般同意的解释是：可以在特定的正式模型中证明是安全的，假设没有多项式时间算法用于NP完全问题。更准确地说，我们假设不存在总是解决NP完全问题的算法。这是一个非常安全的假设，因为对于算法来说这是一件很难的事情 - 看起来很容易想出一个算法，以很好的概率解决问题的随机实例。

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:

：此加密方案证明是安全的，假设没有
多项式时间算法用于
解决某个问题X的随机实例。

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

注意随机实例部分。对于一个具体的例子，我们可以假设没有多项式时间算法存在以一些很好的概率分解两个随机n位元素的乘积。这与假定不存在用于总是因子分解两个随机n位素数的所有乘积的多项式时间算法非常不同（更不安全）。

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.

随机实例与最坏情况问题是上面几个响应者跳过的。 McEliece型加密方案基于解码线性码的非常特殊的随机版本 - 而不是基于NP完整的实际最坏情况版本。

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.

推送超越这个随机实例问题需要一些深入和美丽的理论计算机科学研究。从MiklósAjtai的工作开始，我们发现了加密算法，其中安全假设是一种最坏情况（更安全）假设，而不是随机情况。不幸的是，最坏的情况假设是不知道是NP完成的问题，一些理论证据表明我们不能适应他们使用NP完全问题。对于感兴趣的，查找基于网格的加密。

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难以击败？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！