Weisen Sie n Agenten zufällig n Elemente zu, sodass jeder Agent nur sein eigenes Element kennt

Question

Problem

Ich arbeite an einer App, die das Mischen und Verteilen von Spielkarten an Spieler beinhaltet.Als Herausforderung habe ich versucht, dieses Problem auf eine Weise zu lösen, die keinen vertrauenswürdigen Vermittler erfordert.

Mit anderen Worten besteht die Aufgabe darin, einen verteilten Algorithmus zu finden

• eindeutig zuordnet $n$ Agentennummern $1..n$
• ermöglicht es jedem Agenten, nichts über den Auftrag zu erfahren, außer seinem eigenen
• Beim Aufdecken der Aufgabe können andere Spieler die Aufgabe überprüfen

Wir gehen auch davon aus, dass es für jeden Agenten von Vorteil ist, den Auftrag anderer zu kennen, und dass es einen Nachteil darstellt, den eigenen Auftrag vorzeitig preiszugeben.Es wird auch davon ausgegangen, dass Agenten in der Lage sind, auf eine Weise miteinander zu kommunizieren, die allen anderen Agenten verborgen bleibt.

Teillösung

Die Lösung, die ich gefunden habe, funktioniert nur unter der Annahme, dass die Gegner nicht zusammenarbeiten.

Die Idee ist, eine Reihe von zu erstellen $n$ Nonces und weisen Sie jedem Agenten genau eine Nonce zu.Der Satz wird dann in einer vereinbarten Reihenfolge von Agent zu Agent weitergegeben, verborgen vor allen anderen, bis jeder Agent den Satz genau einmal erhalten hat.Jedes Mal, wenn ein Agent den Satz erhält, tauscht er seine Nonce gegen eine neue aus, merkt sich die neue Nonce und bestätigt den anderen den Empfang des Satzes.Dieser gesamte Vorgang wird zweimal durchgeführt. Zu diesem Zeitpunkt haben alle Agenten den Satz mindestens einmal erhalten, nachdem alle anderen Agenten ihre Nonces ausgetauscht haben, was es unmöglich macht, die Nonces zu erkennen und sie daher den anderen Agenten zuzuordnen.

Wenn der letzte Agent das Set zum zweiten Mal erhält, teilt er es mit allen und alle Agenten bestätigen den anderen, dass ihre Nonce im Set enthalten ist.Die Agenten weisen dann jeder Nonce im Satz basierend auf einem vereinbarten Zufallsstartwert eine Nummer zu und geben uns so die erforderliche eindeutige Zuweisung.

Um eine Eigentumsüberprüfung zu ermöglichen, geben Agenten anstelle der Nonces den Hashwert ihrer Nonce in den Satz ein und geben die tatsächliche Nonce nur dann preis, wenn eine Überprüfung erforderlich ist.

---

Das Problem bei dieser Lösung besteht darin, dass, wenn Gegner zusammenarbeiten dürfen, sie jedes Mal, wenn sie den Satz erhalten, ihre Versionen vergleichen, Änderungen identifizieren und möglicherweise ableiten können, welche Nonce zu anderen Agenten gehört, sodass sie wissen, welche Nummer ihnen zugewiesen wurde .

Alle Ideen sind willkommen!

Answer 1

Dieses Problem ist Teil einer Reihe von Problemen, die als bekannt sind Mentales Poker.

Es gibt ein ausgezeichneter und kleiner Artikel von Shamir, Rivest und Adleman, die einen praktischen Weg zur Implementierung eines solchen Algorithmus beschreiben.

Die Zusammenfassung ist Gold:

Können zwei potenziell unehrliche Spieler ein faires Pokerspiel spielen, ohne Karten zu verwenden (z. B.über ein Telefon)?

Dieses Papier gibt folgende Antworten:

1. NEIN.(Strenger mathematischer Beweis geliefert.)
2. Ja. (Korrektes und vollständiges Protokoll gegeben.)

Grundsätzlich ist es aus informationstheoretischer Sicht unmöglich, ein solches Spiel ohne einen vertrauenswürdigen Dritten zu spielen, aber es ist machbar, ein Protokoll zu entwerfen, das bekannte, schwer umkehrbare kryptografische Funktionen verwendet.

---

Der Algorithmus funktioniert wie folgt:

Angenommen, Sie haben es getan $n$ Nonces (Zahlen aus $1$ Zu $n$).Jeder Teilnehmer des Protokolls hat Zugriff auf geheime Funktionen $e_i$ Und $d_i$ die zum Verschlüsseln und Entschlüsseln von Daten verwendet werden.Diese Funktionen sollten einige Eigenschaften erfüllen, die wir später analysieren werden.

Der erste Teilnehmer erhält den vollständigen Nonces-Satz.Es verschlüsselt jede Nonce mit seiner geheimen Funktion $e_1$, mischt sie zufällig und gibt die resultierenden Daten an den zweiten Teilnehmer weiter.

Der zweite Teilnehmer wird dasselbe tun, aber in diesem Fall hat er keine Nonces, sondern eine zufällige Permutation der verschlüsselten Nonces.Außerdem wird jedes Element mit seiner eigenen geheimen Funktion verschlüsselt $e_2$ und mischen Sie die Daten erneut.

Dann dritter Teilnehmer usw., bis alle Teilnehmer die Daten mit ihrer geheimen Funktion gemischt und verschlüsselt haben.

Insgesamt ist der Einrichtungsprozess wie folgt:

data = [1..n]
for i in [1..n]:
    data = [e_i(nonce) for nonce in data]
    shuffle(data)

Nach diesem Setup wird jedes Element von data sind die Nonces, die mit allen geheimen Funktionen verschlüsselt sind $e_i$ in einer zufälligen Reihenfolge, die keinem Teilnehmer bekannt ist.

Beachten Sie, dass es zu diesem Zeitpunkt für jeden Teilnehmer unmöglich ist, jede Nonce ohne die Hilfe anderer Teilnehmer abzuleiten.Und es reicht aus, dass einer der Teilnehmer die Daten völlig zufällig mischt, um mögliche Verzerrungen in der resultierenden Reihenfolge zu beseitigen, unabhängig davon, ob ein böswilliger Teilnehmer versucht, die Reihenfolge zu verzerren.

Teilnehmer $i$-th wird die Nonce an Position zugewiesen $i$.Um eine solche Nonce wiederherzustellen, Teilnehmer $i$ fragt jeder andere Teilnehmer $j eq i$ um den Wert mit seiner geheimen Funktion zu entschlüsseln $d_j$ abwechselnd.Am Ende Teilnehmer $i$ wird seine Nonce nur mit seiner eigenen geheimen Funktion verschlüsseln $e_i$ damit es mit wiederhergestellt werden kann $d_i$.

Nonce wiederherstellen $i$:

nonce_i_encrypted = data[i]
for j in [1..n]:
    if j == i:
        continue
    nonce_i_encrypted = d_j(nonce_i_encrypted)

nonce_i = d_i(nonce_i_encrypted)

Am Ende dieses Verfahrens kennt jeder Teilnehmer seine eigene Nonce, aber kein anderer Teilnehmer weiß etwas darüber.

Nachdem Sie diese Werte für Ihr aktuelles Problem verwendet haben, kann ein Spieler behaupten, dass er tatsächlich die Kontrolle über eine solche Nonce hat, indem er entweder die geheimen Funktionen veröffentlicht $e_i$ Und $d_i$, sodass jeder alle Werte lokal berechnen oder den Wert entschlüsseln kann data[i] nach dem ersten Schritt, aber vor dem zweiten Schritt, Veröffentlichen und anschließendes Verwenden dieses Werts als Eingabe im zweiten Schritt, um ihn vollständig zu entschlüsseln.

Die Funktionen $e_i$ Und $d_i$ sollte folgende Eigenschaften haben:

1. $e_i(x)$ ist die verschlüsselte Version einer Nachricht $x$ unter Schlüssel $i$,
2. $d_i(e_i(x)) = x$ für alle Nachrichten $x$ und Schlüssel $i$,
3. $e_i(e_j(x)) = e_j(e_i(x))$ für alle Nachrichten $x$ und Schlüssel $i$ Und $j$,
4. Gegeben $x$ Und $e_i(x)$ Es ist für einen Kryptoanalytiker rechnerisch unmöglich, dies abzuleiten $i$, für alle $x$ Und $i$,
5. Irgendwelche Nachrichten gegeben $x$ Und $y$, ist es rechnerisch unmöglich, Schlüssel zu finden $i$ Und $j$ so dass $e_i(x) = e_j(y)$.

Wie in dem Artikel dargelegt, sind die meisten dieser Annahmen irgendwie üblich, mit Ausnahme von Eigenschaft 3), die angibt, dass die Verschlüsselungsfunktionen kommutieren müssen.

Sie schlagen ein einfaches Verschlüsselungsschema vor, das diese Eigenschaften erfüllt.Nehmen wir an, alle Teilnehmer sind sich auf eine große Primzahl einig $P$ (Es ist in Ordnung, wenn es im Protokoll festgelegt ist).Und jeder Teilnehmer wählt heimlich eine Zufallszahl $k_i$ so dass $gcd(k_i, P - 1) = 1$.Sagen wir $q_i$ ist so wertvoll, dass $k_i \cdot q_i \equiv 1 \mod(P -1)$.Dann Teilnehmer $i$ kann geheime Funktionen verwenden:

$$e_i(x) = x^{k_i} \mod(P)$$ $$d_i(y) = y^{q_i} \mod(P)$$

Einige Vorbehalte zu diesem Algorithmus:Teilnehmer können nicht auf eine Weise betrügen, die ihnen durch Absprachen dabei zugute kommt, etwas über den anderen Kollegen zu erfahren (es sei denn natürlich). $n-1$ (die Teilnehmer kollidieren und es bleibt nur noch eine Nonce übrig.)Allerdings können böswillige Teilnehmer das Protokoll angreifen, indem sie nicht teilnehmen, wodurch der Handelsprozess effektiv blockiert wird, da von jedem Teilnehmer viele Aktionen erforderlich sind, während er die Nonces austeilt.Sie können auch Kauderwelsch produzieren, aber dies kann durch die Erweiterung des Protokolls gemildert werden, um zu erkennen, welcher Teilnehmer der Täter war, und diesen Teilnehmer auf einer höheren Ebene zu bestrafen.

---

Ich habe diesen Algorithmus für ein Pokerspiel implementiert NEAR-Blockchain.Sie können den Code in Rost sehen Hier.Beachten Sie, dass es in einer Blockchain keinen vertrauenswürdigen Dritten gibt, sondern eine vertrauenswürdige Computerumgebung, die alle Teilnehmer als Mechanismus zum Ausführen dieses Protokolls verwenden können.