可以使用量子算法搜索(Grover's算法)对差分和线性攻击进行新的搜索策略。

Question

我试图使用Grover算法来寻找Feistel和SPN结构块密码的微分特性。基本上，它是在(相关键)差别化攻击中找到一个高概率的良好的微分特性。

例如，使用Matsui的算法在DES类密码中搜索相关的关键差分特性，由Alex Biryukov，Ivica Nikolic.：FSE 2011。

还使用整数规划的方法(微分和线性密码分析使用混合整数线性规划)，由尼基穆哈，王庆菊，大武谷，巴特Preneel Inscrypt 2011。

我的问题

能否构造Grover算法来寻找Feistel和SPN结构块密码的微分特性？

Answer 1

Grover算法是一种概率量子算法，它使用函数的$$ O({\sqrt {N}}) $$求值法(其中函数具有大小为$N$的域)查找(高概率)对产生特定输出值的黑箱函数的唯一输入。函数域的大小。

考虑到加速比只是二次型的事实，与Shor算法不同，Shor算法在不同的问题上提供指数加速，它可以应用于有限域上的任何搜索问题。

在对称密码设置中，通常建议的该算法的对策是相当温和的:对称密钥长度可以加倍以补偿风险。

编辑：用于多对象搜索$\ell$对象，Boyer等。阿尔。在1中，正如@poncho在评论中指出的那样，证明了以下定理是有点违背直觉的。

定理：(释义)假定$\ell/N$是小的。然后，对$\ell$对象的任何搜索算法，以平均$O(\sqrt{N/\\ell})$迭代的形式进行，以获得成功的概率$>1/2$，独立于$N$和$\ell.$。

1. 作者声明：[ on ] M. Boyer，G. Brassard，P. H yer和A. Tapp，量子搜索，Fortsch.太棒了。46 (1998)，493-506。见关于arXiv 这里的相关论文