新論文聲稱對 AES 的量子多對數時間攻擊
眾所周知，Grover 算法可以解決 AES $ O(\sqrt{n}) $ 這就是為什麼對稱密鑰長度需要加倍才能在面對量子對手時保持其安全級別的原因。 最近的一篇電子印刷論文聲稱，使用量子電腦對 AES（或一般搜尋未排序集）存在多對數時間攻擊。熟悉量子計算的人可以評論這次攻擊的有效性嗎？
我同意 Xavier Bonnetain per lamba 的回答，但可以為正在發生的事情添加更多內容。
使用所提出的算法 $ n $ -位搜尋空間，尋找解決方案 $ x $ 至 $ f(x)=y $ , 這個想法是首先準備 $ n/2 $ 銀行 $ n $ 完全疊加的單個量子位寄存器（例如，通過使用 $ n^2/2 $ 哈達瑪門）。對於每組寄存器，我們然後使用另一個 $ n $ 單個量子位寄存器來計算函式 $ f $ （在密碼分析範例中，它被視為具有從輸入寄存器獲取的可變密鑰並在固定明文上操作的分組密碼，但我認為沒有充分的理由不應用一般的 Grover 問題）。因此我們有 $ n/2 $ 國家副本 $$ \frac1{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle|f(x)\rangle. $$ 事實上，每個狀態只需要兩個不同的位 $ f(x) $ , 所以上面可以通過一個呼叫來完成 $ f(x) $ 而不是 $ n/2 $ 來電。如果我們寫 $ S_i $ 為了 $ i $ 我們現在對 Grover 算法進行一次迭代以尋找解決方案 $ x $ 這樣 $ f_{2i,2i+1}(x)=y_{2i,2i+1} $ 其中下標表示僅考慮索引位（即我們查找所有 $ x $ 使得 $ 2i $ 和 $ (2i+1) $ 第 位 $ f(x) $ 匹配對應的位 $ y $ ）。這是一個 2 位的搜尋空間，我們希望 Grover 的算法能夠在一次迭代中成功，並且大約 1/4 的搜尋空間與條件匹配。
我們的每一個 $ n/2 $ 銀行現在大致由 $ 2^{n/2-1} $ 與其他有效零振幅狀態的平衡疊加狀態： $$ S_i=\frac1{2^{n/2-1}}\sum_{x=0\atop f_{2i,2i+1}(x)=y_{2i,2i+1}}^{2^n-1}|x\rangle|f(x)\rangle $$ 請注意，唯一 $ x $ 值出現在所有 $ n/2 $ 疊加是與 $ f(x)=y $ . 這裡似乎沒有對比特對劃分的關鍵依賴；例如，可以分為 $ n/k $ 銀行並考慮六倍位和使用 $ O(2^{k/2}) $ Grover 迭代。
作者現在觀察到，如果我們可以對每個值的幅度進行Hadamard 積（分量積） $ x $ 橫跨 $ n/2 $ 銀行，然後所有非因果價值 $ x $ 將至少有一個幅度為零的銀行（即至少一個銀行，其中 $ f(x) $ 未能匹配的兩個位 $ y $ ）。在這種情況下，唯一的非零幅度將是 $ x $ 我們尋求和測量應該恢復它們。這隱含地假設 Hadamard 乘積內的幅度重新正規化。
有量子計算背景的人此時會擔心，因為 Hadamard 乘積不可逆，因此不是酉變換。然而，該論文指出，Hadamard 乘積是Zhao 等人的論文為量子電腦編譯基本線性代數子程序中涵蓋的眾多矩陣運算之一。將 Zhao 論文視為計算重整化 Hadamard 產品的黑盒資源，然後給出結果。但是，我認為趙的論文並不完全以這種方式工作。在 Zhao 的論文中，通過將問題嵌入到更大的酉系統中併計算 Hadamard 乘積的近似值來計算 Hadamard 乘積。因果解的幅度超指數小（大約 $ 2^{-n^2/4} $ ) 並且會失去在近似值的雜訊中。也許更準確地說，要足夠準確地近似答案將需要成倍增長的資源集。我打算更深入地閱讀趙的論文以對此進行擴展。