Exploiting Preprocessing for Quantum Search to Break Parameters for MQ Cryptosystems
Exploiting Preprocessing for Quantum Search to Break Parameters for MQ Cryptosystems
复制标题
利用量子搜索预处理来破坏 MQ 密码系统的参数
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Benjamin Pring
中科院分区：
文献类型：
--
作者：
Benjamin Pring
本文重新考察了量子搜索在有限域GF(2)上的多元二次((数学{mq}))难度问题中的应用。这个问题是后量子公钥密码体制安全性的关键，这些公钥密码体制被设计用来抵抗来自量子计算机的攻击。在这篇文章中，我们警告说，基于量子搜索算法的效率推断参数是危险的。我们的方法表明，通过对(数学{mq})问题进行预处理，我们可以减少量子计算机上的计算量，并且，在对单目标的多目标搜索的推广中，提高了对GF(2)上的(数学{mq})问题的基本量子搜索预言的效率。我们的工作建立在Westbaan和Schwabe[19]引入的(Mathcal{MQ})预言的基础上，并对其进行了改进，从而打破了原作者提出的Gui密码系统[16]的所有量子抵抗安全参数[15]。我们的结果在逻辑门模型下和算法完全按Clifford+T通用门集计算时都成立。
In this paper we re-examine quantum search applied to the Multivariate Quadratic ((mathcal {MQ})) hardness problem over the finite field GF(2). This problem is key to the security of a number of proposed post-quantum public-key cryptosystems designed to be resistant against attacks from quantum computers and in this paper we give a warning of the dangers of extrapolating parameters based upon the efficiency of quantum search algorithms. Our methods demonstrate that by applying preprocessing to the (mathcal {MQ}) problem, we can reduce the computational load on the quantum computer and, in a generalisation of multi-target search for single-targets, improve the efficiency of the basic quantum search oracle for the (mathcal {MQ}) problem over GF(2). Our work builds upon the (mathcal {MQ}) oracle introduced by Westerbaan and Schwabe [19] and improves it to the extent that it breaks all quantum-resistant security parameters for the Gui cryptosystem [16] proposed by the original authors [15]. Our results hold both in the logical gate model and when the algorithm is fully costed in terms of the Clifford+T universal gate set.