I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper.
The proof is a 2 round where the verifier asks the prover to extract square roots of quadratic residues.
I've read the HVZK proof (shown in the picture below) and I agree that you can produce a transcript that distributes like a normal proof, however I still can't get over the simple fact that:
- Without the witness (factorization) you can't extract a square root modulo $N$.
- When the proof is turned into a NIZK via the Fiat-Shamir transformation, the prover records square roots in their raw form inside the proof, so the verifier learns square roots of numbers in the group which it could not compute on its own before.
Isn't that a "knowledge" leak? Why can this proof be turned into a NIZK?
Many thanks in advance.