Is this an example of a zero knowlege proof?

Question

My Math Structures professor mentioned the strange concept of a zero knowledge proof to me after class one day, and I decided to do some reading about it. After reading the relatively famous "How to Explain Zero Knowlege Protocols to Your Children", and the Wikipedia page on zero knowledge proofs, I wanted to see if I could construct a protocol for a proof myself. After a bit of thinking, I believe the one that follows completes a zero knowledge proof.

---

Let Peggy be the prover and Victor be the verifier Peggy is trying to prove that she knows $(p,q)$

1. Peggy picks two random large primes $p$ and $q$
2. Peggy gives Victor $L=pq$
3. Peggy picks two random large primes $r$ and $s$
4. Peggy gives Victor $C=rs$
5. Victor randomly either asks Peggy for either $r$ or $pr$
6. Victor verifies Peggy's response $m$:
   • If Victor asked for $r$, he checks that $m\mid C$ and that $C/m$ is prime
   • If Victor asked for $pr$, he checks that $m\ne C$ and $m\neq L$ and that $m\mid LC$

---

steps 3 through 6 can be repeated to reduce the chance Peggy could have guessed what Victor was going to ask for.

I think this protocol works because factoring large pseudoprimes is infeasible, and Peggy can fake responses if she knows what Victor is going to ask for.

If Peggy knows Victor will ask for $r$, she just does the protocol as normal (sending $r$ when asked). If she knows Victor will ask for $pr$, she sends $C^\prime=rsn$ initially (for some $n$ and prime $r,s$), and then sends $rn$ when Victor asks for $pr$.

Now I would like if someone more experienced than me could let me know: does my protocol successfully perform a zero knowledge proof? If not, do I appear to have some simply correctable misunderstanding, or did I maybe miss a couple details?

Answer 1

This has some issues, with both soundness and zero-knowledge.

The issue with zero-knowledge is that an eavesdropper who knows $L$ and overhears legitimate traffic can compromise the secret quite easily. While factoring is hard, taking a GCD is very efficient. That means that given $M=pr$ and $L=pq$, an eavesdropper Eve can efficiently compute $\gcd(M,L)=p$. That is a fatal flaw in this scheme as a ZKP -- an eavesdropper can compromise the secret. Where it gets interesting is that your idea of a simulator is correct -- Sam can simulate a valid transaction, which should be enough to guarantee zero-knowledge (Eve could simulate the valid Peggy-Victor transaction without knowing $p$, which would let her efficiently compute $p$ from scratch).

After thinking about this, I think the reason why you can simulate it but it leaks info is that it's unsound (i.e. a prover without the secret can successfully authenticate with 100% probability). When checking $pr$, you verify that $M\ne L$, and $M\ne C$, and $M\mid LC$. It's certainly true that $pr$ meets those conditions. But so does $r$! That's why the fact that a simulator could produce a legitimate-looking transcript doesn't imply zero-knowledge: the transcript only looks legitimate in the protocol because you don't do all the checks you should on it, and further checks on the actual simulated transcript could reveal that it's faked.

The reason simulators are often used to show zero-knowledge is that it means that someone can produce a transcript indistinguishable from a real one without knowing the secret. It's not enough that this transcript passes the tests in the protocol; it must be something that could actually have been produced by a legitimate prover/verifier combo (or computationally indistinguishable from it). If your scheme is unsound, this is certainly not necessarily the case -- an unsound scheme can let a class of transcripts through that are easily distinguishable from legitimate transcripts, which means the simulator might be generating transcripts from the former class.

So, the fatal issue is ultimately that you have $L=pq$ and $M=pr$ both known to an attacker, who can recover $p$. The only reason simulation worked is that you didn't check everything you could have checked; this lets a simulator work, but means that the simulator's transcripts couldn't have been real transcripts (and it's easy to tell that they couldn't have been real), so the simulator doesn't give you zero-knowledge.