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?

Es legte den Grundstein zur sicheren Mehrparteienberechnung, 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:

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. Jedes Public-Key Kryptosystem ist dafür geeignet.

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+1$.
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\}$. Außerdem muss $Z_{i}\leq p-1$ für alle $i$ sein.
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.