# Schnorr proof of group with unknown order (but the prover know the order)

We assume that we have $$n = pq$$, where $$p = 2p'+1$$, $$q = 2q'+1$$, and all $$p, q, p', q'$$ are large primes. Pick $$g' \gets_R Z_n^*$$, and compute $$g = (g')^2 \bmod n$$. Then we have a generator $$g$$ for $$QR_n$$. The order of $$g$$ is $$p'q'$$.

Both prover and verifier are given $$n$$, $$g$$, and $$h = g^x \bmod n$$. The prover is given $$p', q'$$, and the witness $$x$$. Now the prover knows the order of $$g$$. Both parties start the Schnorr proof.

1. The prover picks $$y \gets_R Z_{p'q'}$$, computes $$a = g^y \bmod n$$, and sends $$a$$ to the verifier.

2. The verifier sends a random $$e \gets_R \{1, \ldots, n/4\}$$.

3. The prover sends $$z = ex + y \bmod p'q'$$ to the verifier.

4. The verifier accepts if $$g^z \equiv h^ea \bmod n$$.

It seems that this procedure works ok. But when I want to prove the special soundness and special HVZK, I was stuck.

For SHVZK, it seems that the simulator does not know $$p'q'$$, and thus it cannot perfectly simulate the interaction. A similar problem happens when I want to prove the special soundness. Given $$z_1 = e_1 x + y$$ and $$z_2 = e_2 x + y$$, I cannot compute the inverse of $$e_1 -e_2$$ to recover $$x$$ since I do not know $$p'q'$$.

I am wondering whether there is something wrong?

• Well, I'm very late on the weighing in part, but Yehuda's answer is perfectly right: proving that we can extract requires more work. At a very high level, this is done by showing that you can actually divide by $(e_1-e_2)$ over the integers (hence the factorization is not needed) unless the prover breaks some assumption (strong RSA in early works, RSA in the latest results). See the detailed discussions and analysis on this issue in this paper, which is also included in my thesis. – Geoffroy Couteau Oct 7 '20 at 19:42