Welcome to the resource topic for 2019/151
Title:
Solving binary MQ with Grover’s algorithm
Authors: Peter Schwabe, 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.
ePrint: https://eprint.iacr.org/2019/151
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .