Fast Quantum Algorithm for Solving Multivariate Quadratic Equations
This work addresses the quantum security evaluation of post-quantum cryptosystems, a critical issue for standardization bodies and cryptographic applications, though it appears incremental as it builds on existing quantum approaches.
The paper tackles the problem of solving systems of Boolean multivariate quadratic equations (MQb), a central challenge in post-quantum cryptography, by presenting a Las-Vegas quantum algorithm that requires an average of O(2^{0.462n}) quantum gates, which is claimed to be the fastest known method.
In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency NSA concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of {\it $m$ Boolean multivariate quadratic equations in $n$ variables} (\MQb); a central problem in post-quantum cryptography. When $n=m$, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving \MQb{} that requires the evaluation of, on average, $O(2^{0.462n})$ quantum gates. To our knowledge this is the fastest algorithm for solving \MQb{}.