Home | Sitemap | Kontakt | english  | Impressum | KIT
Informatik mit Profil.
Facebook Google+ Twitter YouTube
KIT on on iTunes U

Gedankenspiele mit Sudoku

Gedankenspiele mit Sudoku
Autor:

Gunnar Hartung, Julia Braun, Sebastian Schäfer

Links:
Datum: 11.02.2014

Wie man ein Geheimnis verrät, ohne es preiszugeben

Eine der Aufgaben der Kryptographie ist es, Geheimnisse möglichst gut zu schützen. Texte beispielsweise können ihre Geheimnisse durch eine Verschlüsselung für Fremde unlesbar transportieren. Die moderne Kryptographie befasst sich jedoch auch mit der Frage, wie man beweisen kann, ein Geheimnis zu kennen, ohne dessen Inhalt zu verraten. Als Beispiel sei hier die Wahlkontrolle genannt: Wie kann geprüft werden, ob eine Person an einer Wahl eine gültige Stimme abgegeben hat, ohne deren Votum offenzulegen? Obwohl dieses Ziel paradox klingt, kann es erreicht werden. Zur Veranschaulichung des Prinzips wird die Vorgehensweise am Beispiel Sudoku durchgespielt:

Man kann beweisen, die Lösung eines Sudoku-Rätsels zu kennen, ohne dabei auch nur ein Feld zu verraten. Sudoku ist ein populäres Logik-Spiel, das normalerweise von einer Einzelperson mit Stift und Papier gespielt wird. Ziel ist es, die Ziffern von eins bis neun so in einem quadratischen Spielfeld mit neun Zeilen und neun Spalten anzuordnen, dass in jeder Zeile, jeder Spalte und in jedem Drei-Mal-Drei-Block jede dieser Ziffern genau einmal vorkommt. Dabei sind einige Felder bereits mit Ziffern ausgefüllt.

Um zu beweisen, dass man die Lösung kennt, legt man auf jedes leere Feld drei zugedeckte Karten mit der Ziffer, die in der korrekten Lösung in dieses Feld gehört. Auf die vorgegebenen, bereits ausgefüllten Felder kommen jeweils drei aufgedeckte Karten mit der entsprechenden Ziffer.

Nun nimmt man von jedem Feld in der ersten Zeile eine zufällige Karte, dreht die aufgedeckt liegenden um, sodass alle Karten verdeckt sind, und legt diese neun Karten gemeinsam auf einen Stapel. Dieser Stapel wird gemischt und dann komplett aufgedeckt. Jetzt ist auf einen Blick ersichtlich, ob der Stapel alle Ziffern von eins bis neun enthält. Ist das der Fall, ist nachgewiesen, dass alle Ziffern korrekt angeordnet wurden, ohne zu erfahren, welche Ziffer auf welchem Feld lag. Dieser Vorgang wird bei allen übrigen Zeilen und allen Spalten wiederholt. Anschließend liegt auf jedem Feld nur noch jeweils eine Ziffernkarte. Zuletzt wird das Stapel-Misch-Verfahren auch bei jedem der Drei-Mal-Drei-Blöcke durchgeführt.

Hat jeder der insgesamt 27 Kartenstapel jeweils einmal jede Ziffer von eins bis neun enthalten, ist der Beweis erbracht, dass alle Felder des Neun-Mal-Neun-Sudokus richtig belegt waren. Welche Zahl auf welchem Feld lag, bleibt dabei dennoch geheim. Das scheinbar Unmögliche ist vollbracht: Es ist bewiesen, dass das Rätsel richtig gelöst wurde, ohne die Lösung aufzudecken.

Dieses Verfahren mag wie eine Spielerei anmuten. Tatsächlich jedoch finden ähnliche Techniken Anwendung in der kryptographischen Forschung. Dieser Linie folgend ist es denkbar, bei einem elektronischen Wahlverfahren nachzuweisen, dass genau ein Kreuz gesetzt wurde, ohne dabei zu enttarnen, bei welchem Kandidaten dieses Kreuz gesetzt wurde. Auf diese Art kann die Korrektheit eines Wahlvorgangs mit kryptographischen Methoden geprüft werden, ohne das Wahlgeheimnis zu lüften.

Weitere Informationen und Photos zu dem obigen Verfahren gibt es hier.

Auf dem Kryptologikum vom 12. bis zum 14. Februar 2014 im ZKM in Karlsruhe ausgestellt wird, kann man dieses Verfahren auch selbst ausprobieren.