Zero-Knowledge-Protokolle

Authentisierung einer Person durch Passwort Passwort einmal genannt: nicht mehr geheim Verfahren zur Authentisierung kann Passwort nur einmal schützen Wird Passwort offen gelegt in Zukunft missbrauchbar Mögliche Abhilfen Verwendung von Einmalpasswörtern (z.B. Transaktionsnummern im Bankverkehr) andere Methoden,  belege Kenntnis eines Passworts ohne dieses offen zu legen  (d.h. keine Information über Passwort übermitteln Zero-Knowledge-Protokolle

Beispiel  geheimes Lösungsverfahren für spezielles Problem z.B. Lösung von Gleichungen höheren Grads Lösung kubischer Gleichungen von Nicolò Tartaglia (1456-1526) entwickelt  zunächst geheim gehalten Nachweis der Kenntnis eines Lösungsverfahrens konnte er jederzeit erbringen, indem er entsprechende Aufgabe in angemessener Zeit löste.

	Verfahren Fiat und Shamir  bestimmte Zahl s als Geheimnis Veröffentlicht wird das Quadrat modulo m schwieriges, rechenzeitaufwendiges Problem zu einer Zahl die Quadratwurzel (mod m) zu finden, wenn m=p*q das Produkt zweier großer Primzahlen ist.
	Weise Kenntnis der Zahl s nach, ohne diese offen zu legen,
	folgendes Protokoll leistet diese

Alf kenne das Geheimnis s und will Bert beweisen, dass er s kennt, ohne Bert s zu nennen.

Alf wählt ein Modul m=p*q und veröffentlicht m und v=s2 mod m.

Um Bert von der Kenntnis von s zu überzeugen, geht Alf folgendermaßen vor:

Alf wählt eine zufällige Zahl r. Alf sendet deren Quadrat  x=r2 mod m an Bert. Bert darf jetzt genau eine der Zahlen r oder y=s/r mod m von Alf anfordern Fordert Bert r, so kann Bert prüfen, ob r eine Quadratwurzel von x=r2 mod m ist. Fordert Bert y, so kann Bert prüfen, ob y2*x=s2/r2*r2=v das Quadrat des Geheimnisses ist. Dieser Vorgang wird solange wiederholt, bis Bert mit ausreichender Wahrscheinlichkeit sicher ist, dass Alf das Geheimnis s kennt.

	Alf kennt das Geheimnis nicht entweder zu v und beliebigem y einfach x=v/y2 berechnen,  aus x=r2 nicht einfach r bestimmen oder  Alf kann zu beliebigem r einfach x=r2 bestimmen aber aus x nicht einfach y bestimmen Bert überprüft  kennt Alf wirklich Quadratwurzel aus x ist y2*x=v nicht gleichzeitig y und r offen legen s einfach aus y=s/r berechnbar nur eine der beiden Zahlen r oder y fälschbar Bert überzeugt sich durch zufällige Auswahl von Richtigkeit einer dieser beiden Zahlen  Wegen zufälliger Wahl ist Bert nur zu 50% überzeugt Überprüfung wird mehrfach wiederholt n Schritten geht Bert davon aus Alf betrügt nur mit Wahrscheinlichkeit 0,5n nach 10 Schritten zu 0,1% nach 20 Schritten zu 0,0001% usw.  Bert bestimmt Sicherheit selbst
	m=p*q, Primfaktoren p und q bekannt effizient die Quadratwurzel s berechenbar v bspw. aus Identifikation hergeleitet Name,  Kartennummer  freie Zusatzzahl usw.  Quadratwurzel von v bestimmbar quadratischer Rest v bestimmbar Chipkarten vor Fälschungen schützbar
	Sicherheit des Verfahrens beruht auf Schwierigkeit große Zahlen zu faktorisieren  zu m=p*q die Primfaktoren p und q finden