1
$\begingroup$

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.

enter image description here

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

I'm guessing:

"HVZK" stands for "honest-verifier zero knowledge", 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 "dangerous" 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your comment, I understand the difference between HVZK and regular ZK and Fiat Shamir heuristic, it's just that this protocol "feels" odd in that sense: Before observing the ZKP, I cannot root square mod N any number. However after observing the ZKP now I know several numbers of the form $(x, \sqrt{x}~mod~N)$ however I could never have computed these roots before observing the ZKP, so how is zero knowledge preserved here if I can compute new things I wasn't able to before? $\endgroup$
    – yacovm
    Jun 19, 2020 at 18:34
  • 1
    $\begingroup$ Ah, sorry. Maybe the answer is that you could compute such roots before having seen the ZKP, but you have to compute them "backwards": you pick a random number to act as the root, then square it? $\endgroup$
    – Sam Jaques
    Jun 20, 2020 at 9:49
1
$\begingroup$

so the verifier learns square roots of numbers in the group which it could not compute on its own before.

With Fiat-Shamir transform, these roots will be of random numbers. And the learner could easily compute those by sampling random $x$ and computing $x^2$ (modulo $N$). This distribution is not distinguishable from $(\sqrt{x},x)$ pairs that would be given in the protocol.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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