Begründung: Ab "Umsetzung" besteht der Artikel nur noch aus wirrem Zeug. Der Teil davor macht nicht wrklich klar, was nun das Problem sei und warum es nun so wichtig sein solle. Es ist doch nun wirklich völlig Brause, welcher Geldsack fetter ist, das sollen die halt unter sich ausmachen. In dieser Form ist das unbrauchbar für den geneigten Leser. --Weissbier 09:17, 26. Sep. 2007 (CEST)
Ich denke, man kann den Wert des Artikels nur als Nicht-Informatiker verkennen. Ich spreche mich für Erhalt des Artikels aus, vielleicht kleine Überarbeitung. Ich unterestelle Ihnen Übereifrigkeit, Herr Weißbier. --C. Grade 15:11, 26. Sep. 2007 (CEST)
- Und ich gebe nicht viel auf die Meinung von Benutzern, welche nicht mal Quellen angeben können. Weissbier 15:38, 26. Sep. 2007 (CEST)
Literaturhinweis: Formale_Sprache. Ich hoffe, Sie wissen zumindest, warum Sie wahrnimmt, wie man Sie wahrnimmt. --C. Grade 09:14, 27. Sep. 2007 (CEST)
Das Millionärsproblem wurde 1982 vom taiwanischen Informatik Professor Andrew Yao formuliert. Das Problem legte den Grundstein zur Multiparty Computation, welche noch heute ein zentrales Forschungsgebiet der Kryptologie darstellt.
Formulierungen
Eine mögliche Formulierung ist:
- Zwei Millionäre treffen sich und wollen wissen, wer von beiden reicher ist, ohne ihr Vermögen offenzulegen.
Eine alternative Variante des Millionärsproblems wurde am TIK formuliert:
- Yao, eine Informatikerin, hat zwei Verehrer. Sie möchte wissen, wer von den beiden mehr Geld verdient. Jedoch will keiner der beiden sein Gehalt offenbaren. Wie kann sie dennoch die gewünschte Auskunft bekommen?
Anwendung
Yaos Millionärsproblem ist ein Problem der Informatik, genauer der Kryptologie. Tatsächlich geht es hierbei nicht um das Vermögen von Millionären, sondern um den Abgleich bzw. den Vergleich von Daten zwischen Systemen ohne die Daten der jeweiligen Systeme offenzulegen.
Dies kann zum Beispiel notwendig sein, wenn keine vertrauenswürdige Gegenstelle oder Verbindung garantiert werden kann.
Algorithmische Lösung
Es wird vereinfachend angenommen, dass die Vermögen oder Gehälter Elemente einer bekannten endlichen Menge sind. Yao zeigte, dass sich das Problem dann ohne Trusted Third Party lösen lässt. Er schlug dazu folgendes Protokoll vor:
Vorbedingungen
Alice habe das Vermögen A und Bob das Vermögen B. Es sei bekannt, dass die beiden Vermögen A und B Elemente der Menge {1, …, 10} sind (zum Beispiel in Millionen Dollar). Zudem besitze Alice das RSA-Schlüsselpaar (kprivate, kpublic). Festgelegt sei auch eine Konstante N, die eine bestimmte Zahlenmenge festlegt, zum Beispiel 0 bis 255 für N = 8 Bit.
Algorithmus
- Bob wählt eine zufällige natürliche Zahl X der Länge N Bit.
- Bob berechnet C = kpublic{X} (die RSA-Verschlüsselung von X mittels public key).
- Bob übermittelt an Alice C−B+1.
- Alice berechnet Y1, …, Y10 mit Yi = kprivate{C−B+i}.
- Alice wählt eine zufällige Primzahl P der Länge (N/2) Bit, so dass |Zi − Zj| ≥ 2 für alle Paare aus der Folge Z1, …, Z10 mit Zi = Yi mod P.
- Alice sendet Z1, …, ZA, ZA+1+1, …, Z10+1 und P an Bob.
- Wenn der B-te Eintrag aus dieser Liste gleich X mod P ist, dann ist A ≥ B, andernfalls ist A < B.
- Bob informiert Alice über sein Resultat.
Literatur
- Andrew C.-C. Yao: Protocols for secure computation. In: Proc. 23rd IEEE Symposium on Foundations of Computer Science (FOCS). 1982, S. 160–164. pdf; 120k