Paper 2021/182

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

István András Seres, Eötvös Loránd University
Máté Horváth, University of Wuppertal
Péter Burcsi, Eötvös Loránd University

Sequences of consecutive Legendre and Jacobi symbols as pseudorandom bit generators were proposed for cryptographic use in 1988. Major interest has been shown towards pseudorandom functions (PRF) recently, based on the Legendre and power residue symbols, due to their efficiency in the multi-party setting. The security of these PRFs is not known to be reducible to standard cryptographic assumptions. 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. We conduct algebraic cryptanalysis on the resulting MQ instance. We show that the currently known techniques and attacks fall short in solving these sparse quadratic equation systems. Furthermore, we build novel cryptographic applications of the Legendre PRF, e.g., verifiable random function and (verifiable) oblivious (programmable) PRFs.

Note: Added proofs to the application part of the paper. Additionally, minor fixes elsewhere in the text.

Available format(s)
Secret-key cryptography
Publication info
Legendre PRF pseudo-randomness multivariate cryptography MPC-friendly primitives
Contact author(s)
seresistvanandras @ gmail com
mhorvath @ crysys hu
bupe @ inf elte hu
2022-11-06: last of 3 revisions
2021-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {István András Seres and Máté Horváth and Péter Burcsi},
      title = {The Legendre Pseudorandom Function as a Multivariate Quadratic Cryptosystem: Security and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/182},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.