Yaos Millionärsproblem

Das Millionärsproblem wurde 1982 von dem taiwanischen Informatiker Andrew Yao formuliert:

Zwei Millionäre möchten wissen, wer reicher ist. Jedoch wollen sie nicht unbeabsichtigt irgendeine weitere Information über ihren gegenseitigen Reichtum herausfinden. Wie können sie ein solches Gespräch führen? ^[1]

Es legte den Grundstein zur Multiparty Computation, welche noch heute ein zentrales Forschungsgebiet der Kryptologie darstellt. Bei dem Problem geht es abstrakt darum, den Abgleich bzw. den Vergleich von Daten zwischen Systemen zu erledigen, 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 Elemente einer bekannten endlichen Menge sind. Yao zeigte, dass sich das Problem dann ohne Trusted Third Party lösen lässt, die zu schützenden Daten werden also auch keiner weiteren Person bekannt. Er schlug dazu folgendes Protokoll vor:^[1]

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). Es sei k eine bijektive Falltürfunktion auf den Zahlen der Länge N Bit, deren privaten Schlüssel Alice besitzt, das heißt, nur Alice kann die Umkehrfunktion k⁻¹ effizient berechnen.

Dann ermöglicht der folgende Algorithmus, zu ermitteln, wer von den beiden reicher ist, ohne das genaue Vermögen preiszugeben.

Algorithmus

1. Bob wählt eine zufällige Zahl X der Länge N Bit und übermittelt an Alice k(X) − B.
2. Alice berechnet $Y_1, \ldots, Y_{10}$ mit Y_i = k ^{− 1}(k(X) − B + i) für $i \in \{ 1,2,\dots , 10 \}$.
3. Alice wählt eine zufällige Primzahl P der Länge (N/2) Bit, so dass $|Z_i - Z_j| \geq 2$ für alle Paare aus der Folge $Z_1, \ldots, Z_{10}$ mit $Z_i = Y_i \,\bmod\, P$ und $i,j \in \{ 1,2,\dots , 10 \}$.
4. Alice sendet $Z_1, \ldots, Z_A, Z_{A+1}+1, \ldots, Z_{10}+1$ und P an Bob.
5. Wenn der B-te Eintrag aus dieser Liste gleich X mod P ist, dann ist A ≥ B, andernfalls ist A < B.
6. Bob informiert Alice über sein Resultat.

Einzelnachweise

1. ↑ ^{a b} Andrew C. Yao: Protocols for Secure Computations (extended abstract). (PDF-Datei, 116 kB) In: Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Chicago 1982, S. 160–164. (englisch)