是否存在可证明NP难以击败的公钥加密算法？ [关闭]

https://stackoverflow.com/questions/311064

10-07-2019
|

题

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

编辑：

请查看<！>“计算复杂性理论中的量子计算<！>”;部分关于量子计算机的维基文章。它指出量子计算机可以回答的问题类别（BQP））被认为比NP完全更容易。

编辑2：

'基于NP-complete'是表达我感兴趣的一种不好的方式。

我打算问的是一个公钥加密算法，其特性是任何破解加密的方法也可用于打破潜在的NP完全问题。这意味着破解加密证明P = NP。

解决方案

我正在回应这个旧帖子，因为这是一个非常普遍而重要的问题，而且这里的所有答案都是不准确的。

对原始问题的简短回答是明确的<！>“NO <！>”。没有已知的加密方案（更不用说公钥密钥方案）基于NP完全问题（因此在多项式时间缩减下所有加密方案都是如此）。有些是<！>“;更接近<！>”;但是，其他人，让我详细说明。

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

但是，没有加密方案有这样的证据。如果你看一下文献，除了极少数例外（见下文），安全定理如下：

定理：这种加密方案可证明是安全的，假设没有存在多项式时间算法 解决某些问题的随机实例X 。

注意<！> quot; random instances <！> quot;部分。举一个具体的例子，我们可以假设没有多项式时间算法用于以两个很好的概率分解两个随机n位素数的乘积。这与假设总是分解两个随机n位素数的所有乘积的多项式时间算法非常不同（不太安全）。

<！>“随机实例<！>”;与<！>;最坏情况实例<！>问题是上面的几个响应者被绊倒了。 McEliece类型的加密方案基于解码线性代码的非常特殊的随机版本 - 而不是基于NP完全的实际最坏情况版本。

超越此<！>“随机实例<！>”;问题需要在理论计算机科学方面进行一些深入而美好的研究从Mikl <！>＃243; s Ajtai的工作开始，我们发现了加密算法，其中安全假设是<！>“最坏情况<！>”; （更安全）假设而不是随机案例。不幸的是，最坏的情况假设是针对未知的NP完全问题，并且一些理论证据表明我们无法使它们适应使用NP完全问题。对于感兴趣的人，请查找<！> quot;基于格子的加密<！>“。

其他提示

已经提出了一些基于NP难问题的密码系统（例如 Merkle-Hellman 基于子集和问题的密码系统，以及基于 Naccache-Stern背包密码系统的密码系统关于背包问题），但他们都被打破了。为什么是这样？ Scott Aaronson的第16讲理论计算机科学的伟大构想谈到这一点，我认为你应该把它当作权威。它的内容如下：

理想情况下，我们想构建一个[加密伪随机生成器]或密码系统，其安全性基于NP完全问题。不幸的是，NP完全问题总是最糟糕的情况。在密码学中，这将转换为类似<！>＃8220; 存在的消息，<！>＃8217;难以解码<！>＃8221;这不是一个好消息保证加密系统！消息应该难以以极大的概率解密。尽管已经进行了数十年的努力，但尚未发现将最坏情况与NP完全问题的平均情况联系起来。这就是为什么，如果我们想要计算安全的密码系统，我们需要做出比P <！>＃8800; NP更强的假设。

这是1998年的一个悬而未决的问题：

关于在假设P！的基础上建立密码学的可能性。 = NP 作者：Oded Goldreich，Rehovot Israel，Shafi Goldwasser

摘自：<！>;我们的结论是问题仍然存在<！>“。

- 我想知道过去十年是否有所改变？

编辑：

据我所知，这个问题仍然存在，最近在答案中没有这样的算法存在。

Adi Akavia，Oded Goldreich，Shafi Goldwasser和Dana Moshkovitz于2006年在ACM上发表了这篇论文：基于NP-硬度的单向函数 <！>;我们的主要发现是以下两个负面结果<！>

stanford网站复杂性动物园有助于描述这两个负面结果的含义。

虽然许多表格已被破坏，但请查看 Merkle-Hellman ， NP-complete“背包问题”的一种形式。

格子密码学提供（过）广义的带回家消息，确实可以设计密码系统，其中打破平均情况与解决特定NP难问题（通常是最短向量问题或最近向量问题）一样困难。

我可以推荐阅读 http://eprint.iacr.org/2008/521的介绍部分然后追逐对密码系统的引用。

另请参阅 http://www.cs.ucsd上的讲义。 edu / ~daniele / CSE207C / ，如果你愿意，可以追逐一本书的链接。

谷歌搜索NP完整和公钥加密发现误报......实际上是不安全的。这个卡通的pdf 似乎显示出来了基于最小化支配集问题的公钥加密算法。进一步阅读它然后承认说算法是安全的......潜在的问题是NP-Complete但它在PK算法中的使用并不能保持难度。

Google发现另一个误报：

有一个网站可能与您的兴趣相关：后量子密码学。

这是我的推理。如果我错了，请纠正我。

（i）“破坏”密码系统在NP和co-NP中必然是一个问题。（破解密码系统涉及反转加密函数，它是一对一的，并且在多项式时间内是可计算的。因此，给定密文，明文是可以在多项式时间内验证的证书。因此，基于此查询明文。密文在NP和共同NP中。）

（ii）如果NP和co-NP存在NP难问题，那么NP = co-NP。（这个问题将是NP完全的并且在共同NP中。由于任何NP语言可以简化为这种共同NP语言，NP是co-NP的子集。现在使用对称性：co-NP中的任何语言L具有-L NP中的（恭维），其中-L在共同NP中 - 即L = --L在NP中。）

（iii）我认为通常认为NP！= co-NP，否则有多项式大小证明布尔公式是不可满足的。

结论：复杂性理论推测意味着NP-hard密码系统不存在。

（否则，你在NP和co-NP中存在NP难问题，NP = co-NP--这被认为是错误的。）

虽然RSA和其他广泛使用的加密算法是基于整数分解的难度（不知道是NP完全的），但也存在一些基于NP完全问题的公钥加密算法。谷歌搜索<！>“;公钥<！>”;和<！>“; np-complete <！>”;将揭示其中一些。

（之前我错误地说过，量子计算机会加速NP完全问题，但事实并非如此。我有所纠正。）

正如许多其他海报所指出的那样，有可能将密码学建立在NP难或NP完全问题上。

然而，密码学的常用方法将基于困难的数学（难以破解，即）。事实是，将数字序列化为传统密钥比创建解决NP难问题的标准化字符串更容易。因此，实际的加密是基于尚未证明是NP难或NP完全的数学问题（因此可以想象其中一些问题在P中）。

在ElGamal或RSA加密中，打破它需要破解离散对数，所以请看这个 wikipedia 文章。

没有用于计算一般离散对数logbg的有效算法。朴素的算法是将b提高到更高和更高的功率k，直到找到所需的g;这有时被称为试乘。该算法要求运行时间与组G的大小成线性关系，因此需要指数组大小的位数。然而，由于Peter Shor存在一种有效的量子算法（ http://arxiv.org/abs/定量-PH / 9508027 ）。

计算离散对数显然很困难。不仅没有针对最坏情况的有效算法，而且平均情况复杂性可以显示为至少与使用随机自还原性的最坏情况一样难。

同时，离散求幂的逆问题不是（例如，可以通过求平方来有效地计算）。这种不对称性类似于整数因子分解和整数乘法之间的不对称性。在加密系统的构建中已经利用了这两种不对称性。

人们普遍认为这些是NP完全的，但可能无法证明这一点。请注意，量子计算机可能会有效地破坏加密！

由于没有人真正回答这个问题，我必须给你提示：<！>“McEliece <！>”;做一些搜索。它是一种经过验证的NP-Hard加密算法。它需要O（n ^ 2）加密和解密时间。它有一个大小为O（n ^ 2）的公钥，这很糟糕。但是有一些改进降低了所有这些界限。

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow