{"id":"arxiv/2604.04833","url":"https://arxiv.org/abs/2604.04833","tags":["cs.CR","math.NT"],"score":0,"title":"Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields","domain":"cs.CR","source":"arxiv","authors":["Daksh Pandey"],"reviews":0,"subject":"cs.CR","summary":"The Legendre Pseudorandom Function (PRF) is a highly efficient cryptographic primitive built upon the Legendre symbol, valued for its low multiplicative complexity in Multi-Party Computation (MPC) and Zero-Knowledge Proof (ZKP) protocols. While its security over prime fields $\\mathbb{F}_p$ is well-documented, recent interest has shifted toward instantiations over extension fields $\\mathbb{F}_{p^r}$. This paper presents the first comprehensive cryptanalysis of the single-degree Legendre PRF operating over $\\mathbb{F}_{p^r}$. First, we analyze polynomial input encoding under a standard passive…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-06","reactions":{}}