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?


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.

  • $\begingroup$ Thank you very much for your answer :) $\endgroup$ – Pure Air Feb 7 '20 at 7:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Geoffroy Couteau Oct 7 '20 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.