Therefore, in this work, we show that key-recovery attacks against the Legendre PRF are equivalent to solving a specific family of multivariate quadratic (MQ) equation system over a finite prime field. This new perspective sheds some light on the complexity of key-recovery attacks against the Legendre PRF. This allows us to take the first steps in settling the provable security of the Legendre PRF and other variants. We do this by conducting extensive algebraic cryptanalysis on the resulting MQ instance. We show how the currently best-known techniques and attacks fall short in solving these sparse quadratic equation systems. Another benefit of viewing the Legendre PRF as an MQ instance is that it facilitates new applications of the Legendre PRF, such as verifiable random function or oblivious (programmable) pseudorandom function. These new applications can be used in cryptographic protocols, such as state of the art proof-of-stake consensus algorithms or private set intersection protocols.
Sequences of consecutive Legendre and Jacobi symbols as pseudorandom bit generators have been proposed for cryptographic use in 1988. Since then they were mostly forgotten in the applications. However, recently revived interest is shown to pseudorandom functions (PRF) based on the Legendre and power residue symbols, due to their extreme efficiency in the multi-party setting and their conjectured post-quantum security. The lack of provable security results hinders the deployment of PRFs based on quadratic and power residue symbols. On the other hand, the security of the Legendre PRF and other variants do not seem to be related to standard cryptographic assumptions, e.g. discrete logarithm or factoring.