Welcome to the resource topic for 2017/1236
Title:
Fast Quantum Algorithm for Solving Multivariate Quadratic Equations
Authors: Jean-Charles Faugère, Kelsey Horan, Delaram Kahrobaei, Marc Kaplan, Elham Kashefi, 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$.
ePrint: https://eprint.iacr.org/2017/1236
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .