DC-Problem

Das Problem der Dining Cryptographers (engl. essen-gehende Kryptologen, gelegentlich auch überlagerndes Senden genannt) ist ein Modell zur anonymen Kommunikation in geschlossenen Gruppen. Es wurde in den 1980er Jahren von David Chaum formuliert und seitdem von einem ursprünglichen Ein-Bit-Protokoll unter Berücksichtigung praktischer Probleme weiterentwickelt.

Motivation

Chaums ursprüngliches Beispiel schildert die folgende Situation: Drei Kryptologen haben sich zum Essen in einem Restaurant verabredet. Der Kellner informiert seine Gäste darüber, dass jemand sein Einverständnis gegeben hat, die Rechnung der Kryptologen zu bezahlen. Diese respektieren das Recht eines jeden, diese Übernahme der Zahlung anonym zu tätigen, möchten jedoch wissen, ob es eine der drei Personen, oder ein Außenstehender war. Um dies festzustellen (unter der Annahme, dass alle drei Kryptologen ehrlich sind und sich nicht zwei Kryptologen die Rechnung – in Unkenntnis des Dritten – teilen) gehen sie nach folgendem Protokoll vor:

1. Jeweils zwei Kryptologen erzeugen ein geheimes Bit, das dem jeweils Dritten nicht bekannt ist. Zwischen Alice, Bob und Carol gibt es also die Bits AB, BC, CA. (Chaum schildert im Beispiel, dass hinter der Speisekarte, für den Dritten unsichtbar, eine Münze geworfen wird)
2. Jeder Kryptologe kennt nun zwei Bits, die er mit jeweils den beiden anderen geteilt hat. Kein Kryptologe kennt jedoch Bits, an denen er nicht beteiligt ist. Nun berechnet jeder aus den beiden bekannten Bits das exklusive Oder. Wenn AB = 0 und CA = 1 gilt, berechnet Alice also AB ^ CA = 1.
3. Wenn ein Kryptologe nicht bezahlt hat, gibt er dieses Ergebnis bekannt, ansonsten das Gegenteil.
4. Die drei Ergebnisse werden ebenfalls mit dem exklusiven Oder verknüpft. Wenn das Ergebnis hiervon 0 ist, hat keiner der drei Kryptologen bezahlt. Ist es dagegen 1, hat einer der Kryptologen angegeben, bezahlt zu haben.

Verallgemeinerte Modelle gehen davon aus, dass mit der gleichen Methodik ganze Nachrichten anonym (jeder der Beteiligten kommt als Absender in Frage) übertragen werden. Diese lassen sich ebenfalls als Sequenz von einzelnen Bits betrachten.

Praktische Probleme

Das angeführte Beispiel hat vor allem eine didaktische Funktion. Bei der Implementierung in Software, um anonyme Kommunikation in geschlossenen Gruppen zu ermöglichen, sind einige wichtige Schwachstellen dieses Modells zu beachten:

1. Geheimhaltung der Schlüssel: Wer die geheimen Bits kennt (im Lehrbeispiel etwa jemand, der alle drei Münzwürfe beobachtet), kann anhand der veröffentlichten Bits (die von einem bestimmten Kryptologen vorgelesen werden, also selbst naturgemäß nicht anonym sind) ermitteln, wer der Absender ist, also denjenigen, der die Rechnung bezahlt hat, identifizieren. Wegen der hohen Bandbreite, die erforderlich wäre, werden in den vorgeschlagenen praktischen Protokollen für gewöhnlich nicht lange Zufallsfolgen ausgetauscht, sondern die Ausgabe eines Stromchiffre-Algorithmus genutzt.
2. Störung der Kommunikation: Die Kommunikation kann versehentlich oder absichtlich gestört werden. Versehentlich im Beispiel, wenn zwei Kryptologen zusammen bezahlt haben und aus Verunsicherung beide angeben, bezahlt zu haben. Dies ist bei Nachrichten auch insofern problematisch, dass z. B. ein anonymer Chat versehentlich gestört werden kann, wenn in einer Runde mehrere Nutzer senden wollen. Methoden, um dies zu vermeiden, sind Reservierungsprotokolle, die klar regeln, wer wann senden darf. Absichtliche Störungen können ebenfalls anonym erfolgen, indem ein Nutzer ohne Erlaubnis im Sinne eines solchen Reservierungsprotokolls sinnlose Daten sendet.
3. Bandbreite: Alle Nutzer müssen Daten mit der Länge der anonymen Nachricht veröffentlichen; fehlt eine zentrale Instanz wie ein Server, bedeutet dies, dass jeder Teilnehmer die Daten an jeden anderen senden muss. Dies hat schon bei kleinen Gruppen einen Bedarf an wesentlich höheren Bandbreiten als beispielsweise das konventionelle IRC-Protokoll (ohne Anonymität des Absenders) zur Folge.

Protokolle

Um das Verfahren, welches das ursprüngliche DC-Problem löst, praktisch nutzen zu können, sind weitreichende Entwürfe für Netzwerkprotokolle zu designen. Diese müssen etwa regeln, wie (anonym) festgestellt werden kann, dass jemand senden möchte, und wie Teilnehmer, die absichtliche Störungen auslösen, wirkungsvoll von der Kommunikation ausgeschlossen werden können.

Vorschläge (die bisher nur akademisch bzw. versuchsweise implementiert wurden) sind: DC+, Herbivore, Dissent, und SecretRoom.

Weblinks

• Das DC-Netz: Anonymes Senden und Empfangen (TU Dresden)
• Herbivore
• Dissent
• SecretRoom