Cryptology ePrint Archive: Report 2019/151

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