Solving binary MQ with Grover's algorithm

Peter Schwabe; Bas Westerbaan

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

Metadata

Available format(s): PDF
Publication info: Published elsewhere. MINOR revision.Security, Privacy, and Applied Cryptography Engineering (SPACE 2016)
DOI: 10.1007/978-3-319-49445-6_17
Keywords: Grover's algorithm multivariate quadratics quantum resource estimates
Contact author(s): peter @ cryptojedi org
bas @ westerbaan name
History: 2019-02-20: received
Short URL: https://ia.cr/2019/151
License: 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}
}