EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The Legendre pseudorandom function as a multivariate quadratic cryptosystem: security and applications

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

Applicable Algebra in Engineering, Communication and Computing · 2025-03 · 36 (2) · 223-253

DOI: 10.1007/s00200-023-00599-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Applicable Algebra in Engineering, Communication and Computing, online erschienen am 01.03.2023. Verfasst von István András Seres und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 80 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Eötvös Loránd University.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Eötvös Loránd University

Zitieren

APA

Seres, I. A., Horváth, M., & Burcsi, P. (2025). The Legendre pseudorandom function as a multivariate quadratic cryptosystem: security and applications. Applicable Algebra in Engineering, Communication and Computing, 36(2), 223-253. https://doi.org/10.1007/s00200-023-00599-2

Vancouver

Seres IA, Horváth M, Burcsi P. The Legendre pseudorandom function as a multivariate quadratic cryptosystem: security and applications. Applicable Algebra in Engineering, Communication and Computing. 2025;36(2):223-253. doi:10.1007/s00200-023-00599-2

BibTeX
@article{Seres2025,
  author = {Seres, István András and Horváth, Máté and Burcsi, Péter},
  title = {The Legendre pseudorandom function as a multivariate quadratic cryptosystem: security and applications},
  journal = {Applicable Algebra in Engineering, Communication and Computing},
  year = {2025},
  volume = {36},
  number = {2},
  pages = {223--253},
  doi = {10.1007/s00200-023-00599-2}
}
Kostenlos starten →