Cryptology ePrint Archive: Report 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$.

Category / Keywords: public-key cryptography / FXL, Grover, reversibility, Bennett--Tompa, parallelization, asymptotics

Date: received 15 Dec 2017

Contact author: authorcontact-groverxl at box cr yp to

Available format(s): PDF | BibTeX Citation

Version: 20171218:210332 (All versions of this report)

Short URL: ia.cr/2017/1206


[ Cryptology ePrint archive ]