Abstract

Linear Legendre pseudorandom functions were introduced in 1988 by Damgård, and higher degree generalisations were introduced by Russell and Shparlinski in 2004. We present new key recovery methods that improve the state of the art for both cases. For degree $r\ge 3$ we give an attack that runs in time $O\left(p^{r-3}\right)$ after $O\left(p^3\right)$ precomputation for the most relevant high degree case; it is based on the action of the group of Möbius transformations on degree $r$ polynomials. For $r<3$ we give an $O\left(p^{r∕2}\right)$ attack with $O\left(p^{r∕4}\right)$ oracle queries. In the linear case we recovered the keys for the $64$, $74$ and $84$-bit prime Ethereum challenges, being the first to solve the $84$-bit case.

Keywords

Mathematical Subject Classification 2010

Milestones

Authors