Paper 2021/182

The Legendre Pseudorandom Function as a Multivariate Quadratic Cryptosystem: Security and Applications

István András Seres and Máté Horváth and Péter Burcsi

Abstract

Sequences of consecutive Legendre and Jacobi symbols as pseudorandom bit generators were proposed for cryptographic use in 1988. Since then, they were mostly forgotten in the applications. However, recently revived interest has been shown towards pseudorandom functions (PRF) based on the Legendre and power residue symbols, due to their 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 power residue symbols. On the other hand, the security of these PRFs do not seem to be related to standard cryptographic assumptions, e.g. discrete logarithm or factoring. 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.