Building Cryptographic Primitives from Legendre and Jacobi Symbols

In 1988, Damgård proposed a cryptographic pseudorandom generator based on quadratic characters. The seed of the generator consists of a prime p and an element x in Z_p; the generator's output is the string of Legendre symbols of x modulo p, (x+1) modulo p, (x+2) modulo p, and so on. Damgård proposed a second construction that replaces the prime modulus with a composite integer, and replaces Legendre symbols with Jacobi symbols. A modern variant of the construction takes the modulus to be public.

Each of these constructions has resisted cryptanalysis for years, even against quantum attacks (the best attacks still run in exponential time) and their simple algebraic structure makes these constructions appealing for use in multiparty and zero-knowledge protocols. At the same time, we do not know whether security of these constructions follows from any traditional number-theoretic assumption.

In this talk, we give the first results relating the security of Damgård's constructions to pre-existing hardness assumptions:
* First, we prove that a variant of Damgård's generator is secure under the quadratic-residuosity assumption. In this variant, the generator outputs the Legendre symbols of (x+a_1) modulo p, (x+a_2) modulo p, and so on, for public random values (a_1, a_2, ...).
* Second, we show that when using a modulus of the form p^2 q, for primes p and q, Damgård's composite-modulus generator is one-way, provided that factoring integers of the form p^2 q is 
computationally hard.
* Finally, we analyze a recently proposed pseudorandom function based on Damgård's construction; we show that breaking this construction is no harder than factoring and thus that it is not post-quantum secure.

The security of Damgård's original construction remains open. We will conclude with a discussion of this and related open problems.