Proving Things With Hats
When you log into your bank, you may be asked for certain characters from your password. If Eve was trying to hack Bob’s account, she might guess the characters correctly, but the more times she is asked, the less chance there will be in getting the characters right, based on a random guess.
In a similar way, Victor (the verifier) might challenge Peggy (the prover) to reveal something about her secret, and every time she gets it right, Victor will increasingly trust that Peggy knows the secret. Eventually, he might define that he has prompted Peggy enough, and does not have to challenge her anymore. For a character for a password, Eve has a 1-in-26 chance of getting it right for the first prompt, and might strike lucky, but in the next character, her chances of getting two characters correct from random guessing with only be 1-in-676 (26 * 26).
The Hats Problem
In an interactive form, Victor can challenge Peggy to prove that she has a given solution, and for Victor not to see what her solution is. In Figure 1, Victor sends Peggy a puzzle and asks her to colour-in the circles so that none of the circles that are connected by the vertices have the same colour, and that only three colours are used (red, yellow and green).
