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

作者: 你咖喱人biss嗷
发布时间: 2024-10-07 12:04:16 (9天前)
转自：

9 条回复

0#
回复此人
一只特立独行的猪 | 2019-08-31 10-32

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

编辑
1#
回复此人
哈哈哈哈 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 正如许多其他海报所指出的那样，有可能将密码学建立在NP难或NP完全问题上。 </p> <P> 然而，密码学的常用方法将基于困难的数学（难以破解，即）。事实是，将数字序列化为传统密钥比创建解决NP难问题的标准化字符串更容易。因此，实际的加密是基于尚未证明是NP难或NP完全的数学问题（因此可以想象这些问题中的一些存在于P中）。 </p> <P> 在ElGamal或RSA加密中，打破它需要破解离散对数，所以看看这个 <a href="http://en.wikipedia.org/wiki/Discrete_logarithm" rel="nofollow noreferrer"> 维基百科 </A> 文章。 </p> <BLOCKQUOTE> <P> 没有用于计算一般离散对数logbg的有效算法。朴素的算法是将b提高到更高和更高的功率k，直到找到所需的g;这有时被称为试乘。该算法要求运行时间与组G的大小成线性关系，因此在组的大小中以指数表示数字。由于Peter Shor，存在一种有效的量子算法（ <a href="http://arxiv.org/abs/quant-ph/9508027" rel="nofollow noreferrer"> http://arxiv.org/abs/quant-ph/9508027 </A> ）。 </p> <P> 计算离散对数显然很困难。不仅没有针对最坏情况的有效算法，而且平均情况复杂性可以显示为至少与使用随机自还原性的最坏情况一样困难。 </p> <P> 同时，离散求幂的逆问题不是（例如，可以通过求平方来有效地计算）。这种不对称性类似于整数因子分解和整数乘法之间的不对称性。在加密系统的构造中已经利用了这两种不对称性。 </p> </BLOCKQUOTE> <P> 人们普遍认为这些是NP完全的，但可能无法证明这一点。请注意，量子计算机可能会有效地破坏加密！ </p> </DIV>

编辑
2#
回复此人
Moso31 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 虽然许多表格已被打破，但请查看 <a href="http://en.wikipedia.org/wiki/Merkle-Hellman" rel="nofollow noreferrer"> 梅克尔 - 赫尔曼 </A> ，基于NP-complete'背包问题'的形式。 </p> </DIV>

编辑
3#
回复此人
我头上有犄角 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 我正在回应这个旧线程，因为这是一个非常普遍和重要的问题，这里的所有答案都是不准确的。 </p> <P> 对原始问题的简短回答是明确的“不”。没有已知的加密方案（更不用说公钥密钥方案）基于NP完全问题（因此在多项式时间缩减下所有加密方案都是如此）。有些人比其他人更“接近”，所以让我详细说明。 </p> <P> 这里有很多要澄清的内容，让我们从“基于NP完全问题”的含义开始。对此的一般商定解释是：“在特定的形式模型中可以证明是安全的，假设NP完全问题不存在多项式时间算法”。更准确地说，我们假设没有算法存在 <EM> 总是 </EM> 解决了NP完全问题。这是一个非常安全的假设，因为对于算法来说这是一件非常困难的事情 - 看起来很容易想出一个能够很好地解决问题的随机实例的算法。 </p> <P> 但是，没有加密方案有这样的证据。如果你看一下文献，除了极少数例外（见下文），安全定理如下： </p> <BLOCKQUOTE> <P> <EM> 定理： </EM> 假设没有，这种加密方案可证明是安全的存在多项式时间算法的<strong> 解决一些问题的随机实例X. </强> 。 </p> </BLOCKQUOTE> <P> 注意“随机实例”部分。举一个具体的例子，我们可以假设没有多项式时间算法用于以两个很好的概率分解两个随机n位素数的乘积。假设不存在多项式时间算法，这是非常不同的（不太安全） <EM> 总是 </EM> 保理 <EM> 所有 </EM> 两个随机n位素数的乘积。 </p> <P> “随机实例”与“最坏情况实例”问题是上面几个响应者被绊倒的原因。 McEliece类型的加密方案基于解码线性代码的非常特殊的随机版本 - 而不是基于NP完全的实际最坏情况版本。 </p> <P> 超越这个“随机实例”问题需要在理论计算机科学方面进行一些深入而美好的研究。从MiklósAjtai的工作开始，我们发现了加密算法，其中安全性假设是“最坏情况”（更安全）的假设而不是随机情况假设。不幸的是，最坏的情况假设是针对未知的NP完全问题，并且一些理论证据表明我们无法使它们适应NP完全问题。对于感兴趣的人，查找“基于格子的密码术”。 </p> </DIV>

编辑
4#
回复此人
筱梨 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 虽然RSA和其他广泛使用的加密算法是基于整数因子分解的难度（不知道是NP完全的），但也存在一些基于NP完全问题的公钥加密算法。谷歌搜索“公钥”和“np-complete”将揭示其中一些。 </p> <P> （我之前错误地说过，量子计算机会加速NP完全问题，但事实并非如此。我有所纠正。） </p> </DIV>

编辑
5#
回复此人
听风～ | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 格子密码学提供（过）广义的带回家消息，确实可以设计密码系统，其中打破平均情况与解决特定NP难问题（通常是最短向量问题或最近向量问题）一样困难。 </p> <P> 我可以推荐阅读介绍部分 <a href="http://eprint.iacr.org/2008/521" rel="nofollow noreferrer"> http://eprint.iacr.org/2008/521 </A> 然后追逐对密码系统的引用。 </p> <P> 另外，请参阅讲座说明 <a href="http://www.cs.ucsd.edu/~daniele/CSE207C/" rel="nofollow noreferrer"> http://www.cs.ucsd.edu/~daniele/CSE207C/ </A> ，如果你愿意，可以追逐一本书的链接。 </p> </DIV>

编辑
6#
回复此人
v-star*위위 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 有一个网站可能与您的兴趣相关： <a href="http://pqcrypto.org/" rel="nofollow noreferrer"> 后量子密码学 </A> 。 </p> </DIV>

编辑
7#
回复此人
敢嫁就敢娶 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 这是我的推理。如我错了请纠正我。 </p> <P> （i）“破坏”密码系统必然是NP和co-NP中的一个问题。（破解密码系统涉及反转加密函数，它是一对一的，并且在多项式时间内是可计算的。因此，给定密文，明文是可以在多项式时间内验证的证书。因此，基于此查询明文。密文在NP和co-NP中。） </p> <P> （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中。） </p> <P> （iii）我 <EM> 认为 </EM> 一般认为NP！= co-NP，否则有多项式大小证明布尔公式是不可满足的。 </p> <P> 结论：复杂性理论推测意味着NP-hard密码系统不存在。 </p> <P> （否则，你在NP和co-NP中存在NP难问题，NP = co-NP--这被认为是假的。） </p> </DIV>

编辑

登录后才能参与评论