# Dining cryptographers protocol

The dining cryptographers protocol is a method of anonymous communication. It offers untraceability of both the sender and the recipient.

## Problem Statement

### Dining Cryptographers

An odd numbered group of cryptographers is 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 the member to his left and right. Then they all stand up and annouce 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). If one of the cyptographers is the payer, he states the opposite. If there is an odd number of trues, then the NSA payed. If there is an even number, then one of the cryptographers lied, and the check was payed by a member of the group. Who actually payed is not revealed. If there were an even number of crytographers the opposite would be the case; odd, a cryptographer payed, and even, the NSA payed.

### 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 [itex]F(x_1, x_2, \ldots, x_n)[/itex] without revealing any individual's [itex]x_i[/itex]
• 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 [itex]n[/itex] cryptographers sitting around a circular table, so for convenience they shall be numbered [itex]P_1[/itex], [itex]P_2[/itex], [itex]...[/itex], [itex]P_{n-1}[/itex], [itex]P_n[/itex]. The cryptographers are arranged such that [itex]P_i[/itex] has as his neighbors [itex]P_{i-1}[/itex] and [itex]P_{i+1}[/itex]. ([itex]P_1[/itex] sits between [itex]P_n[/itex] and [itex]P_2[/itex]; [itex]P_n[/itex] sits between [itex]P_{n-1}[/itex] and [itex]P_1[/itex].) Additionally, there are [itex]n[/itex] pairs of adjacent cryptographers. Each pair is written as [itex]N_{(h,i)}[/itex], where [itex]P_h[/itex] and [itex]P_i[/itex] are the cryptographers in the pair. It is obvious then that each cryptographer [itex]P_i[/itex] is a member of exactly two pairs [itex]N_{(h,i)}[/itex] and [itex]N_{(i,j)}[/itex]. (Note that [itex]h[/itex] and [itex]j[/itex] are not necessarily distinct.)

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

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

[itex]s = v_1 \oplus \cdots \oplus v_n[/itex]

[itex]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)[/itex]

[itex]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)[/itex]

[itex]s = s_1 \oplus \cdots \oplus s_n[/itex]

Assuming that at most one person is attempting to send a signal over the channel, at most one value [itex]s_i[/itex] on the right-hand side of the last equation should be 1, yielding [itex]s = 1[/itex]. If nobody tried sending a signal over the channel, then it is evident that this equation yields [itex] s = 0[/itex]. 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 [itex]s = s_1 \oplus \cdots \oplus s_n[/itex], and saying node [itex]i[/itex] was the sender, without knowing all secrets except for the sender ([itex]s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_n[/itex]) 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 [itex]n - 2[/itex].

#### Example

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

### Transmitting multiple bits at once

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

The method is as follows: three or more cryptographers arrange themselves around a circular dinner table (ring network), with menus (encrypted links) hiding the interaction of each pair of adjacent cryptographers from the rest. Each people pair picks a random number in private and allows the person on the right to see it. Then each cryptographer announces publicly the difference between his own number and the number on his left, adding a message if he wants to transmit one. All cryptographers then add up the publicly announced numbers. If the sum is 0, no one sent a message. If the sum is a valid message, one cryptographer transmitted a message. If the sum is invalid, more than one cryptographer tried to transmit a message; they wait a random time and try again.

### The Dining Cryptographers in the Disco

• Add short description of this protocol

### Security considerations

• Anonymous sender
• Anonymous recipient (if key used)
• Allow key to be sent in main channel rather than key channel
• Slow (what is the O-notation for this?)
• Malicious party can inject random bits to mess up data
• Collusion to detect who sent the signal
• Chaum describes a method to prevent collusion

## The Ageing Cryptographers Protocol

The ageing 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

(I made this up based on the dining cryptographers protocol. What is the "real" Ageing Cryptographers Protocol ?)

• Description of protocol

Alice and Bob ask Trent to help them out.

Each one makes up a random number, and gives it to the person on their right (without letting the person on their left see).

Each one subtracts the number they were given from the left, from the number they made up (which might result in a negative number), and writes down that difference.

Alice subtracts her age from the number she just wrote down, and announces the result. On the other hand, Bob adds his age to the number he just wrote down, and announces the result.

Trent adds the number he just wrote down to the 2 numbers he hears announced. He then announces whether the result is positive (Bob is older), negative (Alice is older), or zero (both the same age).

• Proof of correctness
• Proof of anonymity (of age)

#### Example

• Alice and Bob, as described earlier

Alice gives Bob "234", Bob gives Trent "373", and Trent gives Alice "823".

Alice writes down "-589" (234 - 823), Bob writes down "+139" (373 - 234), and Trent writes down "+450" (823 - 373).

Alice announces "-624" (-589 - 35), while Bob announces "+176" (+139 + 37).

Trent finds the sum of +450 + -624 + +176 = +2, and announces the sum is positive.

Alice and Bob now realize Bob is older.

### Security considerations

• (?)
• Trent now knows the *difference* between their ages.

Variant: if Alice and Trent flip a coin ahead of time to decide which will add and which will subtract the age, but don't tell Trent, then Trent won't know which one is older. (Trent would only know the absolute value of the difference between their ages).

## The Voting Cryptographers Protocol

The voting cryptographers protocol is similar to the ageing 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 anonymity (of vote)

### Security considerations

• Collusion (?)