Subject: Zero Knowledge in the Cave - msg#00139

List: encryption.general

Date: Prev Next Index Thread: Prev Next Index

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?

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@xxxxxxxxxxxx

Was this page helpful?

Thread at a glance:

Previous Message by Date: click to view message preview

Re: A Trial Balloon to Ban Email?

On Wed, 14 May 2003, Sunder wrote: > Say, things get harder and he has to adapt, well, he'll just charge his > clients more for the trouble and advertise it as a value add that it's > garanteed that x% will be read (never mind that idiot client hasn't got a > way to prove it one way or another.) There are ways to prove it. You can use web bugs embedded in HTML mail, fetching an object from a tracking server. This doesn't work with some mailers, however Outlooks to version 5.5 are vulnerable for sure and numerous other ones are as well. This approach is already widely used for checking the validity of email addresses. You can count the clickthroughs from the mails, thus not measuring the impressions themselves, but the raw success. The spammer then can be paid not per mail sent, but per URL clicked to - leading to a new level of various confusing and enticing tactics. You can also share profit with the spammer using some kind of provision per sale, thus fully outsourcing your advertising. Possibly there are yet other ways. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@xxxxxxxxxxxx

Next Message by Date: click to view message preview

deterring coin re-use with offline coins (Re: A Trial Balloon to Ban Email?)

Sunder wrote: [...spammer sends 170k mails all with same micropayment coin...] > Each time this happens - (from my point of view I get about 50-60 > spams/day that I filter) each of those recipients turns around and sends > some traffic attempting to auth the micropayments via the micropayment > bank. That's a DDoS from the point of view of the bank. > > Even if it can handle the traffic it has to do lots of CPU intensive work > and send the error back to each of those requests, which will result in > rejection of 169,999 requests and 1 acceptance (assuming the spammer is > using a valid coin in the 1st place.) It becomes expensive to run the > mint. and Declan wrote: | It is true that the notions of micropayments as applied to spam | (that I'm familiar with, at least) would require that the email | recipient check with the bank to detect doublespending. This would | introduce an additional delay before delivery from unknown senders, | yes, but I fail to see how it would impose an unacceptable cost in | bandwidth or CPU usage. So I'm not sure if you'd want to do it, and it has other issues discussed on cpunks recently, but there are some other options here with ecash that can avoid the bank having to say "already spent" 169,999 times for each valid but already spent coin. (I concur with Sunder that if the bank had to fit such usage patterns into their business model, it would increase ther costs significantly which would make running the bank even harder to do and still turn a profit, especially as we are talking very high volume, and exceedingly low value tokens.) One assumption I'm making is presumably the micropayment system provides the option for payer and payee anonymity, or email privacy just got removed once and for all. (Trace the payments at the bank and you know who emailed who in a convenient central database - a definite privacy no-no). So with the offline brands protocol of which there was some discussion recently, the MTA could verify the coin locally. It would be assured that if the coin was locally verified as valid, he either gets the money later when he deposits, or the bank gets the spammers identity and prosecutes them for payment fraud. So (and this is why I said I don't know if you would want to do this...) this payment choice where identity is revealed iff you double-spend has the recently discussed issue: A) you have to provide your identity in the first place, and if having it revealed is any deterrent, you'd better be identified robustly (doing this identification for every email user on the planet seems a somewhat daunting task) B) the spammer will have an incentive to find a way to provide fake identity to the bank, or of buying someone else's identification (eg. someone with no credit rating, or of stealing someone else's tokens, or stealing someone else's mail services which automatically add a payment (identifying them) on event of double spend But aside from those issues (plus the showstopper issue of building a payment infrastructure to support this volume in the first place which was discussed earlier in this thread) this now gives the MTA the ability to reject double-spends locally -- modulo the amount of deterrent to double-spending anyway and being identified ends up providing after the spammers have finished attacking issue B). A remaining technical issue would be the MTA could have it's CPU overloaded as verifying such tokens is while relatively cheap (I think around DSA signature verification cost) still much more expensive than it is for the DoS spammer to send you plausibly formatted random numbers to burn off your CPU. But we have a separate solution to that: you make the spammer provide a hashcash token of comparable cost to that verification and this can be verified an one order of magnitude or more efficiently and increases the would-be DoSers costs to be comparable to the signature verification. (Or more if you wish -- legitimate mail users usually don't need to send 200 mails/sec). Sunder wrote: > From my point of view, if my MTA has already spooled the spam, I've > already lost my bandwidth, and thus lost some value. Doesn't matter > that I never see the spam. Bandwidth was already wasted receiving > bits that wind up in /dev/null and cpu cycles to make the decision > to drop said bits. Well in some cases I guess the ISP lost the bandwidth (depending on where you do your checking). But anyway personally I'd be more than happy to double by bandwidth consumption to receiving email to avoid any spam arriving in my mailbox. (As an individuals bandwidth consumption sending and receiving email is typically rather low, and entirely feasible over perhaps 15 minutes of dialup per day). Or at least to the end-user the human attention costs of spam are vastly in excess of the bandwidth costs of spam. ISPs I suspect have a different perspective: while they have some human costs -- dealing with complaints and manually throttling debilitating spam floods -- the users inconvenience at having to sort spam from non-spam is not directly their problem, other than in perhaps a competitive advantage if users will switch ISPs to use one which offers better anti-spam options. Sunder also wrote: > The current cost to the spammer is currently nearly zero. To add > hash generation for each email might slow things down a bit, but > throwing more hardware at it gets around this. Hardware is cheap, > and old out of date PC's are plentiful. The bandwidth cost is the > same, the CPU cost and time is a bit higher, but not much. I presume this comment is about hashcash or variants rather than about ecash which the rest of the post was about. Hardware is cheap, but 1 sec of CPU per sent mail on a 1Ghz machine still ends up costing by my estimates (see thread with Subject: economics of spam) about a factor of 30 more for the spammer. Note old machines are cheaper but they are also slower; the spammer would want to buy the best value for money hardware factoring in electricty costs (old slow machines don't necessarily consume less electricity, and electricity is around the same cost as the amortized cost of ownership of the machine). Adam --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@xxxxxxxxxxxx

Previous Message by Thread: click to view message preview

Sender Pays Email

There's been a lot of talk lately about various sender-pays, proof of work, and related schemes for dealing with the spam problem. I am interested in building a sender-pays anonymous value-associated stamp system using Wagnerian cash. This would involve a commercial mint, email client plugins, and all the rest. I have talent, technology, and time. But I don't have any money. Anyone who wants to try it, and has funds available, should contact me. Thanks, Patrick --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@xxxxxxxxxxxx

Next Message by Thread: click to view message preview

Re: Zero Knowledge in the Cave

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@xxxxxxxxxxxx

Loading Comments...