A classic example of a proof protocol with zero disclosure is the proof protocol of the knowledge of a password to a door inside a circular cave. Let Alice know this password and want to prove his knowledge to Bob without disclosing the password itself. The following protocol is used: Alice enters the cave and approaches the door from an arbitrary side so that Bob does not know which side Alice is from. Bob enters the cave and asks Alice to come out from either side of the cave (left or right). Alice, knowing the password to the door, can always fulfill Bob’s wish, appearing from either side. After each iteration, Bob’s confidence that Alice knows the secret doubles. Thus, after $ k $ successfully executed operations, the probability that Alice is actually cheating on Bob is $ 1/2 ^ k $.

Question: why is it important that Bob does not know which side Alice is coming from? After all, this knowledge is not related to the secret, and knowing, for example, that Alice enters from the right, Bob can ask her to go to the left and make sure that she has the key.

    1 answer 1

    In the original a bit wrong.

    1. At the beginning of the quest, both are at point A. Next, Alice goes inside the cave and turns either left or right, so Bob does not know where she turned (the projection between A and B hides her movement).
    2. Bob then goes to point B and shouts to Alice. Leave from the left or from the right.
    3. Alice, by necessity, opens the door with a password and exits either to the left or to the right.

    The bottom line is that Bob doesn't know which side Alice is from and shouts at random, come out to the left or the right.

    That is, the likelihood that Alice used the password to open the door is just 50%. After N iterations, Bob's confidence grows as (1 - 1/2^N)

    Cave

    • one
      Then he can "manage the process." That is, either to make her always go through the door, or not to go through. The very concept of “choice” disappears and there is no need to fence this system. - KoVadim
    • one
      The point is that Bob can cheat - that is, he knowing that Alice comes in from the left will tell her on the left and go out. And in the case when Bob does not know which side Alice came from, the dishonesty of the verifier does not affect the final result. - Barmaley
    • one
      Zero disclosure has 3 properties: 1. If Alice knows the password, she will convince Bob that she knows the password 2. If Alice does not know the password, then she will not be able to convince Bob that she knows the password 3. If Alice knows the password, then even the dishonest Bob does not know anything except the fact that Alice knows the password In the version where Bob knows where Alice turned - Bob may cheat and thus may not know whether Alice knows the password or not. With regards to twin sister - this is one of the vulnerabilities of this protocol. Alas, there is no ideal. - Barmaley
    • one
      @Barmaley ♦ In other words, if Bob knows where Alice has turned and begins to cheat (as you don’t really understand), will he deceive himself about Alice’s knowledge? - avp
    • one
      @avp, when proving with zero disclosure, there is a condition that no information should be passed on to the verifier. In the case of knowing where Alice turned, this condition will be violated and the proof will no longer be "proof with zero disclosure." All the same, Bob-Alice is just an example, which should demonstrate the principle itself. - Alex Krass