CryptoDB
The Pseudorandomness of Legendre Symbols under the Quadratic-Residuosity Assumption
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| 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. |
BibTeX
@inproceedings{tcc-2025-36076,
title={The Pseudorandomness of Legendre Symbols under the Quadratic-Residuosity Assumption},
publisher={Springer-Verlag},
author={Henry Corrigan-Gibbs and David J. Wu},
year=2025
}