Paper 2020/098

Improved key recovery on the Legendre PRF

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


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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.ANTS XIV - Proceedings of the Fourteenth Algorithmic Number Theory Symposium
Legendre pseudorandom functionnumber theorycryptanalysissecret-key cryptographymultiparty computation primitives
Contact author(s)
novak kaluderovic @ epfl ch
2021-06-23: last of 4 revisions
2020-02-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Novak Kaluđerović and Thorsten Kleinjung and Dusan Kostic},
      title = {Improved key recovery on the Legendre PRF},
      howpublished = {Cryptology ePrint Archive, Paper 2020/098},
      year = {2020},
      doi = {10.2140/obs.2020.4.267},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.