I Know but I'm not telling !

R. Ramanujam, The Institute of Mathematical Sciences, Chennai

"Problem 7 was so difficult, did you do it ?", asked Sujata, as she came out of the examination hall.
Sundar smiled enigmatically: "Oh yes I did it, just a simple trick was needed".
"Tell me, tell me, what's the trick ?" 
"Ah that would be too easy ! What will you give me ? One ice cream and I will tell you !"
Sujata is in a quandary. Does Sundar really know the solution, or is he merely bluffing ? If she can find out the answer, that would be well worth an ice cream, but if, after consuming the ice cream it turns out that he has no idea of the solution, life would get rather difficult.
On the other hand, Sundar would like to PROVE to her that he knows the trick, without her getting the correct answer from him. Can someone help him ?
*****
Such proofs, where A convinces B that a fact P is true, without revealing A's concrete evidence for truth of B, are called ZERO-KNOWLEDGE PROOFS. This is very important for security, where A needs to convince an authority that he is indeed A, without giving any more information.
It is not even clear that such a proof is possible, at all. What you want is a proof that convinces the other person that P is true but afterwards, she should not be able to construct the proof herself from this information. When you show that 143 is composite, you can give the divisors (11, 13) but that would be too much information.
Though this is amazing, yes, it is indeed possible to give zero knowledge proofs of SOME statements.
*****
Leela and Maya are playing the game "Where is Waldo?". This is a picture book. Waldo is a clown and much loved by the children. Each picture in the book shows a crowded scene (a beach, a fair, a party etc), somewhere inside which is Waldo. Spotting Waldo in the picture is not easy, since he wears many different costumes. The challenge is to spot him first!
Maya spots Waldo first. She exclaims: "I have seen him !"
"No, you haven't."
"Yes I have."
"Then show me."
"Why should I ? You look for him."
"Ha ha, then of course you haven't seen him."
How can Maya convince Leela that she has seen Waldo without giving away his location ?
Method 1
Maya can take a xerox of the picture, cut out Waldo's shape from it and show it to Leela (and then destroy the photocopy!). Since she could do this ony if she had indeed spotted Waldo, Leela would be convinced, and Leela does not get the location.
But where can children find xerox machines ? We need a simpler solution !
Method 2
She takes a black square sheet, cuts out the shape of Waldo, and ensuring that Leela isn't looking, she slides the black sheet on top of the picture aligning so that the hole shows Waldo inside. Ideally, it should show ony Waldo, and nothing more.
Now Leela is of course convinced, but does she get zero extra information ? Not really. If Waldo happens to be in the top right corner, she can get a rough idea of Waldo's location.
This is avoided quite easily. Suppose the Waldo picture frame is a square with side x centimetres. Then you can easily see that as long as the black sheet has sides at least 2x, Maya can always slide it so that Waldo appears in the middle, and his location is not revealed to Leela.
Now, Leela may suspect that Maya may have substituted some other picture underneath, so Maya should pull the sheet from underneath, revealing that this was indeed the given picture. (This has to be done very carefully, a least covering the hole while sliding.) 
*****
Here is another scenario. Padma has uncovered a secret word that opens a magic door in a cave. See the picture, the cave is shaped like an oval, open at one end, and blocked by the magic door at the other. Vijay is willing to pay her to learn the secret, but he will pay only if he is sure that she knows the secret. Padma will tell him only after he pays. Again they need a zero knowledge proof.
This is how they do it:
1. Vijay waits outside the cave, Padma goes in. Call the two paths from the entrance going left and right A and B. She RANDOMLY takes either path A or B.
2. Vijay enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. 
Provided that Padma really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path. Vijay, of course, does not know which path she has gone down.
However, suppose that Padma did not know the word. Then, she would only be able to return by the named path if Vijay were to give the name of the same path that she had entered by. Since Vijay would choose A or B at random, she would have only a 50% chance of guessing correctly.
If they were to repeat this trick many times, say 20 times in succession, her chance of successfully anticipating all of Vijay's requests would become very very small.
Thus, if Padma keeps appearing at the exit that Vijay names, he can conclude that she is very likely to know the secret word.
*****
There is one big difference between the first case and the second. The cave story relies on chance ! Is this still a "proof" at all ? How can even a small margin of error be alright ?
These are questions that bother philosophers a great deal, but computer scientists say this is a proof for all practical purposes and such techniques are now used in software.