Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems

Benjamin Pring

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationArithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers.
PublisherWAIFI
Publication statusPublished - 16 Jun 2018

Keywords

  • quantum search
  • cryptography
  • multivariate quadratic

Fingerprint Dive into the research topics of 'Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems'. Together they form a unique fingerprint.

  • Cite this

    Pring, B. (2018). Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems. In Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers. WAIFI. http://waifi.org/documents/AcceptedPapers2018/S5-WAIFI_2018_paper_23.pdf