2
$\begingroup$

Take an output length $\ell$ and a random seed $s \in \Bbb Z_p$ and a large 1000-bit or so prime number $p$ and output the Legendre symbols of $s, s+1, \dotsc, s + \ell - 1$ with respect to $p$.

There might be a vulnerability when $s$ is very close to $0$, so you need to give it a value sufficiently far away from $0$.

Is this a cryptographically secure pseudorandom generator? I can't seem to reduce it to any number theoretic problem.

$\endgroup$
2
$\begingroup$

"On the Randomness of Legendre and Jacobi Sequences", Ivan Damgård, CRYPTO 88.

"Quantum algorithms for some hidden shift problems", Wim van Dam et al., SODA '03.

"On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol", Mauduit and Sárközy, Acta Arithmetica 1997.

From the van Dam article: "We conjecture that classically the shifted Legendre symbol is a pseudo-random function [...]" They indicate Damgård says: "Given a part of the Legendre sequence (s|p), (s+1|p), ..., (s+l|p), where l is O(log p), predict the next value (s+l+1|p)" is a hard problem with applications in cryptography.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.