Henry
Corrigan-
Gibbs

The Pseudorandomness of Legendre Symbols under the Quadratic-Residuosity Assumption

Henry Corrigan-Gibbs and David J. Wu

To appear in: Theory of Cryptography Conference (TCC)
December 1-5, 2025, Aarhus, Denmark

Materials

• Full version: PDF

Abstract

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.