**Solving binary MQ with Grover's algorithm**

*Peter Schwabe and Bas Westerbaan*

**Abstract: **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.

**Category / Keywords: **Grover's algorithm, multivariate quadratics, quantum resource estimates

**Original Publication**** (with minor differences): **Security, Privacy, and Applied Cryptography Engineering (SPACE 2016)
**DOI: **10.1007/978-3-319-49445-6_17

**Date: **received 13 Feb 2019

**Contact author: **peter at cryptojedi org, bas at westerbaan name

**Available format(s): **PDF | BibTeX Citation

**Version: **20190220:172926 (All versions of this report)

**Short URL: **ia.cr/2019/151

[ Cryptology ePrint archive ]