Arbeitsgruppe Theoretische Informatik

Protokolle für den Unterricht

Eine Reihe von kryptographischen Protokollen, genauer: Sicherheitsprotokollen, sind geeignet, im Schulunterricht behandelt zu werden. Derartige Protokolle sind hier zu finden:

Handydiebstahl

Problemstellung: In einer Klasse befindet sich möglicherweise ein Handydieb. Ob es tatsächlich eine Handydieb gibt, soll ermittelt werden, ohne dass ggf. die Identität des Diebes aufgedeckt wird.

Randbedingungen: Die Schüler sitzen mit der Lehrerin in einem Kreis. Die Lehrerin sendet an den links von ihr sitzenden Schüler zunächst eine Nachricht, danach liest jeder Schüler, der (von seinem rechten Nachbar) eine Nachricht erhält, diese Nachricht und sendet dann eine Nachricht an seinen linken Nachbarn. Erhält (letztlich) die Lehrerin eine Nachricht (von ihrem rechten Nachbarn), dann liest sie diese und gibt das Ergebnis bekannt.

Korrektheit: Die Lehrerin verkündet das richtige Ergebnis nach Beendigung des Protokolls (wenn sich alle an das Protokoll halten).

Sicherheit: Befindet sich in der Klasse ein Dieb, so hält jeder Schüler, außer dem Dieb, jeden anderen Schüler für den möglichen Täter.

Protokoll für die Lehrerin, 1. Teil

  • Wähle zufällig ein Bit und sende dies an deinen linken Nachbarn.

Protokoll für eine Schüler

  • Empfange ein Bit.
  • Wenn du der Dieb bist, negiere das Bit und sende das resultierende Bit an deinen linken Nachbarn.
  • Wenn du nicht der Dieb bist, sende das Bit an deinen linken Nachbarn

Protokoll für die Lehrerin, 2. Teil

  • Empfange ein Bit.
  • Wenn dieses Bit mit dem von dir ursprünglich gewählten Bit übereinstimmt, gib „Es ist kein Dieb unter euch.“ aus, sonst gib „Es ist ein Dieb unter euch.“ aus

Verdeckte Auktion

Problemstellung: Alice möchte gegenüber Bob ein verdecktes Gebot für ein Smartphone abgeben.

Randbedingungen: Es gibt eine Vertrauensfrau Viola, die im Vorfeld agieren kann. Das eigentliche Protokoll sol in zwei Phasen ablaufen: Am Ende der ersten Phase hat Alice ein verdecktes Gebot abgegeben; im Rahmen der zweiten Phase wird dieses Gebot aufgedeckt und von Bob überprüft, so dass Bob ggf. zu der Erkenntnis kommt, dass Alice beim Aufdecken zu täuschen versucht. Es wird angenommen, dass Alice kein Gebot abgibt, das höher als 1000 ist.

Korrektheit/Sicherheit: 1) Nach Ablauf der ersten Phase weiß Bob über Alices Gebot nur, dass es in dem angegebenen Bereich liegt (Gebotsgeheimhaltung). 2) Wenn Alice in der zweiten Phase einen anderen Wert als ihr Gebot aufdeckt, dann wird dieser Täuschungsversuch fast immer entdeckt (Gebotsbindung).

Protokoll für Viola:

  • Wähle eine Gerade (lineare Abbildung) g, die zu keiner der Achsen parallel ist, und sende sie an Alice.
  • Wähle einen Punkt P auf der Geraden mit einem x-Wert größer als 1000 und sende ihn an Bob.

Protokoll für Alice, 1. Teil

  • Empfange eine Gerade.
  • Wähle ein Gebot x zwischen 0 und 1000.
  • Bestimme den Wert y der linearen Abbildung an der Stelle x.
  • Sende y an Bob.

Protokoll für Alice, 2. Teil

  • Empfange die Nachricht „Decke bitte auf.“
  • Sende x und die Gerade g an Bob.

Protokoll für Bob, 1. Teil

  • Empfange einen Punkt P.
  • Empfange einen Betrag y.
  • Sende die Nachricht „Decke bitte auf.“ an Alice.

Protokoll für Bob, 2. Teil

  • Empfange x’ und eine lineare Abbildung g’.
  • Überprüfe, ob der empfangene Punkt und P auf der empfangenen Geraden g’ liegen.
  • Wenn ja, gib das Gebot x’ aus.

Tatsächliche Sicherheitsgarantien: 1) Bob weiß nach Beendigung seines zweiten Protokollteils nichts über Alices Gebot, außer dass es zwischen 0 und 1000 liegt. 2) Verhält sich Alice gemäß des Protokolls, signalisiert Bob keinen Täuschungsversuch. 3) Weicht Alice vom Protokoll im zweiten Teil ab, so entdeckt Bob diese Täuschung nur dann nicht, wenn Alice eine richtige Annahme über den x-Wert von P macht.

Bemerkung: Will man unter 3) konkrete Aussagen über die W’keit machen, mit der Bob die Täuschung aufdeckt, muss man annehmen, dass die Gerade und der Punkt nach einer W’Verteilung gewählt wurden. Z.B. kann man annehmen, dass eine große Primzahl p vorgegeben ist und in dem entsprechenden Restklassenring gerechnet wird. Dann  wird ein Täuschungsversuch mit W’keit 1 – 1/(p – 1001) erkannt.