# LeakWatch

## 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:

- 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.
- 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.
- 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 `Diner`s 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 `Diner`s then concurrently execute the protocol described above: they privately exchange their randomly-generated bits with each other using `Socket`s, and the payer sends their payment details to the `Waiter` over another private `Socket`. The `Diner`s 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 `Diner`s 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 `Diner`s 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.

### References

- [C88] David Chaum. "The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability". Journal of Cryptology 1(1). 1988.