New number-theoretic cryptographic primitives (Q2023304)

It is known that factoring unbalanced integers, e.g. integers of the form \(n = {p^r}q\), \(p\), \(q\)-primes is easy if \(r\) is large, but for small values of \(r\) the task seems to be as hard as in the general case. Thus, a new family of one-way functions and signature schemes based on this fact is introduced, e.g. for signing a document signer generates multiple moduli \({n_i} = p_i^2{q_i}\) using secret primes \({p_i}\), \({q_i}\). The signature is a bounded-size prime whose Jacobi symbols with respect to the \({n_i}\)s match the message digest.