Paper 2017/1206

Asymptotically faster quantum algorithms to solve multivariate quadratic equations

Daniel J. Bernstein and Bo-Yin Yang

Abstract

This paper designs and analyzes a quantum algorithm to solve a system of $m$ quadratic equations in $n$ variables over a finite field ${\bf F}_q$. In the case $m=n$ and $q=2$, under standard assumptions, the algorithm takes time $2^{(t+o(1))n}$ on a mesh-connected computer of area $2^{(a+o(1))n}$, where $t\approx 0.45743$ and $a\approx 0.01467$. The area-time product has asymptotic exponent $t+a\approx 0.47210$. For comparison, the area-time product of Grover's algorithm has asymptotic exponent $0.50000$. Parallelizing Grover's algorithm to reach asymptotic time exponent $0.45743$ requires asymptotic area exponent $0.08514$, much larger than $0.01467$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
FXLGroverreversibilityBennett--Tompaparallelizationasymptotics
Contact author(s)
authorcontact-groverxl @ box cr yp to
History
2017-12-18: received
Short URL
https://ia.cr/2017/1206
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1206,
      author = {Daniel J.  Bernstein and Bo-Yin Yang},
      title = {Asymptotically faster quantum algorithms to solve multivariate quadratic equations},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1206},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1206}},
      url = {https://eprint.iacr.org/2017/1206}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.