为了安全，需要一个1-1密码映射是NP-完全？

Question

“密码学基础”一书指出：

据了解，与破坏1-1密码映射有关的问题不可能是NP-完全的，更重要的是，破缺任务的NP-硬度是密码安全性的不良证据。

但我认为复杂性理论的全部目的是确定哪些问题是NP，这样我们才能利用它们的解决方案的不可行性来产生安全性？

Answer 1

NP是最坏的情况下的硬度。在大多数情况下，NP难问题实际上是很容易解决的。这显然是一个糟糕的密码系统。此外，一些NP难问题甚至可能很容易近似。这也可能对密码学不利。