Publications

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 \).

BibTeX

@misc{CW24,
  author    = {Henry Corrigan-Gibbs and David J. Wu},
  title     = {Legendre Sequences are Pseudorandom under the Quadratic-Residuosity Assumption},
  misc      = {Full version available at \url{https://eprint.iacr.org/2024/1252}},
  year      = {2024}
}

Publications

Legendre Sequences are Pseudorandom under the Quadratic-Residuosity Assumption

Resources