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 and 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 that 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, 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.
Category / Keywords: secret-key cryptography / Legendre PRF, pseudo-randomness, multivariate cryptography, MPC-friendly primitives Date: received 19 Feb 2021, last revised 8 Mar 2021 Contact author: seresistvanandras at gmail com,mhorvath@crysys hu,bupe@inf elte hu Available format(s): PDF | BibTeX Citation Version: 20210308:133254 (All versions of this report) Short URL: ia.cr/2021/182