HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

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 {\it $m$ Boolean multivariate quadratic equations in $n$ variables} (\MQb); a central problem in post-quantum cryptography. When $n=m$, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving \MQb{} that requires the evaluation of, on average, $O(2^{0.462n})$ quantum gates. To our knowledge this is the fastest algorithm for solving \MQb{}.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Contributor : Ludovic Perret Connect in order to contact the contributor
Submitted on : Saturday, January 26, 2019 - 4:04:14 PM
Last modification on : Thursday, February 3, 2022 - 11:18:52 AM

Links full text


  • HAL Id : hal-01995374, version 1
  • ARXIV : 1712.07211


Jean-Charles Faugère, Kelsey Horan, Delaram Kahrobaei, Marc Kaplan, Elham Kashefi, et al.. Fast Quantum Algorithm for Solving Multivariate Quadratic Equations. 2019. ⟨hal-01995374⟩



Record views