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)$
- Peggy picks two random large primes $p$ and $q$
- Peggy gives Victor $L=pq$
- Peggy picks two random large primes $r$ and $s$
- Peggy gives Victor $C=rs$
- Victor randomly either asks Peggy for either $r$ or $pr$
- 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?