DC problem

from Wikipedia, the free encyclopedia

The problem of the dining cryptographers (cryptologists who go to eat, sometimes also called superimposed sending ) is a model for anonymous communication in closed groups. It was formulated by David Chaum in the 1980s and has since been refined from an original one-bit protocol with practical problems in mind.

motivation

Chaum's original example describes the following situation: Three cryptologists have arranged to meet for dinner in a restaurant. The waiter informs his guests that someone has given their consent to pay the cryptologists' bill. They respect the right of everyone to take over the payment anonymously, but want to know whether it was one of the three people or an outsider. To determine this (assuming that all three cryptologists are honest and not two cryptologists share the bill - in ignorance of the third party) proceed according to the following protocol:

  1. Two cryptologists each generate a secret bit that is not known to the third party. So between Alice Bob and Carol there are bits AB, BC, CA. (In the example, Chaum describes that behind the menu, invisible to the third party, a coin is tossed)
  2. Every cryptologist now knows two bits that he shared with the other two. However, no cryptologist knows bits in which he is not involved. Now everyone calculates the exclusive or from the two known bits . So if AB = 0 and CA = 1, Alice calculates AB ^ CA = 1.
  3. If a cryptologist has not paid, he announces this result, otherwise the opposite.
  4. The three results are also linked with the exclusive or. If the result of this is 0, none of the three cryptologists paid. If, on the other hand, it is 1, one of the cryptologists stated that he had paid.

Generalized models assume that the same methodology is used to transmit entire messages anonymously (each of the participants can be considered as the sender). These can also be viewed as a sequence of individual bits.

Practical problems

The example given above all has a didactic function. When implementing in software to enable anonymous communication in closed groups, some important weaknesses of this model must be considered:

  1. Secrecy of the keys : If you know the secret bits (in the example, someone who observes all three coin flips), you can use the published bits (which are read out by a certain cryptologist, i.e. are naturally not anonymous themselves) to determine who the sender is, identify the person who paid the bill. Because of the high bandwidth that would be required, the proposed practical protocols usually do not exchange long random sequences, but use the output of a stream cipher algorithm .
  2. Communication disruption : Communication can be accidentally or intentionally disrupted. Accidentally in the example, when two cryptologists paid together and both stated that they had paid due to uncertainty. This is also problematic with messages in that z. B. an anonymous chat can be accidentally disturbed if several users want to send in a round. Methods to avoid this are reservation protocols that clearly regulate who is allowed to send and when. Deliberate disruptions can also take place anonymously in that a user sends senseless data without permission in the sense of such a reservation protocol.
  3. Bandwidth : All users must publish data with the length of the anonymous message; if a central instance such as a server is missing, this means that each participant has to send the data to each other. Even with small groups, this means that significantly higher bandwidths are required than, for example, a conventional IRC chat (without anonymity of the sender).

Logs

In order to be able to use the method that solves the original DC problem in practice, far-reaching drafts for network protocols have to be designed. These have to regulate, for example, how it can be determined (anonymously) that someone wants to send, and how participants who cause deliberate interference can be effectively excluded from communication.

Suggestions (which so far have only been implemented academically or on an experimental basis) are: DC +, Herbivore, Dissent, and SecretRoom.

Web links

Individual evidence

  1. ↑ Steinacker, Angelika .: Anonymous communication in networks . BI-Wiss.-Verl, Mannheim 1992, ISBN 3-411-15531-0 .
  2. ^ David Chaum: The dining cryptographers problem: Unconditional sender and recipient untraceability . In: Journal of Cryptology . tape 1 , no. 1 , January 1, 1988, ISSN  1432-1378 , pp. 65-75 , doi : 10.1007 / BF00206326 .