Paper 2020/098
Improved key recovery on the Legendre PRF
Novak Kaluđerović, 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}\{r3,r/2\}}r^2\log{p})$ Legendre symbol computations, and $O(p^{\operatorname{max}\{r4,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.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Major revision. ANTS XIV  Proceedings of the Fourteenth Algorithmic Number Theory Symposium
 DOI
 10.2140/obs.2020.4.267
 Keywords
 Legendre pseudorandom functionnumber theorycryptanalysissecretkey cryptographymultiparty computation primitives
 Contact author(s)
 novak kaluderovic @ epfl ch
 History
 20210623: last of 4 revisions
 20200204: received
 See all versions
 Short URL
 https://ia.cr/2020/098
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/098, 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{https://eprint.iacr.org/2020/098}}, url = {https://eprint.iacr.org/2020/098} }