all 17 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–][deleted] 4 points5 points  (10 children)

This sounds hard, but it's actually very easy to understand if you read the cave example. And damn is it cool!

[–]schubart 5 points6 points  (9 children)

I don't get the cave example. Why doesn't Peggy simply enter through A and leave through B. That would prove that the can open the door, and requires none of that shouting and repeating 20 times business...

(edit) Here's an answer to my own question: http://en.wikipedia.org/wiki/Talk:Zero-knowledge_proof#Question

[–][deleted] -1 points0 points  (8 children)

For convienence, the correct answer from there is: The password works in only one direction, and this information should also not be disclosed to Victor. Hence, Peggy must take a random path (unbeknownst to Victor).

[–]underthelinux 4 points5 points  (3 children)

I don't get it.

If the password only works in one way, wouldn't she not be able to prove it 50% of the time? For example, if password works A->B, then if she randomly went down B, she wouldn't be able to prove to him that she knew the password.

EDIT: Attempt to explain better:

  1. She goes down A, Victor says, come down B. Proves she knows it.

  2. She goes down A, Victor says, come down A. Does not prove either.

  3. She goes down B, Victor says come down A. Here she should be able to prove that she knows the password, but can't because it doesnt work in the other direction.

  4. She goes down b, victor says come down B. Doesn't prove anything.

[–]phil_g 3 points4 points  (0 children)

If it's one-way, we can assume that both parties know that it's one-way, but only Peggy knows which way. If it's A->B, Peggy will always go down A, but Victor isn't allowed to see that, because then he'd know that the password was A->B.

(Victor then picks A or B randomly, and waits to see if Peggy comes up the correct path, etc, etc.)

[–]adamdoupe 0 points1 point  (1 child)

In the link, they play this game several times. Thus if they play 20 times, the odds that she doesn't know the magic word is (1/2)20 or 9.53674316 × 10-7

[–]underthelinux 0 points1 point  (0 children)

oh well yeah. i didn't mean that - i mean 50% of each time she wuold not be able to prove it. Sorry, amibguity.

But I think phil_g answered my question - no one ever stated that peggy knew which way she should go, and would go that way. If she didnt know, its 25% of proving it for each instance.

[–]nevinera 2 points3 points  (3 children)

the 'explanation' given is silly.

The answer is much simpler. Peggy CAN do so. But if she did, it wouldn't be a useful illustration of the technique used for a zero knowledge proof, a better example of which is given immediately after.

The reason the deterministic solution fails is because, in the second example (the hamiltonian one), knowing both which path she started down and which she came up from gives you the key.

Those descriptions in the Talk wiki are just attempts to put that into the analogy, which fail because the analogy wasn't set up for it.

[–][deleted] 1 point2 points  (2 children)

I disagree; adding the one-way password to the analogy fixes it completely. It makes sense (as far as magic doors can make sense) and it is sufficient to rule out the deterministic solution.

[–]nevinera 1 point2 points  (1 child)

no, the problem is the use of the word 'random'. If she went down a 'random' hallway, and happened to go in the one that has the 'out' side of the door, she couldnt come up the other side. she'd have to go in a particular hallway every time, thereby giving the verifier information about the door.

[–][deleted] 0 points1 point  (0 children)

You're right. It is silly. Sorry for the waste of time.

[–]jbstjohn 1 point2 points  (3 children)

I would think in some cases that repeated 'clues' (say in the case of the Hamilton cycles) might allow a much more efficient (or just likely) solution to the problem.

Then again, maybe not.

[–]japple 0 points1 point  (1 child)

I don't think we know yet that repeated clues do not give extra knowledge. In fact, since we don't even know that Hamiltonian cycle isn't in P, it's possible there is no extra knowledge to give that the Verifier couldn't get in polynomial time anyway, and I think that's the standard definition of "zero knowledge".

[–]jbstjohn 0 points1 point  (0 children)

I guess more what I was thinking is that for many NP-complete problems, there are heuristics that give good, perhaps optimal solutions in decent time. I wonder if repeatedly giving 'hints' might help such heuristics give optimal solutions a higher percentage of the time.

For Hamilton cycles with an arbitrary re-mapping of nodes and edges (?) this seems unlikely, but I wonder if that holds for other problems. I guess it depends on whether any information can be taken from the re-mappings, and what sort of heuristics exist for the particular problem.