Eine Lotterie, von der Sie überzeugt sein können, dass sie fair ist

(Entschuldigung, wenn dies bekannt ist.) Ich möchte einem von Agenten einen Gegenstand geben , damit der Agent den Gegenstand mit der Wahrscheinlichkeit erhält . Gibt es ein kryptografisches (oder ein anderes) Tool, mit dem jeder Agent (und sogar jeder Beobachter) davon überzeugt werden kann, dass die Zufallsziehung tatsächlich fair war?$k$$j$$p_i$

Wenn ich das Problem richtig verstehe, kommt es mir so vor, als würde die Öffentlichkeit eine seitige Münze werfen. Es scheint viele Möglichkeiten zu geben, dies zu tun, wenn Sie etwas Engagement annehmen. Ein Beispiel wäre, dass jede Partei eine zufällige Ganzzahl zwischen 0 und generiert , indem sie eine Bit-Festschreibung verwendet, um öffentlich eine Festschreibung für diese Bit-Zeichenfolge vorzunehmen. Sobald sich jeder Agent verpflichtet hat, enthüllen sie alle öffentlich ihre geheime Ganzzahl. Der Gewinneragent ist dann derjenige, der durch die Summe der ganzen Zahlen modulo indiziert ist . Wenn auch nur ein Agent ehrlich ist, muss der Flip zufällig sein.$k$$k-1$$k$

Ein Problem dabei ist natürlich, dass es etwas Engagement erfordert. Informationstheoretische Schemata für das Bit-Commitment sind sowohl für das klassische als auch für das Quanten-Computing unmöglich (obwohl Adrian Kent kürzlich ein Schema vorgeschlagen hat, das die Relativität ausnutzt). Ein sicheres Bit-Commitment kann jedoch mit Rechenannahmen erreicht werden.

Wie andere Benutzer bereits angedeutet haben, handelt es sich hierbei um ein gut untersuchtes Problem in der Kryptografie. Es wird "Münzwurf" genannt und ist ein Sonderfall der Mehrparteienberechnung.

Welches Protokoll der Job tatsächlich ausführt, hängt ziemlich stark vom Kontext ab.

• In der "Standalone" -Einstellung wird das Protokoll isoliert ausgeführt, ohne dass die Spieler gleichzeitig an anderen Protokollen (oder in der Tat an Interaktionen mit der Außenwelt) beteiligt sind. In Oded Goldreichs Lehrbuch "Foundations of Cryptography" (Band 2, glaube ich) wird dies wunderbar gründlich behandelt.

Nur um eine Vorstellung davon zu geben, wie subtil es ist, ist das von einem anderen Responder vorgeschlagene Protokoll "Jeder verpflichtet sich zu Zufallswerten" unsicher, wenn das von Ihnen verwendete Verpflichtungsschema formbar ist. Nicht formulierbare Verpflichtungsschemata bieten Ihnen zwar ein sicheres Protokoll, sind jedoch etwas kompliziert zu entwerfen.

• In Einstellungen, in denen Teilnehmer an anderen gleichzeitigen Protokollen beteiligt sind, möchten Sie ein Protokoll, das zusammengestellt werden kann . Es gibt verschiedene Vorstellungen von Zusammensetzbarkeit, aber die stärkste, die als universelle Zusammensetzbarkeit bezeichnet wird , erfordert einige zusätzliche Einrichtungsannahmen (z. B. eine PKI oder eine gemeinsame Zufallszeichenfolge, die für alle Beteiligten sichtbar ist, aber von keiner von ihnen gesteuert werden kann). Ich kenne leider keine zugängliche Behandlung dieses Themas. Ein Blick auf ein kürzlich veröffentlichtes Papier über universelle Kompositionsfähigkeit oder nicht formbares Engagement wäre jedoch ein guter Anfang.

Hinweis: Bitte lesen Sie die Kommentare unten. Dieses Protokoll scheint Probleme zu haben.

$p_j$

$\{0,1\}^b$$b$

Jeder Agent kann sicher sein, dass die gewählte Zufallszahl gleichmäßig zufällig gewählt wurde, indem er seinen eigenen Vektor gleichmäßig zufällig auswählt. Damit ein Beobachter überzeugt ist, muss er darauf vertrauen, dass mindestens ein Agent das Protokoll befolgt hat, aber wenn dies nicht der Fall ist, wollte wohl niemand wirklich eine faire Lotterie.

Passive Beobachter können nicht überprüfen, ob die Zeichnung nicht inszeniert wurde. Eingaben in den Pseudozufallsprozess können ausgewählt werden, um das gewünschte Ergebnis zu erzielen.

Wenn der Beobachter jedoch eine Zufallszahl eingeben kann, von der er weiß, dass sie zufällig ist, UND sicherstellen kann, dass andere Agenten ihre Eingaben danach nicht ändern (da sie seinen Effekt mit ihren Eingaben kompensieren könnten), kann er sicher sein, dass das Ergebnis tatsächlich zufällig war .

Dies erfordert ein Verpflichtungsschema, von dem wir kein mathematisch sicheres kennen, das jedoch in der Praxis mit sicherem Hash (wie SHA3) realisiert werden kann.

Betrachten Sie dieses Beispiel:

Ich habe eine Beispielimplementierung gemacht. Sie können es hier live sehen: https://mrogalski.eu/cl/ oder Quellen auf GitHub überprüfen .