基於NP完全問題的私鑰加密

十多年前，在 Stack Overflow 上提出了一個問題，基本上是問是否有任何加密方案可以簡化為 NP 完全問題，從某種意義上說，破解加密意味著破解潛在的 NP 完全問題，因此證明 $ P\not=NP $ .

作為一個具體的例子，在假設某些潛在的 NP 完全問題難以解決的情況下，是否存在可以證明是 CPA 安全的對稱密鑰密碼系統？也就是說，如果攻擊者被賦予了兩條消息之一的加密，那麼可以確定哪條消息被加密的算法也可以用於解決潛在的 NP 完全問題（在多項式時間內）？

在最初的 Stack Overflow 問題中，答案是明確的“不”。我今天問這個問題是因為 12 年以上的時間在研究領域是很長的時間，我很好奇在這個問題上是否取得了任何進展。

我們沒有這樣的加密。挑戰之一是最壞情況和平均情況之間的差距。當我們基於一個眾所周知的問題建構加密時，將加密問題簡化為已知的 NP 難題是不夠的。因為對於最難的實例，問題只是 NP 難。我們在加密中生成的實例可能並不難，即使被表述為一個難題。

例如，子圖同構很難，但是用有效的解決方案找到此類問題的族是微不足道的。

我們喜歡在 dlog 這樣的隨機自約問題上建構加密，其中解決隨機實例比解決最難的實例更難。我們有充分的理由相信不存在隨機自約 NP 完全問題，因為這會使多項式層次結構崩潰。

您的問題是專門關於對稱加密的，這更加成問題。證明眾所周知的困難（不是 NP 困難）問題與加密之間的關係是非對稱加密的標準，但在對稱加密中不是。我們領先的對稱原語（如 AES 和 SHA3）與已知的難題無關。

引用自：https://crypto.stackexchange.com/questions/100597