From msuinfo!agate!howland.reston.ans.net!noc.near.net!uunet!ddsw1!chinet!schneier Sat May 15 18:49:44 1993
Newsgroups: sci.crypt
Path: msuinfo!agate!howland.reston.ans.net!noc.near.net!uunet!ddsw1!chinet!schneier
From: schneier@chinet.chinet.com (Bruce Schneier)
Subject: Re: Three Cryptographers
Message-ID: <C71yM8.46A@chinet.chinet.com>
Organization: Chinet - Public Access UNIX
References: <1su76e$5k7@fnnews.fnal.gov>
Date: Sat, 15 May 1993 05:15:43 GMT
Lines: 42

In article <1su76e$5k7@fnnews.fnal.gov> newman@pokey.fnal.gov (Mark Newman) writes:
>About a week ago I attended a seminar that was being given by a
>mathematician/cryptographer. At one point he brought up a
>story to illustrate a point about a way to protect anonymouity. It was
>called "The Three Cryptographers". In it three of the learned men were
>enjoying a lunch together. When they asked for the bill, they were told
>that the meal was already payed for by a source who wished to remain
>anonymous. The three men decided that if the meal had been payed for by
>a goeverment agency, than they didn't want to accept it. If however it
>had been payed by one of them, then they would gladly accept. To protect
>the potential anonymous payer, they came up with some sort of scheme where
>each of the three would flip two coins. They would then XOR the results of
>the flip together and then if one of the people at the table had payed, they
>would invert their answer before reporting it. Then they would combine the
>results in some way, and if the answer came up to be 0 then no one at the table
>had payed, and if it came up 1 than one of them had payed.
>
>I'm may be off of the exact method, but it's close. If someone knows the
>exact algorithm, I'd appreciate it if they could let me know, it's been
>bothering me all week.
>
>Thanks,
>
>Mark

The problem is called "The Dining Cryptographers Problem," and it was
invented and solved by David Chaum ("The Dining Cryptographers Problem:
Unconditional Sender and Receive Untraceability," Journal of Cryptology,
v 1, n 1, 1988, pp. 65-75).

The algorithm is simple. Each cryptographer flips a fair secret coin with
the person to his left, and another to his right. Then each cryptographer
announces the XOR of the two coins he sees. If he paid the bill, he
announces the opposite of the XOR. If no one paid, then the XOR of all
the announced values will be 0. If someone paid, then the XOR will be 1.

It is trivial to prove this result correct, so it will be left to an
exercise.

And it was me that gave the talk at Fermilab.

Bruce