In cryptography, the dining cryptographers problem studies how to perform a
secure multi-party computation
Secure multi-party computation (also known as secure computation, multi-party computation (MPC) or privacy-preserving computation) is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their ...
of the boolean-XOR function.
David Chaum first proposed this problem in the early 1980s and used it as an illustrative example to show that it was possible to send anonymous messages with unconditional sender and recipient untraceability. Anonymous communication networks based on this problem are often referred to as DC-nets (where DC stands for "dining cryptographers").
Despite the word ''dining'', the dining cryptographers problem is unrelated to the
dining philosophers problem
In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them.
It was originally formulated in 1965 by Edsger Dijkstra ...
.
Description
![Dining Cryptographers](https://upload.wikimedia.org/wikipedia/commons/5/5a/Dining_Cryptographers.svg)
Three cryptographers gather around a table for dinner. The waiter informs them that the meal has been paid for by someone, who could be one of the cryptographers or the
National Security Agency
The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collect ...
(NSA). The cryptographers respect each other's right to make an anonymous payment, but want to find out whether the NSA paid. So they decide to execute a two-stage protocol.
In the first stage, every two cryptographers establish a shared one-bit secret, say by tossing a coin behind a menu so that only two cryptographers see the outcome in turn for each two cryptographers. Suppose, for example, that after the coin tossing, cryptographer A and B share a secret bit
, A and C share
, and B and C share
.
In the second stage, each cryptographer publicly announces a bit, which is:
* if they didn't pay for the meal, the
exclusive OR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
(XOR) of the two shared bits they hold with their two neighbours,
* if they did pay for the meal, the opposite of that XOR.
Supposing none of the cryptographers paid, then A announces
, B announces
, and C announces
. On the other hand, if A paid, she announces
.
The three public announcements combined reveal the answer to their question. One simply computes the XOR of the three bits announced. If the result is 0, it implies that none of the cryptographers paid (so the NSA must have paid the bill). Otherwise, one of the cryptographers paid, but their identity remains unknown to the other cryptographers.
David Chaum coined the term ''dining cryptographers network'', or DC-net, for this protocol.
Limitations
The DC-net protocol is simple and elegant. It has several limitations, however, some solutions to which have been explored in follow-up research (see the References section below).
; Collision : If two cryptographers paid for the dinner, their messages will cancel each other out, and the final XOR result will be
. This is called a collision and allows only one participant to transmit at a time using this protocol. In a more general case, a collision happens as long as any even number of participants send messages.
; Disruption : Any malicious cryptographer who does not want the group to communicate successfully can jam the protocol so that the final XOR result is useless, simply by sending random bits instead of the correct result of the XOR. This problem occurs because the original protocol was designed without using any
public key
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic al ...
technology and lacks reliable mechanisms to check whether participants honestly follow the protocol.
; Complexity : The protocol requires pairwise shared secret keys between the participants, which may be problematic if there are many participants. Also, though the DC-net protocol is "unconditionally secure", it actually depends on the assumption that "unconditionally secure" channels already exist between pairs of the participants, which is not easy to achieve in practice.
A related
anonymous veto network algorithm computes the logical OR of several users' inputs, rather than a logical XOR as in DC-nets, which may be useful in applications to which a logical OR combining operation is naturally suited.
History
David Chaum first thought about this problem in the early 1980s. The first publication that outlines the basic underlying ideas is his. The journal version appeared in the very first issue of the Journal of Cryptology.
Generalizations
DC-nets are readily generalized to allow for transmissions of more than one bit per round, for groups larger than three participants, and for arbitrary "alphabets" other than the binary digits 0 and 1, as described below.
Transmissions of longer messages
To enable an anonymous sender to transmit more than one bit of information per DC-nets round, the group of cryptographers can simply repeat the protocol as many times as desired to create a desired number of bits worth of transmission bandwidth. These repetitions need not be performed serially. In practical DC-net systems, it is typical for pairs of participants to agree up-front on a single shared "master" secret, using
Diffie–Hellman key exchange for example. Each participant then locally feeds this shared master secret into a
pseudorandom number generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
, in order to produce as many shared "coin flips" as desired to allow an anonymous sender to transmit multiple bits of information.
Larger group sizes
The protocol can be generalized to a group of
participants, each with a shared secret key in common with each other participant. In each round of the protocol, if a participant wants to transmit an untraceable message to the group, they invert their publicly announced bit. The participants can be visualized as a
fully connected graph with the vertices representing the participants and the edges representing their shared secret keys.
Sparse secret sharing graphs
The protocol may be run with less than fully connected secret sharing graphs, which can improve the performance and scalability of practical DC-net implementations, at the potential risk of reducing anonymity if colluding participants can split the secret sharing graph into separate connected components. For example, an intuitively appealing but less secure generalization to
participants using a
ring topology
A ring network is a network topology in which each node connects to exactly two other nodes, forming a single continuous pathway for signals through each node – a ring. Data travels from node to node, with each node along the way handling ever ...
, where each cryptographer sitting around a table shares a secret ''only'' with the cryptographer to their immediate left and right, and ''not'' with every other cryptographer. Such a topology is appealing because each cryptographer needs to coordinate two coin flips per round, rather than
. However, if Adam and Charlie are actually NSA agents sitting immediately to the left and right of Bob, an innocent victim, and if Adam and Charlie secretly collude to reveal their secrets to each other, then they can determine with certainty whether or not Bob was the sender of a 1 bit in a DC-net run, regardless of how many participants there are in total. This is because the colluding participants Adam and Charlie effectively "split" the secret sharing graph into two separate disconnected components, one containing only Bob, the other containing all other honest participants.
Another compromise secret sharing DC-net topology, employed in th
Dissentsystem for scalability,
may be described as a ''client/server'' or ''user/trustee'' topology. In this variant, we assume there are two types of participants playing different roles: a potentially large number ''n'' of users who desire anonymity, and a much smaller number
of ''trustees'' whose role is to help the users obtain that anonymity. In this topology, each of the
users shares a secret with each of the
trustees—but users share no secrets directly with other users, and trustees share no secrets directly with other trustees—resulting in an
secret sharing matrix. If the number of trustees
is small, then each user needs to manage only a few shared secrets, improving efficiency for users in the same way the ring topology does. However, as long as ''at least one trustee'' behaves honestly and does not leak his or her secrets or collude with other participants, then that honest trustee forms a "hub" connecting all honest users into a single fully connected component, regardless of which or how many other users and/or trustees might be dishonestly colluding. Users need not know or guess which trustee is honest; their security depends only on the ''existence'' of at least one honest, non-colluding trustee.
Alternate alphabets and combining operators
Though the simple DC-nets protocol uses
binary digits as its transmission alphabet, and uses the XOR operator to combine cipher texts, the basic protocol generalizes to any alphabet and combining operator suitable for
one-time pad
In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent. In this technique, a plaintext is paired with a ran ...
encryption. This flexibility arises naturally from the fact that the secrets shared between the many pairs of participants are, in effect, merely one-time pads combined symmetrically within a single DC-net round.
One useful alternate choice of DC-nets alphabet and combining operator is to use a
finite group suitable for public-key cryptography as the alphabet—such as a
Schnorr group A Schnorr group, proposed by Claus P. Schnorr, is a large prime-order subgroup of \mathbb_p^\times, the multiplicative group of integers modulo p for some prime p. To generate such a group, generate p, q, r such that
:p = qr + 1
with p, q prime. ...
or
elliptic curve
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
—and to use the associated group operator as the DC-net combining operator. Such a choice of alphabet and operator makes it possible for clients to use
zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...
techniques to prove correctness properties about the DC-net ciphertexts that they produce, such as that the participant is not "jamming" the transmission channel, without compromising the anonymity offered by the DC-net. This technique was first suggested by Golle and Juels,
further developed by Franck,
and later implemented i
Verdict a cryptographically verifiable implementation of th
Dissentsystem.
Handling or avoiding collisions
The measure originally suggested by David Chaum to avoid collisions is to retransmit the message once a collision is detected, but the paper does not explain exactly how to arrange the retransmission.
Dissentavoids the possibility of unintentional collisions by using a verifiable shuffle to establish a DC-nets transmission schedule, such that each participant knows exactly which bits in the schedule correspond to his own transmission slot, but does not know who owns other transmission slots.
Countering disruption attacks
divides a large anonymity network into smaller DC-net groups, enabling participants to evade disruption attempts by leaving a disrupted group and joining another group, until the participant finds a group free of disruptors.
This evasion approach introduces the risk that an adversary who owns many nodes could ''selectively'' disrupt only groups the adversary has not ''completely'' compromised, thereby "herding" participants toward groups that may be functional precisely because they are completely compromised.
Dissentimplements several schemes to counter disruption. The original protocol
used a verifiable
cryptographic shuffle to form a DC-net transmission schedule and distribute "transmission assignments", allowing the correctness of subsequent DC-nets ciphertexts to be verified with a simple
cryptographic hash
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output ...
check. This technique required a fresh verifiable before every DC-nets round, however, leading to high latencies. A later, more efficient scheme allows a series of DC-net rounds to proceed without intervening shuffles in the absence of disruption, but in response to a disruption event uses a shuffle to distribute anonymous ''accusations'' enabling a disruption victim to expose and prove the identity of the perpetrator.
Finally, more recent versions support fully verifiable DC-nets - at substantial cost in computation efficiency due to the use of
public-key cryptography
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
in the DC-net - as well as a ''hybrid'' mode that uses efficient XOR-based DC-nets in the normal case and verifiable DC-nets only upon disruption, to distribute accusations more quickly than is feasible using verifiable shuffles.
References
{{reflist
Cryptography
Mathematical problems
Zero-knowledge protocols