Zero Knowledge in the Cave
Zero Knowledge in the Cave There is a cave with a large entry room. From this room lead two passageways, 1 and 2. Each of 1 and 2 branches into a myriad of smaller passages, twisting and turning through the massive rock formation. The passageways go on for miles and have never been fully explored. One of the big questions has been whether passageways 1 and 2 ever connect up. Is there a way of getting from 1 to 2? Many have searched, but none have ever succeeded. Most people believe that no connection will ever be found. At least, no one used to. Now an explorer comes to you and claims to have found a passage from 1 to 2, not a very long one, either. He will prove it to you, but to you alone. Being a secretive type, he wants no one else to know. If you accompany him to the cave, he will prove the existence of the passageway to you. But there's a problem. You carry a video camera and record everything that you see. If he shows you the existence of the passage, you will be able to show the video tape to others, and they will learn of its existence as well. Not to worry, he says. Come with me. So you enter the large entry room of the cave together. Now the simplest thing to do in order to demonstrate the existence of the connection would be for him to leave through passage 1 and return through passage 2. He could easily do this. However, your film record of the event would prove to anyone else who saw it that there was a connection. Another way must be found. The explorer tells you what to do. Following his instructions, you leave the entry room for a few minutes, while the explorer enters one of the passageways. You then re-enter the room, and loudly call out one of the passageway numbers, either 1 or 2. In a few minutes, the explorer comes out of the requested passageway. You then leave the cave and repeat the process many times. Each time, the reporter enters one of the passageways unknown to you; when you return and name one of them, he is able without fail to exit from the named passage. You reason that if there were no connection between the passageways, the only way the explorer could come out the passage that you named would be if he had gone in that same one. He would have to guess which one you were going to choose, and if he were right, he could come out that one. But you have repeated the test dozens of times. The chances that someone could guess right so often is infinitisimal. The only logical explanation is that the passageway does exist. Excited, you return to the tavern where you met the explorer and show the other patrons your tape. But to your surprise, they just laugh. They don't deny that the tape is real, that the explorer did come out of the passageway you named. But they don't believe in the connection. Instead, they claim you are in league with the explorer in an attempt to perpetrate a fraud. You have simply predetermined together the sequence of numbers you would call out. Each of you has memorized the sequence, and so each time the explorer is able to anticipate the number you will call next. He enters that passage and is able, after a suitable pause, to exit from that same one when you call its number. You leave the bar, frustrated. You are convinced that the connection exists, but even though the tape shows all of the evidence that was so convincing to you, no one else finds it persuasive. The explorer has achieved his goal of proving the existence of the connection to you and you alone. Questions for the student: 1. How could you have done things differently, to produce a tape that would be convincing to others? 2. What counter-measures and conditions could the explorer have put in place to prevent you from getting a convincing tape in this manner?
Big problem, you've got to -prove- that there is only one of the explorers (ie he has no twin) -and- that -only you and he are there-. Your assumption that he is not lying is a major failing of the scientific process - See the Magnificent Randy for more details and examples. Responces to your specific questions below. On Thu, 15 May 2003, Nomen Nescio wrote:
Zero Knowledge in the Cave
There is a cave with a large entry room. From this room lead two passageways, 1 and 2. Each of 1 and 2 branches into a myriad of smaller passages, twisting and turning through the massive rock formation. The passageways go on for miles and have never been fully explored.
One of the big questions has been whether passageways 1 and 2 ever connect up. Is there a way of getting from 1 to 2? Many have searched, but none have ever succeeded. Most people believe that no connection will ever be found.
At least, no one used to. Now an explorer comes to you and claims to have found a passage from 1 to 2, not a very long one, either. He will prove it to you, but to you alone. Being a secretive type, he wants no one else to know. If you accompany him to the cave, he will prove the existence of the passageway to you.
But there's a problem. You carry a video camera and record everything that you see. If he shows you the existence of the passage, you will be able to show the video tape to others, and they will learn of its existence as well.
Not to worry, he says. Come with me. So you enter the large entry room of the cave together.
Now the simplest thing to do in order to demonstrate the existence of the connection would be for him to leave through passage 1 and return through passage 2. He could easily do this. However, your film record of the event would prove to anyone else who saw it that there was a connection. Another way must be found. The explorer tells you what to do.
Following his instructions, you leave the entry room for a few minutes, while the explorer enters one of the passageways. You then re-enter the room, and loudly call out one of the passageway numbers, either 1 or 2. In a few minutes, the explorer comes out of the requested passageway. You then leave the cave and repeat the process many times. Each time, the reporter enters one of the passageways unknown to you; when you return and name one of them, he is able without fail to exit from the named passage.
You reason that if there were no connection between the passageways, the only way the explorer could come out the passage that you named would be if he had gone in that same one. He would have to guess which one you were going to choose, and if he were right, he could come out that one. But you have repeated the test dozens of times. The chances that someone could guess right so often is infinitisimal. The only logical explanation is that the passageway does exist.
Excited, you return to the tavern where you met the explorer and show the other patrons your tape. But to your surprise, they just laugh. They don't deny that the tape is real, that the explorer did come out of the passageway you named. But they don't believe in the connection.
Instead, they claim you are in league with the explorer in an attempt to perpetrate a fraud. You have simply predetermined together the sequence of numbers you would call out. Each of you has memorized the sequence, and so each time the explorer is able to anticipate the number you will call next. He enters that passage and is able, after a suitable pause, to exit from that same one when you call its number.
You leave the bar, frustrated. You are convinced that the connection exists, but even though the tape shows all of the evidence that was so convincing to you, no one else finds it persuasive. The explorer has achieved his goal of proving the existence of the connection to you and you alone.
Questions for the student:
1. How could you have done things differently, to produce a tape that would be convincing to others?
You can't, video is too easily manipulated. It is not strong enough for any sort of real-world 'proof' without extensive corroborating evidence.
2. What counter-measures and conditions could the explorer have put in place to prevent you from getting a convincing tape in this manner?
This is a moot point since the possibilities are endless. In short, your entire scenario is swiss cheese. -- ____________________________________________________________________ We are all interested in the future for that is where you and I are going to spend the rest of our lives. Criswell, "Plan 9 from Outer Space" ravage@ssz.com jchoate@open-forge.org www.ssz.com www.open-forge.org --------------------------------------------------------------------
At 7:20 PM -0700 5/14/03, Nomen Nescio wrote:
Zero Knowledge in the Cave
There is a cave with a large entry room. From this room lead two passageways, 1 and 2. Each of 1 and 2 branches into a myriad of smaller passages, twisting and turning through the massive rock formation. The passageways go on for miles and have never been fully explored.
One of the big questions has been whether passageways 1 and 2 ever connect up. Is there a way of getting from 1 to 2? Many have searched, but none have ever succeeded. Most people believe that no connection will ever be found.
This description is remarkably like the description of Jewel Cave (National Monument) when Herb and Jan Conn start exploring in the 1960s. The park wanted them to find a connection between two passages that separated close to the entrance so they could run tour groups that didn't have to pass each other in the narrow passages. In 1969, there were 54 miles of passage mapped, and still no connection. It is now over 127 miles, and still no connection. Cheers - Bill ------------------------------------------------------------------------- Bill Frantz | Due process for all | Periwinkle -- Consulting (408)356-8506 | used to be the | 16345 Englewood Ave. frantz@pwpconsult.com | American way. | Los Gatos, CA 95032, USA
On Wednesday, May 14, 2003, at 07:20 PM, Nomen Nescio wrote:
Zero Knowledge in the Cave
There is a cave with a large entry room. From this room lead two passageways, 1 and 2. Each of 1 and 2 branches into a myriad of smaller passages, twisting and turning through the massive rock formation. The passageways go on for miles and have never been fully explored.
One of the big questions has been whether passageways 1 and 2 ever connect up. Is there a way of getting from 1 to 2? Many have searched, but none have ever succeeded. Most people believe that no connection will ever be found.
....... I recall reading a very similar explanation of ZK interactive proofs, using "zero knowledge in the cave," many years ago. By one of the founders of the field I haven't searched for it to compare his (or hers, though I don't recall it as an article by Shafi G.) words to yours, but you should have given credit to using the "zero knowledge in the cave" version of ZKIPS. --Tim May
I recall reading a very similar explanation of ZK interactive proofs, using "zero knowledge in the cave," many years ago. By one of the founders of the field
I haven't searched for it to compare his (or hers, though I don't recall it as an article by Shafi G.) words to yours, but you should have given credit to using the "zero knowledge in the cave" version of ZKIPS.
--Tim May
I've seen the cave example in at least several places. Most of them make this reference: [QG90] J.J. Quisquater and L. Guillou, How to explain zero-knowledge protocols to your children, Advances in Cryptology - Crypto '89, Springer-Verlag (1990), 628-631. Patrick http://lucrative.thirdhost.com/
On Thursday, May 15, 2003, at 12:31 AM, Patrick wrote:
I recall reading a very similar explanation of ZK interactive proofs, using "zero knowledge in the cave," many years ago. By one of the founders of the field
I haven't searched for it to compare his (or hers, though I don't recall it as an article by Shafi G.) words to yours, but you should have given credit to using the "zero knowledge in the cave" version of ZKIPS.
--Tim May
I've seen the cave example in at least several places. Most of them make this reference:
[QG90] J.J. Quisquater and L. Guillou, How to explain zero-knowledge protocols to your children, Advances in Cryptology - Crypto '89, Springer-Verlag (1990), 628-631.
Yes, this is where I first saw it. I don't know if "Nomen Nescio" added any twists, so to speak, to the cave example, but he should not have paraphrased the cave example without some credit. (When I give my explanation of ZKIPS in terms of Hamiltonian cycles, which I certainly did not invent, I give enough informal comments to make it clear that this was not some invention on my part.) --Tim May "Gun Control: The theory that a woman found dead in an alley, raped and strangled with her panty hose, is somehow morally superior to a woman explaining to police how her attacker got that fatal bullet wound"
Nomen postulates:
Following his instructions, you leave the entry room for a few minutes, while the explorer enters one of the passageways. You then re-enter the room, and loudly call out one of the passageway numbers, either 1 or 2. In a few minutes, the explorer comes out of the requested passageway. You then leave the cave and repeat the process many times. Each time, the reporter enters one of the passageways unknown to you; when you return and name one of them, he is able without fail to exit from the named passage.
You reason that if there were no connection between the passageways, the only way the explorer could come out the passage that you named would be if he had gone in that same one. He would have to guess which one you were going to choose, and if he were right, he could come out that one. But you have repeated the test dozens of times. The chances that someone could guess right so often is infinitisimal. The only logical explanation is that the passageway does exist.
A more interesting question would be: If there is no connection between the passageways, and if the explorer manages to pick the passage you are going yell out correctly a large number of times, would you be better off betting or not betting $1 against him being able to do it again at 1000:1 odds. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"
On Thu, 15 May 2003, Nomen Nescio wrote:
Zero Knowledge in the Cave
There is a cave with a large entry room. From this room lead two passageways, 1 and 2. Each of 1 and 2 branches into a myriad of smaller passages, twisting and turning through the massive rock formation. The passageways go on for miles and have never been fully explored. ... 1. How could you have done things differently, to produce a tape that would be convincing to others?
Flip a coin each time you called out which entrace you wanted him to come out of. Couldn't have been predetermined that way. Plus, since he's hidden in the cave, he can't see you proving to the camera this is random and therefore doesn't know you've foiled his intent.
2. What counter-measures and conditions could the explorer have put in place to prevent you from getting a convincing tape in this manner?
Claiming it was a loaded coin after he hears about it? :-) He could force you to write down your list of tunnels in advance, and you must call off the list in order. Each time he correctly leaves the right tunnel, you must show him the list to prove that you haven't faked the list or changed the order. You know he didn't see the list beforehand, you're convinced, people watching your tape don't know he didn't see the list beforehand, and won't be. There's probably a much easier way of doing that, I imagine. -- jordan wiens --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
A highly effective variant of this protocol is in widespread use among alien abductors to make sure their human captives can't prove the aliens' existence.
You reason that if there were no connection between the passageways, the only way the explorer could come out the passage that you named would be if he had gone in that same one. He would have to guess which one you were going to choose, and if he were right, he could come out that one. But you have repeated the test dozens of times. The chances that someone could guess right so often is infinitisimal. The only logical explanation is that the passageway does exist.
A skeptic of the above scenario could claim that the "explorer" was actually a pair of identical twins (one of whom was hiding in the cave before you entered) rather than a single individual. One possible defense against this would involve an uncopiable but verifiable token given to the "first" explorer. - Bill --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
participants (9)
-
Bill Frantz -
Bill Sommerfeld -
Eric Cordian -
Jim Choate -
Jordan Wiens -
Matt Crawford -
Nomen Nescio -
Patrick -
Tim May