Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

1 PolSys - Polynomial Systems
Inria de Paris, LIP6
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{}.
Keywords :
Document type :
Preprints, Working Papers, ...

https://hal.inria.fr/hal-01995374
Contributor : Ludovic Perret <>
Submitted on : Saturday, January 26, 2019 - 4:04:14 PM
Last modification on : Tuesday, March 23, 2021 - 9:28:03 AM

Identifiers

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

Citation

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