Paper 2024/1252
Legendre Sequences are Pseudorandom under the Quadratic-Residuosity Assumption
Abstract
The Legendre sequence 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 sequence of $x$ modulo $p$, with respect to public random offsets $\vec a$, is a pseudorandom generator. This answers an open question of Damgård (CRYPTO 1988), up to the choice of the offsets $\vec a$.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Legendre sequencequadratic residuosity
- Contact author(s)
-
henrycg @ csail mit edu
dwu4 @ cs utexas edu - History
- 2024-08-09: approved
- 2024-08-08: received
- See all versions
- Short URL
- https://ia.cr/2024/1252
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1252,
author = {Henry Corrigan-Gibbs and David J. Wu},
title = {Legendre Sequences are Pseudorandom under the Quadratic-Residuosity Assumption},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1252},
year = {2024},
url = {https://eprint.iacr.org/2024/1252}
}
