Dining cryptographers protocol

The dining cryptographers protocol is a method of anonymous communication.

Anonymous communication is an important property of network security. Anonymity is achieved when entities cannot identify each other, when there is no link back to the first entity that can be used and when there isn’t any way to verify that any two anonymous acts are performed by the same entity.

Keeping confidential who sends which messages, in a world where any physical transmission can be traced to its origin, seems impossible.

The solution presented in the “dining cryptographers” protocol offers un-traceability of both the sender and the recipient. It is unconditionally or cryptographically secure, depending on whether it is based on one-time-use keys or on public keys, respectively; it can be adapted to efficiently address a wide variety of practical considerations.

Introduction

The protocol's description as first introduced by David Chaum, Centre for Mathematics and Computer Science, Amsterdam, The Netherlands: “Three cryptographers are sitting down to dinner at a restaurant. Their waiter informs them that arrangements have been made with the maitre d'hotel for the bill to be paid anonymously. One of the cryptographers might be paying for the dinner, or it might have been NSA (U.S. National Security Agency). The three cryptographers respect each other's right to make an anonymous payment, but they also wonder if NSA is paying”.

A simpler phrasing for the above problem: Given three cryptographers A, B, and C, we want to enable one of them to transmit a bit ‘1’, such that all of them get it, but no one knows who sends it.

The cryptographers resolve their uncertainty fairly by carrying out the following protocol: The cryptographers are arranged in a circle. Each cryptographer has a two-side coin that only he and the cryptographer to his right can see. They flip the coins. Each cryptographer calculates the XOR of his coin and the coin of his left. The cryptographers who wishes to transmit the bit '1', actually broadcasts to all (1 minus the XOR), the others broadcast their XOR. If an odd number of 1s was distributed, then a bit ’1’ was transmitted. For example: A’s coin is 1, B’s coin is 1, C’s coin is 0 (so A sees his coin and B’s coin, etc.). A wants to transmit ‘1’. So A broadcasts 1 - XOR(1,1)=1 – 0 = 1, B broadcasts XOR(1,0) = 1, C broadcasts XOR(0,1) = 1. Three 1s were distributed, i.e. a bit ’1’ was transmitted.

Correctness

Why an odd number of 1s indicates that a bit ’1’ was transmitted? The total sum of the distributed bits if there is no transmission is: XOR (A, B) + XOR (B,C) + XOR (C, A).

A	B	C	XOR(A,B)	XOR(B,C)	XOR(C,A)	Sum of XORs
1	1	1	0	0	0	0
1	1	0	0	1	1	2
1	0	1	1	1	0	2
1	0	0	1	0	1	2
0	1	1	1	0	1	2
0	1	0	1	1	0	2
0	0	1	0	1	1	2
0	0	0	0	0	0	2

It can be easily seen that the sum of the XORs is always even. If one of the XORs is replaced with (1 – XOR), then the sum is odd.

Anonymity Validation

To see why the protocol is unconditionally secure if carried out faithfully, consider the dilemma of a cryptographer who is not the payer and wishes to find out which cryptographer is. (If NSA pays, there is no anonymity problem.) Going back to the three cryptographers from before, A, B and C: A knows he is the transmitter (he distributed 1 - XOR), B and C don’t know who is the transmitter: B knows that A distributed 1 and C distributed 1, he also knows that his coin is 1, and that C’s coin is 0, but he doesn’t know what is A’s coin, so he can’t know whether A’s coin is 1 and A is the transmitter (because the XOR of A’s and B’s coins is 0 and A distributed 1) or A’s coin is 0 and C is the transmitter (because the XOR of C’s and A’s coins is 0 and C distributed 1). The same argument goes for C. Thus, in each case, a nonpaying cryptographer learns nothing about which of the other two is paying.

Protocol Extensions

1) For sending messages longer than one bit, say n bits, the protocol is performed in rounds such that each round performs the protocol for one bit. In other words, each participant should have n coins or n coin-flips.

2) If more than one participant tries to transmit at the same time there is a collision. Collisions are detected by the transmitters themselves, when two participants try to transmit together – the result is an even number of 1s. If all three try to transmit together – it wouldn’t be detected. In case of a collision, a simple solution is for example to wait a number of rounds chosen at random from a suitable distribution before trying to retransmit again.

3) The number of participants can be extended from 3 to k (though with two participants, only non-participant listeners are unable to distinguish between the two potential senders). Each pair shares a secret bit. To transmit ‘0’ a cryptographer broadcasts the sum of his bits modulo 2; to transmit ‘1’ – the converse is broadcast (1 – this sum). In total, each bit is counted twice, so the sum is expected to be even, if there is no transmission; if someone transmits ‘1’, the sum is odd. To transmit a longer message than one bit, each pair of cryptographers shares a chain of secret bits, one bit for each round. (Collision detection is as before: an even number of transmissions can be detected, by the transmitters, odd number – cannot be detected).

The Model Description

Each participant is assumed to have two kinds of secret: (a) the keys shared with other participants for each round; and (b) the inversion used in each round (i.e., a 1 if the participant inverts in that round and a 0 if not). Some or all of a participant's secrets may be given to other participants in various forms of collusion. The remaining information about the system may be described as: (a) who shares keys with whom; and (b) what each participant outputs during each round (the modulo two sum of that participant's keys and inversion). This information need not be secret to ensure un-traceability. If it is publicly known and agreed, it allows various extensions. The sum of all the outputs will, of course, usually become known to all participants. In the terminology of graphs, each participant corresponds to a vertex and each key corresponds to an edge. An edge is incident on the vertices corresponding to the pair of participants that shares the corresponding key. From here on, the graph and dinner-table terminologies will be used interchangeably. Also, without loss of generality, it will be assumed that the graph is connected (i.e., that a path exists between every pair of vertices), since each connected component (i.e., each maximal connected subgraph) could be considered a separate untraceable-sender system. An anonymity set seen by a set of keys is the set of vertices in a connected component of the graph formed from the original graph by removing the edges concerned. Thus a set of keys sees one anonymity set for each connected partition induced by removing the keys. The main theorem of the security's proof of this protocol is essentially that those having only the public information and a set of keys seeing some anonymity set can learn nothing about the members of that anonymity set except the overall parity of their inversions. Thus, for example, any two participants connected by at least one chain of keys unknown to an observer are both in the same anonymity set seen by the observer's keys, and the observer gains nothing that would help distinguish between their messages.

Collusion of Participants

If the graph is not a full graph, then a connected component is anonymized. Collusion means the cooperation of participants who pool their keys in efforts to trace the messages of others. Collusion of k-1 participants breaks the anonymity. Collusion of fewer participants yields no gain that would help distinguish between different participants (only the parity of the group).In noncomplete graphs, if a full collusion (i.e. each member of the collusion exposes all of his keys to the other collusion members) includes a cut-set of vertices (i.e., one whose removal partitions the graph), the collusion can then learn something about the origin of messages originating outside the collusion; the noncolluding vertices are partitioned into disjoint subgraphs.

Examples are:

File:S graph.JPG

A collusion of 2,3,4 breaks the anonymity. The collusion isolates both 1 and 5, so it can know who transmits.

File:C graph.JPG

A collusion of 4,5 partitions the graph into two subgraphs: {1,2,3,6,7,8} and {a,b,c,d,e,f}. The collusion can know whether the message origined in {1,2,3,6,7,8} or in {a,b,c,d,e,f} (4,5 know that they are not the origin of the message). If 1 is also in the collusion, the subgraph {1,2,3,6,7,8} is partitioned to {2,3} and {6,7,8}. That is because {4,5} is a cut-set of the whole graph, and {1} is a cut -set of {1,2,3,6,7,8}.

Proof of Security

Consider, without loss of generality, a single round in which say some full collusion knows some set of keys. Remove the edges known to the collusion from the key-sharing graph and consider any particular connected component C of the remaining graph. The vertices of C thus form an anonymity set seen by the pooled keys. Informally, what remains to be shown is that the only thing the collusion learns about the members of C is the parity sum of their inversions. This is intuitively apparent, since the inversions of the members of C are each in effect hidden from the collusion by one or more unknown key bits, and only the parity of the sum of these key bits is known (to be zero). Thus the inversions are hidden by a one-time pad, and only their parity is revealed, because only the parity of the pad is known. The setting is formalized as follows: the connected component C is comprised of rn vertices and n edges. The incidence matrix M of C is defined as usual, with the vertices labeling the rows and the edges labeling the columns. Let K, I, and A be stochastic variables defined on GF(2)^n, GF(2)^m, and GF(2)^m, respectively, such that K is uniformly distributed over GF(2)^n, K and I are mutually independent, and A = (MK) cross I. In terms of the protocol, K comprises the keys corresponding to the edges, I consists of the inversions corresponding to the vertices, and A is formed by the outputs of the vertices. Notice that the parity of A (i.e., the modulo two sum of its components) is always equal to the parity of I, since the columns of M each have zero parity. The desired result is essentially that A reveals no more information about I than the parity of 1. More formally: Theorem. Let a be in GF(2)^n. For each i in GF(2)^n, which is assumed by I with nonzero probability and which has the same parity as a, the conditional probability that A = a given that I = i is 2^(1 - m). Hence, the conditional probability that I = i given that A = a is the a priori probability that I = i. Proof. Let i be an element of GF(2)^n have the same parity as a. Consider the system of linear equations (MK) cross i = a, in k an element of GF(2)^n. Since the columns of M each have even parity, as mentioned above, its rows are linearly dependent over GF(2)^m. But as a consequence of the connectedness of the graph, every proper subset of rows of M is linearly independent. Thus, the rank of M is m - 1, and so each vector with zero parity can be written as a linear combination of the columns of M. This implies that the system is solvable because i cross a has even parity. Since the set of n column vectors of M has rank m - 1, the system has exactly 2^(n - m + 1) solutions. Together with the fact that K and I are mutually independent and that K is uniformly distributed, the theorem follows easily.

Practical Considerations

1. Establishing Keys: For long messages there is a need to provide long keys (i.e. chain of bits). One way to do this is for one member of each pair to toss many coins in advance, or – in other words - to generate a sufficient number of bits by a RNG (random number generator) and burn it on a CD. A second way is to establish a short key and expand it as needed. A third way is to use a Diffie -Helman key exchange [2]. 2. Underlying Communication Techniques: The communication topology is independent of the key-sharing graph. 3. For efficiency, communication can be made in blocks (i.e. participants have to group bits into blocks, instead of transmitting bit-by-bit). “In high-capacity broadcast systems, such as those based on coaxial cable, surface radio, or satellites, more efficient use of channel capacity is obtained by grouping a participant's contribution into a block about the size of a single message” [2]. If the block size is one message, contentions protocols may be used: One frame is used to transmit a block. In case of collision, the participant waits a random number of frames and tries to retransmit. If the block size is more than one message, a first block may be used to request a “slot reservation” in a second block. “A simple scheme would be for each anonymous sender to invert one randomly selected bit in the first block for each slot they wish to reserve in the second block. After the result of the first block becomes known, the participant who caused the ith 1 bit in the first block sends in the ith slot of the second block” [2]. 4. Example Key-Sharing Graphs: In a complete graph m(m - 1)/2 keys are required. Sometimes this number is too large. In a circle -topology graph, each entity alone cannot learn anything, but two collaborators can partition the graph, perhaps compromising an entity between them (e.g. if A’s right neighbor is X and A’s left neighbor is Y, so if X and Y collaborate, they can identify A). Even so, in cases where nearby entities are not likely to maliciously collaborate, circle-topology may be used. “If many people wish to participate in an untraceable communication system, hierarchical arrangements may offer further economy of keys. Consider an example in which a representative from each local fully connected subgraph is also a member of the fully connected central subgraph. The nonrepresentative members of a local subgraph provide the sum of their outputs to their representative. Representatives would then add their own contributions before providing the sum to the central subgraph. Only a local subgraph’s representative, or a collusion of representatives from all other local subgraphs, can recognize messages as coming from the local subgraph. A collusion comprising the representative and all but one nonrepresentative member of a local subgraph is needed for messages to be recognized as coming from the remaining member”

Drawbacks

1. Although malicious participants cannot break the anonymity (unless there is a big - enough collusion), they can block others from transmitting by DoS (denial of service) attacks. In addition, all participants are required to form a transmission. 2. For every bit of information sent, three bits of messages have to be passed all the way around the circle. 3. The last participant to transmit can “read” a message and pass a different message on.

DC Networks

The DC problem is the basis of a kind of network that gives absolute sender anonymity for messages, which is called a DC-net or “Dining Cryptographer’s network”. In DC-nets, each participant can send messages to all others and none can tell from whom this message is. If a participant wishes to send a message to a specific recipient (only), he can encrypt it in a way that only the intended recipient can decrypt. A DC network allows both the sender and the recipient to remain anonymous.

Conclusion

This solution to the “dining cryptographers” problem demonstrates that unconditional secrecy channels can be used to construct an unconditional sender un-traceability channel. It also shows that a public-key distribution system can be used to construct a computationally secure sender-un-traceability channel. The approach appears able to satisfy a wide range of practical concerns.

References

Chaum, David (1988). The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability. Journal of Cryptology. {{cite book}}: Text "pages 65-75" ignored (help)

Chaum, David. Untraceable Electronic Mail, Return Addresses, and Digital Psuedonyms. CACM 24(2):84-88, 1981. CACM 42(2), 1999. h.