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

Question

已关闭。这个问题是 off-topic 。目前不接受答案。

---

想要改进这个问题吗？ Update the question所以它是on-topic用于堆栈溢出。

已关闭10 年前。

Improve this question

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

编辑:

请查看“计算复杂性理论中的量子计算”部分 the wiki article on quantum computers.它指出，量子计算机可以回答的一类问题(BQP)被认为比 NP 完全问题更容易。

编辑2:

“基于 NP 完全”是表达我感兴趣的内容的糟糕方式。

我想要的是一种公钥加密算法，其属性是任何破解加密的方法也可以用来破解底层的 NP 完全问题。这意味着破解加密证明 P=NP。

Answer 1

我回复这个旧帖子是因为这是一个非常常见且重要的问题，并且这里的所有答案都不准确。

对原始问题的简短回答是明确的“否”。没有已知的加密方案(更不用说公钥方案)是基于 NP 完全问题(因此所有这些方案都在多项式时间约简下)。不过，有些比其他“更接近”，所以让我详细说明一下。

这里有很多需要澄清的地方，所以让我们从“基于 NP 完全问题”的含义开始。对此普遍同意的解释是:“假设对于 NP 完全问题不存在多项式时间算法，可以在特定的形式模型中证明安全”。更准确地说，我们假设不存在总是解决 NP 完全问题的算法。这是一个非常安全的假设，因为这对于算法来说是一件非常困难的事情 - 提出一种以良好概率解决问题的随机实例的算法似乎要容易得多。

不过，没有加密方案有这样的证明。如果您查看文献，除了极少数异常(exception)(见下文)，安全定理如下所示:

Theorem: This encryption scheme is provably secure, assuming that no polynomial-time algorithm exists for solving random instances of some problem X.

请注意“随机实例”部分。举一个具体的例子，我们可能假设不存在多项式时间算法来以一定的概率分解两个随机 n 位素数的乘积。这与假设不存在用于总是因式分解两个随机 n 位素数的所有乘积的多项式时间算法有很大不同(不太安全)。

“随机实例”与“最坏情况实例”问题是上述几位响应者所困扰的问题。 McEliece 型加密方案基于解码线性代码的非常特殊的随机版本 - 而不是基于 NP 完全的实际最坏情况版本。

要超越这个“随机实例”问题，需要在理论计算机科学方面进行一些深入而精彩的研究。从 Miklós Ajtai 的工作开始，我们发现了密码算法，其中安全假设是“最坏情况”(更安全)假设，而不是随机情况假设。不幸的是，最坏的情况假设是针对未知的 NP 完全问题，并且一些理论证据表明我们无法调整它们以使用 NP 完全问题。如果有兴趣，请查找“基于格的密码学”。