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

Question

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?

Answer 1

You are not wrong. This indeed does not work. The way out typically in these situations is to use a proof over the integers. There is quite a bit of work around zero knowledge over groups of unknown order. See Section 3.7 of this thesis by Geoffroy Couteau. Since he is active here, let's hope he weighs in.