Paper 2024/1252

The Pseudorandomness of Legendre Symbols under the Quadratic-Residuosity Assumption

Abstract

The Legendre signature of an integer $x$ modulo a prime~$p$ with respect to offsets $\vec a = (a_1, \dots, a_\ell)$ is the string of Legendre symbols $(\frac{x+a_1}{p}), \dots, (\frac{x+a_\ell}{p})$. Under the quadratic-residuosity assumption, we show that the function that maps the pair $(x,p)$ to the Legendre signature of $x$ modulo $p$, with respect to public random offsets $\vec a$, is a pseudorandom generator. Our result applies to cryptographic settings in which the prime modulus $p$ is secret; the result does not extend to the case—common in applications—in which the modulus $p$ is public. At the same time, this paper is the first to relate the pseudorandomness of Legendre symbols to any pre-existing cryptographic assumption.