Publications

We show that under a mild number-theoretic conjecture, recovering an integer from its Jacobi signature modulo \( N = p^2 q \), for primes \( p \) and \( q \), is as hard as factoring \( N \). This relates, for the first time, the one-wayness of a pseudorandom generator that Damgård proposed in 1988, to a standard number-theoretic problem. In addition, we show breaking the Jacobi pseudorandom function is no harder than factoring.