ZKP for product of two primes
I'm guessing:
&quot;HVZK&quot; stands for &quot;honest-verifier zero knowledge&quot;, right? Your objection is that a dishonest verifier can choose a random $x_i$, compute $\rho_i\equiv x_i^2\mod N$, and then when they get $\sigma_i$ from the prover, there is a $1/4$ chance that $gcd(\sigma_i-x_i,N)$ is a non-trivial factor. But an honest verifier should generate random $\rho_i$.
This should be secure, based on the following: Suppose $A$ is an algorithm that can factor $N$ given random $\rho_i$ and $\sigma_i$ such that $\sigma_i^2\equiv \rho_i\mod N$. Then we can factor any $N$ with $A$ by picking a random $\sigma_i$, computing $\rho_i\equiv\sigma_i^2\mod N$, and sending $\rho_i$ and $\sigma_i$ to $A$.
It seems intuitively true that the Fiat-Shamir tansform should be able to turn HVZKs into NIZKs (probably with some extra conditions). An HVZK could fail because a dishonest verifier can send a &quot;dangerous&quot; challenge which reveals information, but a Fiat-Shamir forces the challenges to be random. As long as such dangerous challenges are sufficiently rare, then the Fiat-Shamir transform should produce a NIZK.