Welcome to the resource topic for 2020/098
Title:
Improved key recovery on the Legendre PRF
Authors: Novak Kaluđerović, Thorsten Kleinjung, 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.
ePrint: https://eprint.iacr.org/2020/098
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .