Cryptanalysis of the generalised Legendre pseudorandom function

Abstract

Linear Legendre pseudorandom functions were introduced in 1988 by Damgrd, 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 3 we give an attack that runs in time O( p r -3 ) after O( p 3 ) precomputation for the most relevant high degree case; it is based on the action of the group of Mbius transformations on degree r polynomials. For r < 3 we give an O( p r/2 ) attack with O( p r/4 ) 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.