如果 P = NP，是否有一種密碼算法可以保持安全？
據我所知，許多加密算法都是基於這樣的假設，即某些問題是計算困難的，即 NP 完全的。萬一有人證明 P=NP，這些程式碼就會被破解。
是否存在即使 P=NP 也能保持安全的實用加密算法？即，一種算法依賴於比NP完全更困難的問題？
我的猜測是答案是否定的：為了實用，必須在多項式時間內驗證程式碼，即問題必須在 NP 中。這個對嗎？
P = NP 是否是關於算法計算成本作為輸入大小函式的漸近增長的問題。它可能提供有關特定輸入大小的算法的具體計算成本估計的提示，但不提供答案。
在漸近設置的眼中， $ O(n^{10000}) $ 成本“小於” $ O(1.0001^n) $ 成本，因為對於足夠大的值 $ n $ , 越過某個邊界 $ n_0 $ , 的所有值 $ 1.0001^n $ 超過相應的值 $ n^{10000} $ .
這是否意味著一個密碼系統的實例需要花費 $ 128;\text J $ 計算能量和成本 $ 128^{10000};\text J \approx 10^{20000};\text J $ 破解比花費成本的密碼系統更不安全 $ 128;\text J $ 計算和成本 $ 1.0001^{128};\text J \approx 1.01;\text J $ 打破？當然不是！
例如，尋找 $ k \in {0,1}^{128} $ 給定 $ \operatorname{AES}_k(0) $ 需要 $ O(1) $ 時間，因為輸入大小 $ n $ 是一個常數，但這一事實並不意味著它在實踐中的可行性。NFS 和 ECM 成本的漸近增長引導我們走向參數增長曲線，例如RSA，但它們需要具體分析才能獲得對具體參數選擇的信心。
有關這方面的一個特別愚蠢的例子，請參閱
它展示瞭如何利用使用者的漸近成本和攻擊者的漸近成本之間的平變異數來建構密碼系統，並根據具體使用和攻擊成本估計指導**特定輸入大小的建議，這對於富使用者來說幾乎不可用但即使攻擊者可以訪問大型量子電腦，也可能無法觸及。
那麼，是否存在一種漸近多項式時間算法來解決所有 NP 完全問題 $ O(f(n)^{10000}) $ 測試解決方案的時間 $ O(f(n)) $ 多項式時間 $ f $ ? 不，不是。
如果有一個真正驚人的技巧來使用低次多項式，具體來說，計算成本低，這有關係嗎*？*也許吧，但在這一點上這似乎是不可信的——密碼學可能仍然存在高度多項式漸近間隙和使用者和攻擊者成本之間過高的具體差距，即使它們不是指數級的。