Dining cryptographers problem
In cryptography, the dining cryptographers problem studies how to perform a secure multi-party computation of the boolean-XOR function.
David Chaum first proposed this problem in the early 1980s and used it as an illustrative example to show that it was possible to send anonymous messages with unconditional sender and recipient untraceability.
Anonymous communication networks based on this problem are often referred to as DC-nets (where DC stands for "dining cryptographers").
The waiter informs them that the meal has been paid for by someone, who could be one of the cryptographers or the National Security Agency (NSA).
The cryptographers respect each other's right to make an anonymous payment, but want to find out whether the NSA paid.
David Chaum coined the term dining cryptographers network, or DC-net, for this protocol.
It has several limitations, however, some solutions to which have been explored in follow-up research (see the References section below).
[4] DC-nets are readily generalized to allow for transmissions of more than one bit per round, for groups larger than three participants, and for arbitrary "alphabets" other than the binary digits 0 and 1, as described below.
To enable an anonymous sender to transmit more than one bit of information per DC-nets round, the group of cryptographers can simply repeat the protocol as many times as desired to create a desired number of bits worth of transmission bandwidth.
In practical DC-net systems, it is typical for pairs of participants to agree up-front on a single shared "master" secret, using Diffie–Hellman key exchange for example.
Each participant then locally feeds this shared master secret into a pseudorandom number generator, in order to produce as many shared "coin flips" as desired to allow an anonymous sender to transmit multiple bits of information.
In each round of the protocol, if a participant wants to transmit an untraceable message to the group, they invert their publicly announced bit.
The protocol may be run with less than fully connected secret sharing graphs, which can improve the performance and scalability of practical DC-net implementations, at the potential risk of reducing anonymity if colluding participants can split the secret sharing graph into separate connected components.
However, if Adam and Charlie are actually NSA agents sitting immediately to the left and right of Bob, an innocent victim, and if Adam and Charlie secretly collude to reveal their secrets to each other, then they can determine with certainty whether or not Bob was the sender of a 1 bit in a DC-net run, regardless of how many participants there are in total.
Though the simple DC-nets protocol uses binary digits as its transmission alphabet, and uses the XOR operator to combine cipher texts, the basic protocol generalizes to any alphabet and combining operator suitable for one-time pad encryption.
This flexibility arises naturally from the fact that the secrets shared between the many pairs of participants are, in effect, merely one-time pads combined symmetrically within a single DC-net round.
Such a choice of alphabet and operator makes it possible for clients to use zero-knowledge proof techniques to prove correctness properties about the DC-net ciphertexts that they produce, such as that the participant is not "jamming" the transmission channel, without compromising the anonymity offered by the DC-net.
[10] This evasion approach introduces the risk that an adversary who owns many nodes could selectively disrupt only groups the adversary has not completely compromised, thereby "herding" participants toward groups that may be functional precisely because they are completely compromised.
The original protocol[9] used a verifiable cryptographic shuffle to form a DC-net transmission schedule and distribute "transmission assignments", allowing the correctness of subsequent DC-nets ciphertexts to be verified with a simple cryptographic hash check.
This technique required a fresh verifiable before every DC-nets round, however, leading to high latencies.
