如果实际的量子计算成为现实,我想知道是否有任何基于NP完全问题的公钥加密算法,而不是整数分解或离散对数.
编辑:
请查看有关量子计算机的维基文章中的 "计算复杂性理论中的量子计算"部分 . 它指出量子计算机可以回答的问题类别(BQP)被认为比NP完全更容易.
编辑2:
"基于NP-complete"是表达我感兴趣的一种不好的方式.
我打算问的是一个公钥加密算法,其特性是任何破解加密的方法也可用于打破潜在的NP完全问题.这意味着破解加密证明P = NP.
我正在回应这个旧线程,因为这是一个非常普遍和重要的问题,这里的所有答案都是不准确的.
对原始问题的简短回答是明确的"不".没有已知的加密方案(更不用说公钥密钥方案)基于NP完全问题(因此在多项式时间缩减下所有加密方案都是如此).有些人比其他人更"接近",所以让我详细说明.
这里有很多要澄清的内容,让我们从"基于NP完全问题"的含义开始.对此的一般商定解释是:"在特定的形式模型中可以证明是安全的,假设NP完全问题不存在多项式时间算法".更准确地说,我们假设不存在总能解决NP完全问题的算法.这是一个非常安全的假设,因为对于算法来说这是一件非常困难的事情 - 看起来很容易想出一个能够很好地解决问题的随机实例的算法.
但是,没有加密方案有这样的证据.如果你看一下文献,除了极少数例外(见下文),安全定理如下:
定理:假设没有多项式时间算法来解决某些问题X的随机实例,这种加密方案可证明是安全的 .
注意"随机实例"部分.举一个具体的例子,我们可以假设没有多项式时间算法用于以两个很好的概率分解两个随机n位素数的乘积.这与假设不存在用于总是分解两个随机n位素数的所有乘积的多项式时间算法的情况非常不同(不太安全).
"随机实例"与"最坏情况实例"问题是上面几个响应者被绊倒的原因.McEliece类型的加密方案基于解码线性代码的非常特殊的随机版本 - 而不是基于NP完全的实际最坏情况版本.
超越这个"随机实例"问题需要在理论计算机科学方面进行一些深入而美好的研究.从MiklósAjtai的工作开始,我们发现了加密算法,其中安全性假设是"最坏情况"(更安全)的假设而不是随机情况假设.不幸的是,最坏的情况假设是针对未知的NP完全问题,并且一些理论证据表明我们无法使它们适应NP完全问题.对于感兴趣的人,查找"基于格子的密码术".
已经提出了一些基于NP难问题的密码系统(例如基于子集和问题的Merkle-Hellman密码系统,以及基于背包问题的Naccache-Stern背包密码系统),但它们都被打破了.为什么是这样？斯科特·亚伦森(Scott Aaronson)理论计算机科学的伟大构想第16讲对此有所说明,我认为你应该把它作为决定性的.它的内容如下:
理想情况下,我们希望构建一个[加密伪随机生成器]或密码系统,其安全性基于NP完全问题.不幸的是,NP完全问题总是最糟糕的情况.在密码学中,这将转化为" 存在难以解码的消息"这样的语句,这对于加密系统来说不是一个好的保证!消息应该难以以极大的概率解密.尽管已经进行了数十年的努力,但尚未发现将最坏情况与NP完全问题的平均情况联系起来.这就是为什么,如果我们想要计算安全的密码系统,我们需要做出比P≠NP更强的假设.
这是1998年的一个悬而未决的问题:
关于基于 密封术的可能性,假设P!= NP由Oded Goldreich,Rehovot Israel,Shafi Goldwasser
摘要:"我们的结论是问题依然存在".
- 我想知道这在过去十年是否有所改变？
编辑:
据我所知,这个问题仍然是开放的,最近有一个答案,即没有这样的算法存在.
Adi Akavia,Oded Goldreich,Shafi Goldwasser和Dana Moshkovitz在2006 年的ACM中发表了这篇论文:基于NP-硬度的单向函数 "我们的主要发现是以下两个负面结果"
stanford网站Complexity Zoo有助于描述这两个负面结果的含义.
京公网安备 11010802040832号 | 京ICP备19059560号-6 