Publications

The Legendre signature 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 signature of \( x \) modulo \( p \), with respect to public random offsets \( \vec a \), is a pseudorandom generator. Our result applies to cryptographic settings in which the prime modulus \( p \) is secret; the result does not extend to the case — common in applications — in which the modulus \( p \) is public. At the same time, this paper is the first to relate the pseudorandomness of Legendre symbols to any pre-existing cryptographic assumption.