2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you think would be a simulator for the adversary that $\hspace{2.49 in}$ generates messages just like an honest verifier? $\;$ $\endgroup$ – user991 Mar 21 '15 at 4:47
  • $\begingroup$ I'm slightly confused by the role of $L$ and $C$. Am I correct in assuming that the long-term secret Peggy has is $p,q$ (so those are the same on each authentication attempt), but that she generates a new $r$ and $s$ every time the algorithm is run? Also, did you mean to also have Victor checking that the response is not equal to $L$ in step 6b (in addition to checking that it's not equal to $C$)? $\endgroup$ – cpast Mar 21 '15 at 5:01
  • $\begingroup$ @cpast Yes, that was my intent. $\endgroup$ – Vaelus Mar 21 '15 at 5:05
  • $\begingroup$ @cpast I did not originally consider the case where $m = L$, but I supposed I should have added $m \neq L$ in the conditions for 6b $\endgroup$ – Vaelus Mar 21 '15 at 5:29
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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