为什么没有基于已知的NP问题的加密算法？

Question

当今的大多数加密，例如RSA，都依赖整数分解，这并不认为是NP硬性问题，但它属于BQP，这使其容易受到量子计算机的影响。我想知道，为什么没有基于已知NP问题的加密算法。听起来（至少从理论上讲）听起来像是与未被证明是NP hard的一种更好的加密算法。

Answer 1

NP完整问题的最坏情况不足以使其用于密码学。即使在最坏的情况下（$ p ne np $）中NP完整问题很难，但在平均值中仍然可以有效地解决。密码学假设NP中存在平均案例棘手的问题。同样，使用$ p ne np $假设证明NP中存在强度的问题是一个主要的开放问题。

一本精彩的读物是Russell Impagliazzo的经典作品， 平均案例复杂性的个人观点, 1995.

一个很好的调查是 平均案例复杂性 Bogdanov和Trevisan撰写，理论计算机科学的基础和趋势卷。 2，第1号（2006）1-106

Answer 2

有。

一个这样的例子是 mceliece密码系统 这是基于解码线性代码的硬度。

第二个例子是 ntruencrypt 这是基于最短的向量问题，我认为这是NP-HARD。

另一个是 Merkle-Hellman Knapsack加密系统 这已经打破了。

注意：如果前两个被打破/它们有多好，我不知道。我所知道的是它们存在，我从进行网络搜索中得到了这些人。

Answer 3

我可以想到并非完全独立的四个主要障碍：

• NP硬度只为您提供有关复杂性的信息 在极限. 。对于许多NP完整问题，存在算法，可以合理地解决所有感兴趣的实例（在某种情况下）。换句话说，对于任何 固定的 问题大小（例如给定的“键”），问题不一定仅仅是因为它是NP-HARD。
• NP硬度仅考虑最差的时间。许多，甚至大多数实例都可能易于使用现有算法解决。即使我们知道如何表征硬实例（Afaik，我们没有），我们仍然必须找到它们。
• 你需要 巨大的 难以解决的实例。从搜索空间是平坦的意义上，搜索（）较大的质量数字很容易：一个数字是否适合。想象一下使用图形：在所有$ 2^{n（n-1）} $ size $ n $的图形中，您必须找到具有不错属性的$ n $。
• 您需要某种可逆性。例如，任何整数都是通过其主要分解来唯一描述的。图像我们要使用TSP作为加密方法；鉴于所有最短的旅行，您（重新）可以构造它们来自独特的图表吗？

请注意，我没有密码学专业知识；这些仅仅是算法。复杂性理论异议。

Answer 4

我们今天知道的公开密码学是建立在 单程 陷阱门 排列，板门是必不可少的。

为了使协议公开安全，您需要任何人可用的键，以及一种使用此密钥加密消息的方法。显然，一旦加密，就应该很难恢复只知道其密码和公共密钥的原始消息：只能使用一些额外的信息，即您的私钥。

考虑到这一点，很容易构建 原始 加密系统基于任何单向板门排列。

1. 爱丽丝将单向置换给公众，并将陷阱门保持在自己身上。
2. 鲍勃将其输入放在排列中，并将输出传输到爱丽丝。
3. 爱丽丝（Alice）使用陷阱门以鲍勃（Bob）的输出来倒入置换。

现在的困难是找到实际的单向板门排列，并且我们认为有很多功能是好的候选者（RSA，离散对数，关于晶格问题的一些变化）。但是，如果我们可以肯定地找到单向功能，那么我们还证明了$ mathsf {p} ne ne mathsf {np} $，因此实际上证明函数是单向的。

另一方面，如果我们证明$ mathsf {p} ne ne mathsf {np} $，我们还证明了$ mathsf {npi} $（InterMediate）之间存在一个类， $ mathsf {np} $，而不是$ mathsf {np} $ - 硬。 $ mathsf {npi} $中问题的一些好候选人也是单向排列的候选人，因为我们尚未证明它们是$ mathsf {np} $ - 硬。

因此，要回答您的问题，我们不使用$ mathsf {np} $ - 硬问题，因为我们需要陷阱的单向置换，并且这些特殊功能 大概 活在$ mathsf {np} $和$ mathsf {np} $ - 硬的类中。

Answer 5

只是基于实践经验提出启发式论点。

几乎所有的实例（几乎所有NP完整问题）都很容易解决。在某些问题上，这不是真的，但是很难找到，而且很难积极，您听起来像这样的课。

当人们试图为一些著名的NP完整班级编写随机问题生成器时，这是在实践中多次出现的，例如约束编程，SAT或旅行推销员。在以后的某个日期，有人发现了一种求解几乎随机生成器产生的所有实例的方法。当然，如果是加密系统的情况，我们将遇到严重的麻烦！

Answer 6

Merkle-Hellman密码系统基于二进制背包问题（子集总和）。