One-Way-Function
如果磷≠N磷P≠NPP neq NP為什麼這不能證明OWF的存在?
我知道 $ P = NP \Rightarrow $ 不存在OWF。但我不明白為什麼聲稱: $ P \neq NP \Rightarrow $ OWF的存在有錯嗎?
一個直覺的答案就足夠了。
Goldwasser 和 Bellare 講義中的答案。P≠NP 不是一個充分的。P ≠ NP 僅意味著加密方案在最壞的情況下難以破解。不排除加密方案幾乎在所有情況下都容易被破解的可能性。事實上,人們可以很容易地構造破解問題是 NP 完全的“加密方案”,但存在一種有效的破解算法,它可以在 99% 的情況下成功。因此,最壞情況的硬度是一種較差的安全性度量。安全性需要大多數情況下的硬度或至少平均情況下的硬度。因此,安全加密方案存在的一個必要條件是 NP 中存在平均難的語言。此外,不知道 P≠ NP 是否意味著 NP 中存在平均難的語言。