Wikipedia:WikiProject Computing/Dining cryptographers protocol/Rewrite

This article is a rewrite of the existing article dining cryptographers protocol. Since this page is bound to be incomplete, unedited, or otherwise messy, please do not merge changes from here into the main article just yet.

Problem Statement

Dining Cryptographers

A group of cryptographers are enjoying dinner at a local restaurant. Upon requesting their bill, the cryptographers are surprised to learn from their host that payment for the dinner has already been anonymously arranged and that the group owes nothing. They speculate that the payer might be one of the cryptographers in the party, but then they realize that the dinner may have been paid for by the National Security Agency, their employer. Though everybody at the table respects each other's right to make an anonymous payment, they still wish to know whether their meal was in fact funded by the NSA.

Problem: If it turns out that one of the cryptographers at the table is the payer, how can he anonymously signal this fact to his peers?

Solution: Each cryptographer flips a coin privately with any other member to his left and right. Then they all stand up and announce true if the two coins he can see were different (head and tails) or false if the two coins were the same (head and head or tails and tails). If one of the cyptographers is the payer, he states the opposite. If there is an odd number of trues and the number of cryptographers are odd or there is an even number of trues and the number of cryptographers are even, then the NSA paid. Elsewhere, the check was paid by a member of the group. Who actually paid is not revealed.

Aging Cryptographers

Alice and Bob are attending a prestigious awards ceremony. At this event, it is custom for attendees to sit next to the Master of Ceremonies in order of age. In such a manner the MC wishes to have the oldest and most seasoned recipients sitting closest to him; the youngest members sit at the far end of the table. Alice and Bob wish to determine which of the two is older and thus should be seated closer to the head of the table. However, having never met before, they do not know each other's age. Neither wants to seem rude at a formal function, so they quickly discount the idea of asking each other for his or her age.

Problem: How can Alice and Bob determine which is older without telling each other their ages?

Voting Cryptographers

The CEO of a company that produces cryptographic software is retiring, so the company's board of directors chooses two candidates to replace him. The board convenes, and during this meeting they discuss the merits of each candidate and the likely benefits that each would bring to the company. Since this is a fair and respected organization, company policy states that at the end of the meeting a secret ballot will be used to elect a new CEO. The election process is a democratic one: each board member may cast one vote, and all votes are given equal weight. The candidate who received the greatest number of votes is promoted to CEO.

Problem: Given the requirements of the voting process, how can the board members elect a new CEO?

General problem statement

• How to calculate $F(x_{1},x_{2},\ldots ,x_{n})$ without revealing any individual's $x_{i}$
• Describe need for new protocol to solve problem

History

• (Does this protocol even have a well-defined history?)
  • CCG '88, about CDG '87: "This solution was the first one to raise the hope that such protocols could be implemented in an unconditionally secure way." (p. 12)
• What were the design goals for this protocol?

The Dining Cryptographers Protocol

The dining cryptographers protocol allows for any member of a group to multicast data to every other member of the group. Though the broadcast is public, the protocol guarantees that its sender remains anonymous. This protocol allows only for one member of the group to transmit data during any given round.

Transmitting one bit

Consider that there are $n$ cryptographers sitting around a circular table, so for convenience they shall be numbered $P_{1}$, $P_{2}$, $...$, $P_{n-1}$, $P_{n}$. The cryptographers are arranged such that $P_{i}$ has as his neighbors $P_{i-1}$ and $P_{i+1}$. ($P_{1}$ sits between $P_{n}$ and $P_{2}$; $P_{n}$ sits between $P_{n-1}$ and $P_{1}$.) Additionally, there are $n$ pairs of adjacent cryptographers. Each pair is written as $N_{(h,i)}$, where $P_{h}$ and $P_{i}$ are the cryptographers in the pair. It is obvious then that each cryptographer $P_{i}$ is a member of exactly two pairs $N_{(h,i)}$ and $N_{(i,j)}$. (Note that $h$ and $j$ are not necessarily distinct.)

Each pair $N_{(h,i)}$ secretly chooses one bit at random; this bit $b_{(h,i)}$ is known only to $P_{h}$ and $P_{i}$. In this manner a total of $n$ random bits are chosen among all adjacent pairs of cryptographers. Then each cryptographer $P_{i}$ should know exactly two bits of information: $b_{(h,i)}$ and $b_{(i,j)}$.

Each cryptographer $P_{i}$ now computes a value $v_{i}=b_{(h,i)}\oplus b_{(i,j)}\oplus s_{i}$, where the $b$ values are the secret bits known by $P_{i}$ and $s_{i}$ is the signal that he wishes to send anonymously. This value $v_{i}$ is made public to all persons sitting at the table. When all $v$ values have been made public, the existence of a signal $s$ can be detected by calculating the bitwise XOR of every $v_{i}$. This XOR operation yields the following:

$s=v_{1}\oplus \cdots \oplus v_{n}$

$s=(b_{(n,1)}\oplus b_{(1,2)}\oplus s_{1})\oplus \cdots \oplus (b_{(n-1,n)}\oplus b_{(n,1)}\oplus s_{n})$

$s=(b_{(n,1)}\oplus b_{(n,1)}\oplus s_{1})\oplus \cdots \oplus (b_{(n-1,n)}\oplus b_{(n-1,n)}\oplus s_{n})$

$s=s_{1}\oplus \cdots \oplus s_{n}$

Assuming that at most one person is attempting to send a signal over the channel, at most one value $s_{i}$ on the right-hand side of the last equation should be 1, yielding $s=1$. If nobody tried sending a signal over the channel, then it is evident that this equation yields $s=0$. Hence all cryptographers can detect the existence of a signal if one is sent.

This is trivially anonymous as determining the sender requires knowing the secrets. As $s=s_{1}\oplus \cdots \oplus s_{n}$, and saying node $i$ was the sender, without knowing all secrets except for the sender ($s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,s_{n}$) any of the nodes could have transmitted the message, and each therefore appears equally likely to any attacker as long as the number of attackers is less than $n-2$.

Example

• One-bit communication using n coins as entropy source
• Pictures are nice :)

Transmitting multiple bits

• Explain protocol for multi-bit signal
• Quick overview of proof (should be same as one-bit)

The Dining Cryptographers in the Disco

• Add short description of this protocol

Security considerations

• Advantages
  • Anonymous sender
  • Anonymous recipient (if key used)
    • Allow key to be sent in main channel rather than key channel
• Disadvantages
  • Slow Isn't really slow, as calculation are just some ADD's or XOR's. But much data overhead. 2n bytes transfer for one byte in case of peer to peer communication (n is number of participants)
  • Malicious party can inject random bits to mess up data
    • Chaum present trap massagesmessages to prevent malicious data
  • Collusion to detect who sent the signal
    • Only if described as above with only one key exchange to the "right" participant. Chaum used this as introductional example only and quickly came to exchange keys between all participants. This prevents collusion completely.

The Aging Cryptographers Protocol

Main article: Yao's Millionaires' Problem

The aging cryptographers protocol allows for every member of a group to contribute inputs to a function that can be calculated by all members of the group. The protocol guarantees both that an input to the function cannot be traced back to any particular participant and that each participant calculates the same result. (In other words, a correct implementation of the protocol guarantees that the participant calculates the correct result.) All members of the group may transmit data simultaneously during any given round.

Protocol

• Description of protocol
• Proof of correctness
• Proof of anonymitity (of age)

Example

• Alice and Bob, as described earlier

Security considerations

• (?)

The Voting Cryptographers Protocol

The voting cryptographers protocol is similar to the aging cryptographers protocol. It guarantees both that any particular input cannot be traced back to its source and that all participants correctly implementing the protocol agree on the final result. Additionally, this protocol is immune to attack from a participant trying to change another's vote or otherwise causing disruption. All members of the group may transmit data simultaneously during any given round.

Two candidates

• Description of protocol
• Proof of correctness
• Proof of anonymitity (of vote)

Security considerations

• Collusion (?)

Possible References

• David Chaum (1988). "The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability". Journal of Cryptology. 1 (1): 65–75. doi:10.1007/BF00206326.
• Emin Gun Sirer; Sharad Goel; Mark Robson; Dogan Engin (2004). "Eluding Carnivores: File Sharing with Strong Anonymity" (PDF). Proceedings of the European SIGOPS Workshop, Leuven, Belgium.
• P. Golle & A. Juels (2004). "Dining Cryptographers Revisited" (PDF). Eurocrypt ’04. pp. 456–473.
• Franco Raimondi & Alessio Lomuscio (2004). "Verification of Multiagent Systems via Ordered Binary Decision Diagrams: An Algorithm and Its Implementation". Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2. pp. 630–637. doi:10.1109/AAMAS.2004.295.
• David Chaum, Claude Crépeau and Ivan Damgård (1988). "Multiparty unconditionally secure protocols". Proceedings of the twentieth annual ACM symposium on Theory of computing. pp. 11–19.
• Shlomi Dolev & Rafail Ostrovsky (2000). "Xor-Trees for Efficient Anonymous Multicast and Reception". ACM Transactions on Information and System Security. 3 (2): 63–84. doi:10.1145/354876.354877.
• Christian Cachin & Jan Camenisch (2004). Advances in Cryptology - EUROCRYPT 2004. Berlin: Springer. ISBN 3-540-21935-8.
• G. Goos & J. Hartmanis (1987). Advances in Cryptology - CRYPTO '87. Berlin: Springer-Verlag. ISBN 3-540-18796-0.
• G. Good & J. Hartmanis (1990). Advances in Cryptology - EUROCRYPT '89. Berlin: Springer-Verlag. ISBN 3-540-53433-4.
• Bruce Schneier (1996). Applied Cryptography. LOCATION?:Wiley. ISBN 0-471-11709-9.