**Improved key recovery on the Legendre PRF**

*Novak Kaluđerović and Thorsten Kleinjung and Dusan Kostic*

**Abstract: **We give an algorithm for key recovery of the Legendre pseudorandom function that supersedes the best known algorithms so far.
The expected number of operations is $O(\sqrt{p\log{\log{p}}})$ on a $\Theta(\log{p})$-bit word machine, under reasonable heuristic assumptions, and requires only $\sqrt[4]{p~{\log^2{p}}\log{\log{p}}}$ oracle queries.
If the number of queries $M$ is smaller, the expected number of operations is $\frac{{p}\log{p}\log\log{p}}{M^2}$. We further show that the algorithm works in many different generalisations -- using a different character instead of the Legendre symbol, using the Jacobi symbol, or using a degree $r$ polynomial in the Legendre symbol numerator.
In the latter case we show how to use Möbius transforms to lower the complexity to $O(p^{\operatorname{max}\{r-3,r/2\}}r^2\log{p})$ Legendre symbol computations, and $O(p^{\operatorname{max}\{r-4,r/2\}}r^2\log{p})$ in the case of a reducible polynomial.
We also give an $O(\sqrt[3]{p})$ quantum algorithm that does not require a quantum oracle, and comments on the action of the Möbius group in the linear PRF case.
On the practical side we give implementational details of our algorithm.
We give the solutions of the $64, 74$ and $84$-bit prime challenges for key recovery with $M=2^{20}$ queries posed by Ethereum, out of which only the $64$ and $74$-bit were solved earlier.

**Category / Keywords: **secret-key cryptography / Legendre pseudorandom function, number theory, cryptanalysis, secret-key cryptography, multiparty computation primitives

**Date: **received 31 Jan 2020, last revised 25 Feb 2020

**Contact author: **novak kaluderovic at epfl ch

**Available format(s): **PDF | BibTeX Citation

**Version: **20200225:124545 (All versions of this report)

**Short URL: **ia.cr/2020/098

[ Cryptology ePrint archive ]