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

27

(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?kjpi

Gil Kalai
quelle
1
Dürfen die Agenten .. ? p0pk
Mike Samuel

Antworten:

19

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.kk1k

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.

Joe Fitzsimons
quelle
2
Mein Problem bei diesem Ansatz ist, dass, wenn Sie viele externe Beobachter von Fairness überzeugen möchten, jeder von ihnen ein wenig Engagement zeigen muss und Sie sicher sein müssen, dass jeder von ihnen den Beweis für sein Engagement vorlegt. Sie können nicht einfach das Bit eines Beobachters ignorieren, der seinen Beweis nicht enthüllt, da dann der letzte Beobachter das Lotterieergebnis manipulieren könnte, indem er entscheidet, ob er seinen Beweis enthüllt oder nicht.
Zsbán Ambrus,
1
@ user8067: Ich glaube nicht, dass es ohne Interaktion oder Vertrauen möglich ist, dass mindestens eine Partei ehrlich ist. Der Grund, warum ich das sage, ist, dass, wenn die anfängliche Zufälligkeit tatsächlich durch eine Verschwörung aller an diesem Punkt Beteiligten vorbestimmt ist, der gesamte Prozess deterministisch und nicht zufällig ist. Das Problem erfordert jedoch, dass der Prozess zufällig ist. Dies scheint also das Beste zu sein, was Sie tun können.
Joe Fitzsimons
2
Ich bin nicht überzeugt, dass das möglich ist.
Joe Fitzsimons
2
@ RickyDemer: Die Frage enthält nicht genügend Informationen, um zu sagen, welches Gegenmodell hier anwendbar ist. Wenn Gil uns genau sagt, wofür es ist, ist es einfacher zu beweisen, ob ein bestimmtes Schema seinen Anforderungen entspricht oder nicht. Ich bezweifle jedoch, dass Gil mehr als in der Lage ist zu prüfen, ob unsere Antworten seinen Bedürfnissen entsprechen.
Joe Fitzsimons
2
@ RickyDemer: Es ist mir überhaupt nicht klar, was das offensichtliche Modell für diesen Fall ist. Dies hängt stark vom Setup ab, und es ist nicht klar, welche Standardannahmen verwendet werden sollten. Es ist ein bisschen zu viel, um abzulehnen und sich so zu verhalten, als ob sowohl meine Antwort als auch die von Lev falsch sind. Sie enthalten nicht ausdrücklich den Vorbehalt, auf den Adam in seiner Antwort hingewiesen hat. Beachten Sie, dass ich meine Antwort nicht bearbeite, da es ohne weitere Informationen von Gil keinen Sinn macht, über das Modell des Gegners zu raten Bit Commitment muss nicht maliable sein).
Joe Fitzsimons
15

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.
Adam Smith
quelle
1
"Eine gemeinsame zufällige Zeichenfolge, die für alle Parteien sichtbar, aber von keiner von ihnen kontrollierbar ist", ist genau das, was wir generieren möchten.
Zsbán Ambrus,
1
und nachdem man dieses Problem einmal irgendwie gelöst hat, kann man universell zusammensetzbar lösen (beliebig oft).
Ich denke, das UC-Commitment ist bekannt für die Einrichtung eines registrierten öffentlichen Schlüssels (eine stärkere Annahme als bei PKI) und für die Einrichtung mehrerer Zeichenfolgen (eine schwächere Annahme als bei gewöhnlichen Zufallszeichenfolgen).
2
Willkommen auf der Seite, Adam!
Gil Kalai
11

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


pj

{0,1}bb

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.

Lev Reyzin
quelle
Sorry Lev, ich habe gerade deine Antwort bemerkt. Als ich anfing, eine Antwort zu schreiben, gab es hier nichts, aber wir scheinen uns beide sehr ähnliche Antworten ausgedacht zu haben.
Joe Fitzsimons
Keine Bange! Dann sind wir wohl auf dem richtigen Weg.
Lev Reyzin
Ja, tatsächlich denke ich, dass es im Zusammenhang mit dem Umwerfen von Münzen eine Menge Artikel darüber gibt, aber ich kenne diese Literatur nicht gut genug, um darauf eine richtige Antwort zu geben.
Joe Fitzsimons
7
Die früheste mir bekannte Referenz ist: M. Blum. Münze, die durch Telefon leicht schlägt. CRYPTO 1981: 11-15. Kann heruntergeladen werden unter dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/…
Ryan Williams
4
Es gibt einen Standardangriff, wenn Sie Standard-Bit-Commitment-Schemata (z. B. Hashing) verwenden. Lassen Sie uns den Fall mit zwei Parteien betrachten, Alice und Bob, wo Alice zuerst geht. Nachdem Alice ihr Engagement gesendet hat, kann Bob es kopieren. Nachdem Alice ihr Engagement eröffnet hat, kann Bob jetzt dasselbe eröffnen. Jetzt sind ihre Zufallsvektoren gleich, also xor to zero - Bob konnte den Endwert auf Null setzen, ein Widerspruch zur Forderung nach Fairness.
DW
-3

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:

Bildbeschreibung hier eingeben

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

Marek Rogalski
quelle
1
Dies ist bereits in Joes Antwort vermerkt.
Kaveh
1
Die grafische Darstellung ist sehr schön!
Gil Kalai
3
Die Grafiken sind sehr hübsch, aber Ihre Antwort enthält nichts, was nicht in den vorhandenen Antworten enthalten ist.
David Richerby