Abstract
In this paper we re-examine quantum search applied to the Multivariate Quadratic (MQ) hardness problem over the finite field GF(2). This problem is key to the security of a number of proposed post-quantum public-key cryptosystems designed to be resistant against attacks from quantum computers and in this paper we give a warning of the dangers of extrapolating parameters based upon the efficiency of quantum search algorithms. Our methods demonstrate that by applying
preprocessing to the MQ problem, we can reduce the computational load on the quantum computer and, in a generalisation of multi-target search for single-targets, improve the efficiency of the basic quantum search oracle
for the MQ problem over GF(2). Our work builds upon the MQ oracle introduced by Westerbaan and Schwabe and improves it to the extent that it breaks all quantum-resistant security parameters for the Gui cryptosystem proposed by the original authors. Our results hold both in the logical gate model and when the algorithm is
fully costed in terms of the Clifford+T universal gate set.
preprocessing to the MQ problem, we can reduce the computational load on the quantum computer and, in a generalisation of multi-target search for single-targets, improve the efficiency of the basic quantum search oracle
for the MQ problem over GF(2). Our work builds upon the MQ oracle introduced by Westerbaan and Schwabe and improves it to the extent that it breaks all quantum-resistant security parameters for the Gui cryptosystem proposed by the original authors. Our results hold both in the logical gate model and when the algorithm is
fully costed in terms of the Clifford+T universal gate set.
| Original language | English |
|---|---|
| Title of host publication | Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers. |
| Publisher | WAIFI |
| Publication status | Published - 16 Jun 2018 |
Keywords
- quantum search
- cryptography
- multivariate quadratic