Null-Wissen-Beweise

Null-Wissen-Beweise (bzw. Zero Knowledge Proofs) sind eine faszinierende mathematische Technik, die es ermöglicht, Informationen auszutauschen, ohne dabei die Inhalte selbst preiszugeben. Der Name mag zunächst kompliziert klingen, es lohnt sich allerdings, sich nicht davon abschrecken zu lassen!

In diesem Beitrag werden wir uns mit der Grundidee hinter dem Null-Wissen-Beweis beschäftigen, indem wir zwei spannende Beispiele betrachten, die zeigen, wie dieses Konzept angewendet werden kann.

Beispiel 1: Wo ist Walter?

“Wo ist Walter?” ist eine beliebte Buchreihe mit Wimmelbildern des britischen Illustrators Martin Handford.

Das Konzept besteht darin, auf überfüllten Illustrationen nach einer Figur namens Walter zu suchen, der sich inmitten einer Vielzahl anderer Charaktere und Szenen versteckt.

Typischerweise erkennt man Walter an seinem charakteristischen, rot-weiß gestreiften Pulli.

Situation:

Stell dir vor, du spielst mit einer Freundin “Wo ist Walter” und du entdeckst Walter vor ihr.

Allerdings glaubt dir deine Freundin nicht, dass du ihn so schnell gefunden hast. Daher musst du sie nun davon überzeugen.

Weil deine Freundin Walter aber selbst auch noch finden möchte, kannst du ihr nicht einfach zeigen, wo er sich befindet.

Wie kannst du deiner Freundin beweisen, dass du Walter bereits gefunden hast, ohne deiner Freundin zu verraten, wo er sich befindet?

Beispiel 2: Die rote Karte

Wir betrachten ein gewöhnliches Kartendeck aus 52 Karten. Darin enthalten sind jeweils 13 Karten der Farben ♥,♦,♣,♠.

Du ziehst verdeckt eine Karte aus dem Stapel und siehst sie dir an.

Es ist die Karte ♥8.

Du möchtest nun jemandem beweisen, dass diese gezogene Karte rot ist, ohne dabei zu verraten, dass es sich um eine ♥-Karte handelt oder dass ihr Wert 8 ist.

Wie kannst du beweisen, dass die gezogene Karte rot ist, ohne dabei weitere Informationen über sie preizugeben?