Example: Multi-Party Computation Protocols

The dining cryptographers problem, described in [C88], investigates how anonymity can be guaranteed during secure multi-party computation. Informally: a group of cryptographers dine at a restaurant, and the waiter informs them that the bill is to be paid anonymously; it may be paid by any of the diners, or (for example) by the national security agent sitting at an adjacent table. After the bill has been paid, how do the diners collectively discover whether one of them paid the bill, while respecting their fellow diners' right to anonymity?

The DC-net, also described in [C88], is a solution to the dining cryptographers problem; it provides unconditional sender and recipient untraceability. Briefly, DC-nets function as follows:

  1. Each diner generates a random bit visible only to them and the diner to their left, giving each diner sight of two separate randomly-generated bits.
  2. Each diner computes the XOR of the two bits visible to them and announces the result publicly to the rest of the table — except for the payer, who announces the inverse of their XOR computation.
  3. The XOR of the announcements themselves allow all of the diners at the table to verify whether one of them paid: if this value is 1, one of the diners claimed to have paid; if it is 0, nobody claimed to have paid.

This protocol preserves the anonymity of the payer; however, care must be taken when implementing the protocol to ensure that side-channels do not leak information about the payer's identity.

This example implements a multithreaded, object-oriented DC-net in Java. Four Diners are seated at a Table and one of them is randomly selected to be the payer; the identity of the payer is marked as a secret. The Diners then concurrently execute the protocol described above: they privately exchange their randomly-generated bits with each other using Sockets, and the payer sends their payment details to the Waiter over another private Socket. The Diners then announce the results of their XOR computation to the rest of the Table; the messages sent to the Table's Socket are publicly visible, and are marked as observable. We can therefore quantify what a passive attacker learns about the payer's identity by watching the messages sent to the Table.

LeakWatch estimates that there are ≈1.15 of a possible 2 bits of mutual information between the identity of the payer and the messages the Diners broadcast to the Table. Although the messages themselves reveal no information about the identity of the payer, the order in which they are sent does: the additional time taken by the payer to send their payment details to the Waiter means that, more often than not, they are one of the last Diners to announce the result of their XOR computation to the Table.

This leakage can be eliminated in several ways; one method is to modify the DC-net implementation (by uncommenting line 129 of Diner.java) so that each Diner waits a minimum of 100ms before sending their announcement to the Table's socket; this makes it more likely that messages will arrive at the Table's socket in any order.