可以將量子算法搜尋（Grover 算法）用於差分和線性攻擊的新搜尋策略

我正在嘗試使用 Grover 的算法來查找 Feistel 和 SPN 結構塊密碼的差分特徵。基本上，這是在（相關密鑰）差分攻擊中以高機率找到一個好的差分特徵

例如，Ivica Nikolic 的 Alex Biryukov 使用 Matsui 的算法搜尋 DES 類密碼中的相關密鑰差異特徵。：FSE 2011

還使用基於整數規劃的方法（使用混合整數線性規劃的差分和線性密碼分析），作者 Nicky Mouha、Qingju Wang、Dawu Gu、Bart Preneel Inscrypt 2011。

我的問題

可以構造 Grover 算法來查找 Feistel 和 SPN 結構塊密碼的微分特徵嗎？

Grover 算法是一種機率量子算法，它（以高機率）找到產生特定輸出值的黑盒函式的唯一輸入，使用

$$ O({\sqrt {N}}) $$函式的評估，其中函式具有大小域 $ N $ . 是函式域的大小。 請記住，spedup 只是二次的，與 Shor 的算法不同，它在不同的問題上提供指數加速，它可以應用於有限域上的任何搜尋問題。

在對稱加密設置中，通常建議的對該算法的對策是相當溫和的：對稱密鑰長度可以加倍以補償風險。

**編輯：**對於多對象搜尋 $ \ell $ 對象，博耶等。人。in 1證明了以下定理，正如@poncho 在評論中指出的那樣，這有點違反直覺。

**定理：（**釋義）假設 $ \ell/N $ 是小。然後任何搜尋算法 $ \ell $ 對象，形式為$$ grover search $$ 平均取 $ O(\sqrt{N/\ell}) $ 迭代以便以正機率成功 $ >1/2 $ 獨立於 $ N $ 和 $ \ell. $

1. M. Boyer、G. Brassard、P. Høyer 和 A. Tapp，量子搜尋的嚴格界限，Fortsch。物理。46 (1998), 493–506。在此處查看有關 arXiv 的相關論文

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