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 a=(a1,,a) is the string of Legendre symbols (x+a1p),,(x+ap). 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 a, is a pseudorandom generator. This answers an open question of Damgård (CRYPTO 1988), up to the choice of the offsets 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.