有没有证明是NP难以克服的公钥密码算法？

作者: 只怕再见是故人
发布时间: 2024-12-10 11:52:03 (1月前)

2 条回复

1#
回复此人
春风助手 | 2020-08-21 16-17

我正在回应这个旧主题，因为这是一个非常常见且重要的问题，并且此处的所有答案都不准确。原始问题的简短答案是明确的“否”。没有已知的基于NP完全问题的加密方案（更不用说公共密钥方案了）（因此，在多项式时间减少的情况下，所有方案都是如此）。但是，有些与其他人“更接近”，所以让我详细说明一下。这里有很多要澄清的地方，所以让我们从“基于NP完全问题”开始。通常对此的解释是：“可以假定在不存在用于NP完全问题的多项式时间算法的情况下，在特定的形式模型中被证明是安全的”。更精确地说，我们假设不存在总能解决NP完全问题的算法。这是一个非常安全的假设，因为对于算法而言，这确实是一件很难的事-提出一种算法以较高的概率解决问题的随机性似乎要容易得多。但是，没有加密方案有这种证明。如果看文献，除了极少数例外（请参阅下文），安全性定理如下所示：定理：假设不存在求解某些问题X的随机实例的多项式时间算法，则该加密方案是可证明的安全性。注意“随机实例”部分。举一个具体的例子，我们可能假设不存在用于以一定的概率将两个随机n位素数的乘积分解为因子的多项式时间算法。这与假设不存在用于始终分解两个随机n位素数的所有乘积的多项式时间算法完全不同（不太安全）。 “随机实例”与“最坏实例”的问题是上述几个响应者所遇到的问题。McEliece类型的加密方案基于解码线性代码的非常特殊的随机版本-而不是基于NP完整的实际最坏情况版本。超越“随机实例”的问题，需要对理论计算机科学进行一些深入而优美的研究。从MiklósAjtai的工作开始，我们发现了加密算法，其中安全性假设是“最坏情况”（更安全）的假设，而不是随机情况。不幸的是，最坏的情况假设是针对未知的NP完全问题，并且一些理论证据表明我们无法使其适应NP完全问题。对于感兴趣的人，请查找“基于格的加密”。

编辑

登录后才能参与评论