Henry
Corrigan-
Gibbs

The One-Wayness of Jacobi Signatures

Henry Corrigan-Gibbs and David J. Wu

CRYPTO
August 18-22, 2024, Santa Barbara, California

Materials

• IACR ePrint: 2023/1638

Abstract

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.