Welcome to the resource topic for 2024/1252
Title:
Legendre Sequences are Pseudorandom under the Quadratic-Residuosity Assumption
Authors: Henry Corrigan-Gibbs, David J. Wu
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.
ePrint: https://eprint.iacr.org/2024/1252
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .