### 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.

Available format(s)
Publication info
Published elsewhere. MINOR revision.Security, Privacy, and Applied Cryptography Engineering (SPACE 2016)
DOI
10.1007/978-3-319-49445-6_17
Keywords
Contact author(s)
peter @ cryptojedi org
bas @ westerbaan name
History
Short URL
https://ia.cr/2019/151

CC BY

BibTeX

@misc{cryptoeprint:2019/151,
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{https://eprint.iacr.org/2019/151}},
url = {https://eprint.iacr.org/2019/151}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.