Loteria, którą możesz przekonać, że jest uczciwa

27

(Przepraszam, jeśli jest to dobrze znane.) Chciałbym podać jakiś przedmiot jednemu z agentów, aby agent otrzymał element z prawdopodobieństwem . Czy istnieje narzędzie kryptograficzne (lub inne), aby każdy agent (a nawet każdy obserwator) był w stanie przekonać się, że losowe losowanie rzeczywiście było uczciwe? $k$ $j$ $p_i$

cr.crypto-security Gil Kalai
źródło

1

Czy agentom wolno znać

...

?

p_{0}

$p_0$

p_{k}

$p_k$

Mike Samuel

Widziałeś to? ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4232861

dspyz

19

Jeśli dobrze rozumiem problem, wydaje się, że sprowadza się to do publicznego rzutu monetą side. Wydaje się, że istnieje wiele sposobów na zrobienie tego, jeśli podejmiesz trochę zaangażowania. Jednym przykładem może być wygenerowanie przez każdą ze stron losowej liczby całkowitej od 0 do , przy użyciu zobowiązania do bitu do publicznego zatwierdzenia tego ciągu bitów. Następnie, gdy każdy agent się zgodzi, wszyscy publicznie ujawniają swoją tajną liczbę całkowitą. Zwycięski agent jest następnie indeksowany przez sumę liczb całkowitych modulo . Jeśli choć jeden agent jest uczciwy, flip musi być losowy. $k$ $k-1$ $k$

Oczywiście jednym z problemów jest to, że wymaga nieco zaangażowania. Teoretyczne schematy informacji dotyczące zaangażowania bitowego są niemożliwe zarówno w przypadku obliczeń klasycznych, jak i kwantowych (chociaż Adrian Kent niedawno zaproponował schemat wykorzystujący teorię względności). Jednak bezpieczne zaangażowanie bitów można osiągnąć przy założeniach obliczeniowych.

Joe Fitzsimons
źródło

2

Mój problem z tym podejściem polega na tym, że jeśli chcesz przekonać wielu zewnętrznych obserwatorów do uczciwości, to każdy z nich musi trochę popełnić i musisz być pewien, że każdy z nich ujawni dowód swojego zaangażowania. Nie można po prostu zignorować fragmentu obserwatora, który nie ujawnia swojego dowodu, ponieważ wtedy ostatni obserwator, który ujawnił, mógł manipulować wynikiem loterii, decydując, czy ujawnić swój dowód.

Zsbán Ambrus

1

@ user8067: Nie wierzę, że jest to możliwe bez interakcji lub zaufania, że przynajmniej jedna strona jest uczciwa. Powiadam, że to dlatego, że jeśli początkowa przypadkowość jest faktycznie z góry określona przez spisek wszystkich uczestników w tym momencie, cały proces jest deterministyczny, a nie losowy. Jednak problem wymaga losowości, więc wydaje się, że jest to najlepsze, co możesz zrobić.

Joe Fitzsimons,

2

Nie jestem przekonany, że to możliwe.

Joe Fitzsimons,

2

@RickyDemer: W pytaniu nie ma wystarczających informacji, aby stwierdzić, który model przeciwnika ma zastosowanie. Gdyby Gil powiedział nam dokładnie, do czego służy, łatwiej byłoby udowodnić, czy określony program spełnia jego wymagania. Ale powiedziawszy, nie mam wątpliwości, że Gil jest w stanie sprawdzić, czy nasze odpowiedzi odpowiadają jego potrzebom.

Joe Fitzsimons,

2

@RickyDemer: Nie jest dla mnie jasne, jaki jest oczywisty model tego przypadku. Zależy to od konfiguracji i nie jest oczywiste, jakie powinny być domyślne założenia. Głosuję trochę i zaczynam zachowywać się tak, jakby zarówno moja odpowiedź, jak i odpowiedź Lwa były błędne. Nie zawierają one wyraźnie ostrzeżenia wskazanego w odpowiedzi Adama. Zauważ, że nie edytuję swojej odpowiedzi, ponieważ bez dodatkowych informacji od Gila nie widzę sensu zgadywać o modelu przeciwnika, dlatego pozostawiam go tak ogólny, jak to możliwe (nie określając, czy bitowe zaangażowanie musi być niezmienne).

Joe Fitzsimons,

15

Jak zauważyli inni użytkownicy, jest to dobrze zbadany problem w kryptografii. Nazywa się to „rzutowaniem monetą” i jest szczególnym przypadkiem obliczeń wielopartyjnych.

Jaki protokół faktycznie wykonuje to zadanie, zależy bardzo od kontekstu.

W ustawieniu „autonomicznym” protokół będzie działał w izolacji, bez angażowania graczy w inne protokoły (a nawet w interakcję ze światem zewnętrznym) w tym samym czasie. Cudownie dokładnie to potraktowano w podręczniku Oded Goldreich „Podstawy kryptografii” (tak myślę, tom 2).

Aby dać wyobrażenie o tym, jak jest subtelny, protokół „wszyscy zobowiązują się do losowych wartości” sugerowany przez innego respondenta jest niepewny, czy stosowany schemat zobowiązań jest elastyczny. Schematy zobowiązań niewymienialnych dają ci bezpieczny protokół, ale ich projektowanie jest nieco skomplikowane.

W ustawieniach, w których uczestnicy są zaangażowani w inne równoległe protokoły, potrzebujesz protokołu, który można skomponować . Istnieją różne pojęcia dotyczące kompozycyjności, ale najsilniejsza, zwana uniwersalną kompozycją , wymaga pewnych dodatkowych założeń dotyczących konfiguracji (na przykład PKI lub wspólny ciąg losowy widoczny dla wszystkich stron, ale nie kontrolowany przez żadną z nich). Niestety nie znam dostępu do tego tematu. Ale dobrym pomysłem na rozpoczęcie byłoby przyjrzenie się niedawnemu artykułowi na temat uniwersalnego składu lub niematerialnego zaangażowania.

Adam Smith
źródło

1

„Wspólny losowy ciąg widoczny dla wszystkich stron, ale nie kontrolowany przez żadną z nich” jest dokładnie tym, co chcemy wygenerować.

Zsbán Ambrus

1

a po jakimś czasie rozwiązaniu tego problemu można uniwersalnie skomponować

$\hspace{1 in}$ rozwiąż go ponownie (dowolnie wiele razy).

$\:$

Myślę, że zaangażowanie UC jest znane z konfiguracji zarejestrowanego klucza publicznego (która jest silniejszym założeniem niż PKI) i konfiguracji wielu ciągów (która jest słabszym założeniem niż wspólny ciąg losowy).

2

Witamy na stronie, Adam!

Gil Kalai

11

Uwaga: przeczytaj poniższe komentarze. Ten protokół wydaje się mieć problemy.

$p_j$

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

Każdy agent może być pewien, że wybrana liczba losowa jest losowo równomiernie, wybierając losowo swój własny wektor. Aby każdy obserwator mógł zostać przekonany, musi ufać, że przynajmniej jeden agent postępował zgodnie z protokołem, ale jeśli nie, chyba chyba nikt nie chciał uczciwej loterii.

Lew Reyzin
źródło

Przepraszam, Lev, właśnie zauważyłem twoją odpowiedź. Kiedy zacząłem pisać odpowiedź, nic tu nie było, ale wydaje się, że oboje znaleźliśmy bardzo podobne odpowiedzi.

Joe Fitzsimons,

Bez obaw! Wygląda więc na to, że jesteśmy na dobrej drodze.

Lev Reyzin

Tak, właściwie myślę, że jest wiele artykułów na ten temat w kontekście rzucania monetami, ale tak naprawdę nie znam tej literatury na tyle dobrze, aby udzielić właściwej odpowiedzi na jej podstawie.

Joe Fitzsimons,

7

Najwcześniejsze znane mi odniesienie to: M. Blum. Rzut monetą przez telefon. CRYPTO 1981: 11-15. Można pobrać ze strony dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/...

Ryan Williams

4

Istnieje standardowy atak, jeśli używasz standardowych schematów bitów (np. Haszowanie). Rozważmy sprawę z dwiema stronami, Alice i Bobem, gdzie Alice idzie pierwsza. Po tym, jak Alice wyemituje swoje zobowiązanie, Bob może je skopiować. Po tym, jak Alice otworzy swoje zobowiązanie, Bob może teraz otworzyć to samo. Teraz ich losowe wektory są równe, więc xor do zera - Bob był w stanie zmusić wartość końcową do zera, co jest sprzeczne z wymogiem uczciwości.

DW

-3

Bierni obserwatorzy nie mogą zweryfikować, czy rysunek nie został zainscenizowany. Dane wejściowe do procesu pseudolosowego można wybrać w celu uzyskania pożądanego rezultatu.

Jeśli jednak obserwator może podać losową liczbę, o której wie, że jest losową ORAZ upewnić się, że inni agenci nie zmienią później swoich danych wejściowych (ponieważ mogliby zrekompensować jego efekt swoimi danymi wejściowymi), to może być pewien, że wynik był rzeczywiście losowy .

Wymaga to schematu zobowiązań, którego nie znamy, a który jest matematycznie udowodniony, że jest bezpieczny, ale w praktyce można go zrealizować za pomocą bezpiecznego skrótu (takiego jak SHA3).

Rozważ ten przykład:

wprowadź opis zdjęcia tutaj

Zrobiłem przykładową implementację. Możesz to zobaczyć na żywo tutaj: https://mrogalski.eu/cl/ lub sprawdź źródła na GitHub .

Marek Rogalski
źródło

1

Jest to już odnotowane w odpowiedzi Joe.

Kaveh

1

Ilustracja graficzna jest bardzo ładna!

Gil Kalai

3

Grafika jest bardzo ładna, ale twoja odpowiedź nie zawiera niczego, czego nie ma w istniejących odpowiedziach.

David Richerby

Loteria, którą możesz przekonać, że jest uczciwa

Odpowiedzi: