#### Vol. 4, No. 1, 2020

 Recent Volumes 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index MSP Books and Monographs Other MSP Publications
Cryptanalysis of the generalised Legendre pseudorandom function

### Novak Kaluđerović, Thorsten Kleinjung and Dušan Kostić

Vol. 4 (2020), No. 1, 267–282
##### 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
Legendre symbol, Legendre PRF, cryptanalysis, group action, pseudorandom
Primary: 11T71