Paper 2024/1252

Legendre Sequences are Pseudorandom under the Quadratic-Residuosity Assumption

Henry Corrigan-Gibbs, Massachusetts Institute of Technology
David J. Wu, The University of Texas at Austin
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.