Paper 2017/1236

Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

Jean-Charles Faugère, Kelsey Horan, Delaram Kahrobaei, Marc Kaplan, Elham Kashefi, and Ludovic Perret

Abstract

In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency (NSA) concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of $m$ Boolean multivariate quadratic equations in $n$ variables (MQ$_2$); a central problem in post-quantum cryptography. When $n=m$, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving MQ$_2$ that requires the evaluation of, on average, $O(2^{0.462n})$ quantum gates. To our knowledge this is the fastest algorithm for solving MQ$_2$.

Note: This work is independent of ``Asymptotically faster quantum algorithms to solve multivariate quadratic equations'' from Daniel J. Bernstein and Bo-Yin Yang that recently appeared in Cryptology ePrint Archive: Report 2017/1206.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
ludovic perret @ lip6 fr
History
2017-12-22: revised
2017-12-22: received
See all versions
Short URL
https://ia.cr/2017/1236
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1236,
      author = {Jean-Charles Faugère and Kelsey Horan and Delaram Kahrobaei and Marc Kaplan and Elham Kashefi and Ludovic Perret},
      title = {Fast Quantum Algorithm for Solving Multivariate Quadratic Equations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1236},
      year = {2017},
      url = {https://eprint.iacr.org/2017/1236}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.