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
we give an attack
that runs in time
after
precomputation for the most relevant high degree case; it is based
on the action of the group of Möbius transformations on degree
polynomials.
For
we
give an
attack with
oracle queries. In the linear case we recovered the keys for the
,
and
-bit
prime Ethereum challenges, being the first to solve the
-bit
case.
Keywords
Legendre symbol, Legendre PRF, cryptanalysis, group action,
pseudorandom