Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

Jean-Charles Faug`ere; Kelsey Horan; Delaram Kahrobaei; Marc Kaplan; Elham Kashefi; Ludovic Perret

Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

Jean-Charles Faug`ere, Kelsey Horan, Delaram Kahrobaei, Marc Kaplan, Elham Kashefi, Ludovic Perret

Computer Science

Research output: Contribution to journal › Article › peer-review

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{}.

Original language	English
Journal	QUANTUM INFORMATION COMPUTATION
Publication status	Published - 19 Dec 2017

Keywords

cs.CR
quant-ph

Cite this

@article{535ce52a8e5243c9ba7eadc99dd7ecf3,

title = "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{}. ",

keywords = "cs.CR, quant-ph",

author = "Jean-Charles Faug`ere and Kelsey Horan and Delaram Kahrobaei and Marc Kaplan and Elham Kashefi and Ludovic Perret",

year = "2017",

month = dec,

day = "19",

language = "English",

journal = "QUANTUM INFORMATION COMPUTATION",

issn = "1533-7146",

publisher = "Rinton Press Inc.",

}

TY - JOUR

T1 - Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

AU - Faug`ere, Jean-Charles

AU - Horan, Kelsey

AU - Kahrobaei, Delaram

AU - Kaplan, Marc

AU - Kashefi, Elham

AU - Perret, Ludovic

PY - 2017/12/19

Y1 - 2017/12/19

N2 - 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{}.

AB - 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{}.

KW - cs.CR

KW - quant-ph

M3 - Article

SN - 1533-7146

JO - QUANTUM INFORMATION COMPUTATION

JF - QUANTUM INFORMATION COMPUTATION

ER -