如果实用的量子计算成为现实，我想知道是否有任何基于 NP 完全问题的公钥密码算法，而不是整数分解或离散对数。
编辑：
请查看 关于量子计算机的 wiki 文章的“计算复杂性理论中的量子计算”部分。 它指出，量子计算机可以回答的问题类别（BQP）被认为比 NP-完全更容易。
编辑2：
“基于 NP 完全”是表达我感兴趣的东西的不好方式。
我想问的是一种公钥加密算法，其属性是任何破解加密的方法也可以用来破解潜在的NP完全问题。这意味着破解加密证明 P=NP。
Steve Steiner
问问题
9143 次
11 回答
29
我正在回复这个旧帖子，因为这是一个非常常见且重要的问题，这里的所有答案都是不准确的。
对原始问题的简短回答是明确的“不”。没有已知的基于 NP 完全问题的加密方案（更不用说公钥方案了）（因此所有这些方案都在多项式时间缩减下）。不过，有些人比其他人“更接近”，所以让我详细说明一下。
这里有很多要澄清的地方，所以让我们从“基于 NP 完全问题”的含义开始。对此普遍同意的解释是：“可以在特定的形式模型中证明是安全的，假设不存在针对 NP 完全问题的多项式时间算法”。更准确地说，我们假设不存在总能解决 NP 完全问题的算法。这是一个非常安全的假设，因为这对于算法来说是一件非常困难的事情 - 想出一个以高概率解决问题的随机实例的算法似乎要容易得多。
但是，没有加密方案有这样的证明。如果您查看文献，除了极少数例外（见下文），安全定理如下所示：
定理：假设不存在用于 解决某些问题 X 的随机实例的多项式时间算法，该加密方案可证明是安全的。
注意“随机实例”部分。对于一个具体的例子，我们可以假设不存在多项式时间算法来分解两个随机 n 位素数的乘积，具有一定的良好概率。这与假设不存在多项式时间算法来总是分解两个随机 n 位素数的所有乘积非常不同（不太安全）。
“随机实例”与“最坏情况实例”的问题是上面几个响应者的问题。McEliece 类型的加密方案基于解码线性码的非常特殊的随机版本 - 而不是基于 NP 完全的实际最坏情况版本。
超越这个“随机实例”问题需要对理论计算机科学进行一些深入而美丽的研究。从 Miklós Ajtai 的工作开始，我们发现密码算法的安全假设是“最坏情况”（更安全）的假设，而不是随机情况假设。不幸的是，最坏的情况假设是针对未知的 NP 完全问题，并且一些理论证据表明我们不能将它们调整为使用 NP 完全问题。感兴趣的可以查看“基于格的密码学”。
于 2010-09-06T23:44:40.827 回答
14
一些基于 NP-hard 问题的密码系统已经被提出（如基于子集和问题的Merkle-Hellman密码系统，以及基于背包问题的Naccache-Stern 背包密码系统），但都被破解了。为什么是这样？Scott Aaronson在理论计算机科学中的伟大思想的第 16 讲对此进行了说明，我认为您应该将其视为权威。它说的是以下内容：
理想情况下，我们希望构建一个 [密码伪随机生成器] 或密码系统，其安全性基于 NP 完全问题。不幸的是，NP完全问题总是最坏的情况。在密码学中，这将转化为“存在难以解码的消息”这样的陈述，这对密码系统来说并不是一个很好的保证！消息应该难以以压倒性的概率解密。尽管进行了数十年的努力，但仍未发现将最坏情况与 NP 完全问题的平均情况联系起来的方法。这就是为什么如果我们想要计算安全的密码系统，我们需要做出比 P≠NP 更强的假设。
于 2008-12-11T00:56:34.987 回答
8
这是 1998 年的一个悬而未决的问题：
关于基于 P != NP 假设的密码学的可能性 作者： Oded Goldreich、Rehovot Israel、Shafi Goldwasser
从摘要中：“我们的结论是问题仍然存在”。
——我想知道这在过去十年中是否发生了变化？
编辑：
据我所知，这个问题仍然悬而未决，最近在回答不存在这样的算法方面取得了进展。
Adi Akavia、Oded Goldreich、Shafi Goldwasser 和 Dana Moshkovitz 于 2006年在 ACM 上发表了这篇论文：基于 NP 硬度的单向函数“我们的主要发现是以下两个负面结果”
斯坦福网站Complexity Zoo有助于描述这两个负面结果的含义。
于 2008-11-22T10:09:46.487 回答
4
虽然许多形式已被破坏，但请查看Merkle-Hellman，它基于 NP 完全“背包问题”的一种形式。
于 2008-11-22T08:28:36.893 回答
4
格密码学提供了（过度）广义的带回家的信息，确实可以设计密码系统，其中打破平均情况与解决特定的 NP 难题（通常是最短向量问题或最近向量问题）一样难。
我可以推荐阅读http://eprint.iacr.org/2008/521的介绍部分，然后寻找对密码系统的引用。
此外，请参阅http://www.cs.ucsd.edu/~daniele/CSE207C/上的讲义，如果需要，还可以寻找一本书的链接。
于 2009-02-10T20:52:51.873 回答
2
谷歌搜索 NP 完全和公钥加密会发现误报......实际上是不安全的。这个卡通 pdf似乎显示了基于最小支配集问题的公钥加密算法。进一步阅读它然后承认撒谎该算法是安全的......根本问题是NP-Complete，但它在PK算法中的使用并没有保留难度。
另一个误报 Google 发现：来自 Crypto '97 的 Goldreich-Goldwasser-Halevi 密码系统的密码分析。从摘要：
在 Crypto '97 上，Goldreich、Goldwasser 和 Halevi 提出了一种公钥密码系统，该系统基于点阵中的最接近向量问题，已知该问题是 NP 难的。我们表明，该方案的设计存在一个重大缺陷，它有两个含义：任何密文都会泄露明文上的信息，并且解密密文的问题可以简化为一个特殊的最接近向量问题，这比一般问题要容易得多.
于 2008-11-22T09:34:09.147 回答
1
有一个网站可能与您的兴趣相关：后量子密码学。
于 2010-09-15T14:27:13.013 回答
1
这是我的推理。如我错了请纠正我。
(i) “破解”密码系统在 NP 和 co-NP 中必然是一个问题。（破解密码系统涉及反转加密函数，该函数是一对一且可在多项式时间内计算的。因此，给定密文，明文是可以在多项式时间内验证的证书。因此，根据密文在 NP 和 co-NP 中。）
(ii) 如果 NP 和 co-NP 中存在 NP-hard 问题，则 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-hard 密码系统不存在。
（否则，您在 NP 和 co-NP 中有一个 NP-hard 问题，因此 NP = co-NP---这被认为是错误的。）
于 2010-10-13T03:12:06.630 回答
0
虽然 RSA 和其他广泛使用的密码算法基于整数分解的难度（不知道是 NP 完全问题），但也有一些基于 NP 完全问题的公钥密码算法。谷歌搜索“公钥”和“np-complete”将显示其中一些。
（我之前错误地说过量子计算机会加速 NP 完全问题，但事实并非如此。我是正确的。）
于 2008-11-22T08:28:33.117 回答
0
正如许多其他海报所指出的，可以将密码学建立在 NP-hard 或 NP-complete 问题上。
然而，密码学的常用方法将基于困难的数学（即难以破解）。事实是，将数字序列化为传统键比创建解决 NP 难题的标准化字符串更容易。因此，实际的加密基于尚未证明是 NP-hard 或 NP-complete 的数学问题（因此可以想象其中一些问题在 P 中）。
在 ElGamal 或 RSA 加密中，破解它需要破解离散对数，所以请查看这篇维基百科文章。
没有已知的用于计算一般离散对数 logbg 的有效算法。朴素的算法是将 b 提高到越来越高的 k 次方，直到找到所需的 g；这有时称为试乘法。该算法需要与组 G 的大小成线性关系的运行时间，因此在组大小中的位数是指数的。然而，由于 Peter Shor ( http://arxiv.org/abs/quant-ph/9508027 ) ，存在一种有效的量子算法。
计算离散对数显然很困难。不仅没有已知的最坏情况的有效算法，而且平均情况复杂度可以证明至少与使用随机自约简的最坏情况一样难。
同时，离散取幂的逆问题不是（例如，可以使用平方取幂有效地计算它）。这种不对称类似于整数分解和整数乘法之间的不对称。这两种不对称性都在密码系统的构建中得到了利用。
人们普遍认为这些是 NP 完全的，但可能无法证明是这样。请注意，量子计算机可能会有效地破解密码！
于 2009-02-04T05:53:42.457 回答
-2
由于没有人真正回答这个问题，我必须给你提示：“McEliece”。对其进行一些搜索。它是一种经过验证的 NP-Hard 加密算法。它需要 O(n^2) 的加密和解密时间。它也有一个大小为 O(n^2) 的公钥，这很糟糕。但是有一些改进降低了所有这些界限。
于 2009-11-15T18:04:46.220 回答