Short proofs of knowledge for factoring (Q4950041)

The paper considers the problem of how to prove to a verifier that one knows the factorization of a public modulus without giving any information about the decomposition. An interactive proof of knowledge for the factorization of any public integer \(n\) whose prime factors cannot be found by simple trial division. The protocol is statistical zero knowledge and is a proof of knowledge of a small discrete logarithm of \(z^n \pmod{n}\) for a few randomly chosen elements \(z \pmod{n}\). The communication complexity of the scheme is \(O(k + |n|)\) bits. Results on the probability of generating \(Z^*_{p^e}\) for randomly chosen elements are given and used to prove the security of the protocol given. One round of the protocol consists of the prover randomly choosing an integer \(r \in [0,A[\) and computing for \(i=1,2, \cdots ,K\) the commitments \(x_i = z_i^r \pmod{n}\). The \(x_i\)'s are sent to the verifier who answers with a challenge \(e\) randomly chosen in \([0,B[\). The prover computes \(y=r+(n - \phi (n)) \times e\) and sends it to the verifier who checks \(0 \leq y <A\) and \(z_i^{y-n \times e} = x_i \pmod{n}\). The protocol is repeated \(\ell\) times. The efficiency of the protocol is examined and observations given as how to make it more efficient. A variant is suggested that allows it to work for when \(n\) has small prime factors. For the entire collection see [Zbl 0931.00050].