Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

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{}.