P=NP 世界中的對稱加密
我希望能找到關於攻擊 AES 的量子計算洞察力的答案；然而，這個問題的答案並不適用，因為“量子電腦在（原文如此）一般搜尋問題上給出了二次加速”。
讓我們假設最壞的情況：通過建設性證明 P=NP。因此，對 AES 和所有其他標準模型對稱密碼的 3-SAT 和直接多項式攻擊。
除了使用 ECB 和每個密鑰發送一個塊之外，我們如何建構需要嚴重攻擊才能破解的東西？是否真的存在具有與一次性密碼不同的屬性的量子證明對稱密碼？
我想我可以證明，如果您使用除多項式評估 MAC（或具有其特徵可否認性的其他東西）以外的任何類型的 MAC，您的密碼必須失敗。
我可以證明加密的隨機數據是可能的，因為您無法通過隨機數據破壞 ECB，但該證明是無用的。
我知道最終進入這個 P=NP 的世界是不合理的。我也知道這篇舊文章描述了為什麼 P=?NP 是一個糟糕的易碎性模型的很好的理由。我對這個問題很感興趣，因為我有理由確定任何解決方案都必須使用一種本身可否認的加密方法。
一次性便箋具有此屬性；但是，如果可能的話，我寧願提供一個不那麼笨拙的答案。
需要注意的重要一點是 $ \mathsf{P} = \mathsf{NP} $ 不會從根本上威脅密碼學——甚至是理論上的密碼學。正如 Meir Maor 在他的回答中提到的那樣，這意味著沒有單向函式，這意味著基本上沒有“傳統”密碼學。
然而，單向函式和大多數密碼學在理論上被定義為需要在最佳攻擊和算法的誠實使用之間存在超多項式差距。不過，如果明天你證明 $ \mathsf{P} = \mathsf{NP} $ , 仍然可以存在需要時間的函式 $ n $ 計算，但時間 $ n^{10} $ 反轉。這一點也不矛盾 $ \mathsf{P} = \mathsf{NP} $ . 然而，這對於所有實際目的來說就足夠了：採取 $ N = 2^{10} $ ，然後評估您的函式需要 $ 2^{10} $ 步驟，同時反轉它需要 $ 2^{100} $ 腳步。對於大多數用途來說，這個安全邊際已經足夠了。
這樣的單向函式，其中求值和反演之間的差距是一個固定多項式而不是超多項式，稱為細粒度單向函式。它們是密碼學中一個新興的研究主題（參見最近的這篇論文），主要是因為它們在理論上可以從比那些已知暗示標準 OWF 的假設更弱的假設中建構出來（即使從一個通用的、很好的- 不被認為暗示 OWF 的研究假設到今天仍然是一個懸而未決的問題）。它們可用於建構細粒度的偽隨機生成器和流密碼。
這似乎並不荒謬，如果我們證明 $ \mathsf{P} = \mathsf{NP} $ ，我們對 AES 的最佳攻擊仍然需要 $ n^{10} $ 腳步。在這種情況下，經過一些適當的密鑰大小調整，每個人都會繼續使用好的舊 AES，就好像什麼都沒發生過一樣，理論密碼學家將替換“假設這個 OWF 需要 $ \mathsf{superpoly}(n) $ 通過“假設這個 OWF 採取的步驟來打破” $ n^{10} $ 打破的步驟”。
如果 P=NP 沒有單向函式，則沒有陷門單向函式，基本上沒有密碼學。
如果 P = NP，則意味著驗證密鑰和找到密鑰同樣困難（最多多項式歸約）。所以一次性墊仍然可以工作，它們在理論上是安全的，並且不依賴於計算難度。但是所有加密，無論是否對稱，散列等都變得不安全。
實際上，量子密鑰交換可能會拯救我們，它將允許非加密安全通道用於共享密鑰材料，然後允許一次性密碼。
值得注意的是，即使 P 不等於 NP，我們也有可能生活在密碼學中。我們不知道單向函式的存在，它們可能不存在，即使 P!=NP