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 \F2. The current state of the art in solving the \MQ problem over \F2 for sizes commonly used in cryptosystems is enumeration, which runs in time Θ(2n) for a system of n variables. Grover's algorithm running on a large quantum computer is expected to reduce the time to Θ(2n/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 algorithmmultivariate quadraticsquantum resource estimates
Contact author(s)
peter @ cryptojedi org
bas @ westerbaan name
History
2019-02-20: received
Short URL
https://ia.cr/2019/151
License
Creative Commons Attribution
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},
      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.