Paper 2019/151

Solving binary MQ with Grover's algorithm

Peter Schwabe and Bas Westerbaan


The problem of solving a system of quadratic equations in multiple variables---known as multivariate-quadratic or MQ problem---is the underlying hard problem of various cryptosystems. For efficiency reasons, a common instantiation is to consider quadratic equations over $\F_2$. The current state of the art in solving the \MQ problem over $\F_2$ for sizes commonly used in cryptosystems is enumeration, which runs in time $\Theta(2^n)$ for a system of $n$ variables. Grover's algorithm running on a large quantum computer is expected to reduce the time to $\Theta(2^{n/2})$. As a building block, Grover's algorithm requires an "oracle", which is used to evaluate the quadratic equations at a superposition of all possible inputs. In this paper, we describe two different quantum circuits that provide this oracle functionality. As a corollary, we show that even a relatively small quantum computer with as little as 92 logical qubits is sufficient to break MQ instances that have been proposed for 80-bit pre-quantum security.

Available format(s)
Publication info
Published elsewhere. MINOR revision.Security, Privacy, and Applied Cryptography Engineering (SPACE 2016)
Grover's algorithmmultivariate quadraticsquantum resource estimates
Contact author(s)
peter @ cryptojedi org
bas @ westerbaan name
2019-02-20: received
Short URL
Creative Commons Attribution


      author = {Peter Schwabe and Bas Westerbaan},
      title = {Solving binary MQ with Grover's algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2019/151},
      year = {2019},
      doi = {10.1007/978-3-319-49445-6_17},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.