Most erről lesz szó, Doerr - Künnemann : Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.
A setting a következő (a papír általánosabb, most ráhegyezem a kétszemélyesre):
- Van két játékosunk, nevezzük őket $A$-nak és $B$-nek, egyikük, nevezzük ownernek, rendelkezik egy titokkal, amit csak ő ismer, ez a titok az egyszerűség kedvéért vagy a $0$ bit, vagy az $1$ bit. Hogy melyikük az owner és mi a titok, az függetlenül $\frac{1}{2}$-$\frac{1}{2}$ eséllyel kerül kiosztásra a játék elején.
- Ők ketten azzal tisztában vannak, hogy melyikük ismeri a titkos bitet, és szeretnék úgy nyilvánosságra hozni az értékét egy publikus protokollal, hogy külső megfigyelő, az ellenség, ne tudja meg (azaz kb: minél kisebb valószínűséggel tudja megtippelni), hogy melyikük rendelkezett a titokkal.
- Ehhez használhatnak random biteket, publikusat is (amit mindenki lát, az ellenség is) és privátot is (amit pedig csak az, aki generálja).
Nyilván a WikiLeaks és társai azok, amik a sztori szerint motiválják ezt ($k$ játékosra), hogy ez mennyire van valóban így, azt az utókorra hagynám :D mutatok egy példát, és azon keresztül megnézzük ezt a minimalizálandó valószínűség dolgot.
A közismert (és 2016-ig optimálisnak sejtett) "TwoBit" protokoll a következő (mindjárt elemezni is fogjuk):
- Először az $A$ játékos lép. Ő ebben a lépésében azt fogja kihirdetni, hogy a következő lépésben $A$ vagy $B$ beszéljen, mégpedig a következőképpen hirdet:
- Ha $A$ az owner, akkor $\frac{2}{3}$ eséllyel azt mondja, hogy $B$ beszéljen és $\frac{1}{3}$ eséllyel azt mondja, hogy $A$ beszéljen.
- Ha $A$ nem az owner, akkor pont fordítva: $\frac{2}{3}$ eséllyel nevezi meg magát, és $\frac{1}{3}$ eséllyel $B$-t.
- A második körben bárki is beszél, az
- ha ő az owner, akkor bejelenti, hogy "a titok $X$", ahol $X$ a titok tényleges értéke;
- ha nem ő az owner, akkor bejelenti, hogy "a titok $X$", ahol $X$ egy $\frac{1}{2}-\frac{1}{2}$ eséllyel generált random bit.
- bejön a $\frac{2}{3}$, amekkora eséllyel átadja $B$-nek a beszéd jogát,
- aztán $B$ (mivel nem ő az owner) $\frac{1}{2}$ eséllyel dob egy $0$ bitet és ezt hirdeti ki.
- bejön a $\frac{2}{3}$, amekkora eséllyel átadja $B$-nek a beszéd jogát,
- aztán $B$ (mivel nem ő az owner) $\frac{1}{2}$ eséllyel dob egy $1$ bitet és ezt hirdeti ki.
- bejön az $\frac{1}{3}$, amekkora eséllyel megtartja a beszéd jogát,
- aztán mivel ő az owner, kihirdeti a titok tényleges értékét.
Persze ha csak annyi lenne a célfüggvényünk, hogy hirdessük ki a titkot, akkor $A$ először mindenképp átadná a vezérlést az ownernak, aki aztán igazmond. Ekkor biztosan a tényleges titok értékét hirdetnénk ki, azonban ebben a feladatban az is cél (mindjárt meglátjuk, hogy hogyan), hogy amennyire lehet, titokban tartsuk az owner kilétét. Ha mindenképp az ownernak adjuk át a beszéd jogát, akkor az ellenség tudni fogja, hogy az az owner, aki megszólalt a második körben.
Elemezzük ki, hogy a TwoBit-ben mit is tud az ellenség abból, amit lát?
- Ha azt látja, hogy $A$ átadja $B$-nek a jogot, aki bejelent egy bitet, akkor azt tudja ebből kikövetkeztetni, hogy $\frac{1}{3}$ eséllyel $B$ volt az owner és $\frac{2}{3}$ eséllyel $A$ volt az owner. Ekkor ő a maximum likelihood becslés alapján rámutat $A$-ra, hogy "ő volt az owner!"
- Ha azt látja, hogy $A$ nem adja át $B$-nek a jogot, akkor a protokoll alapján $B$ a valószínűbb owner, ekkor az ellenség $B$-t jelöli meg.
$A$ és $B$ akkor győznek, ha
- sikerül a tényleges titokbit értékét kihirdetniük ÉS
- az ellenség pont a másikukat jelöli meg, mint aki az owner.
Ha mindenképp az ownernek adjuk át a jogot, akkor ugyan mindig a tényleges titokbit értékét jelöljük meg, de utána az ellenség pontosan az ownerre tud rámutatni, így $A$ és $B$ veszítenek.
A TwoBit protokoll esetén mi történik? Akkor nyer $A$ és $B$, ha az ellenség nem az ownert jelöli meg és a helyes bit került kihirdetésre. Ha kiszámoljuk a lehetséges eseteket:
- ha $A$ az ownernek adja át a jogot ($1/3$ eséllyel), az eltalálja a titkot ($1$ eséllyel), ennek összesen $1/3$ az esélye, ekkor az ellenség pont a másik játékosra fog mutatni és ekkor $A$ és $B$ nyernek.
- ha pedig $A$ nem az ownernek adja át a jogot ($2/3$ eséllyel), az mindegy, hogy eltalálja-e a titkot, az ellenség pont az ownerre fog mutatni és $A$ és $B$ veszítenek.
De nem ez a legjobb protokoll, amit erre a problémára adni lehet, erről szól a linkelt cikk.
Minden ilyen protokollt lehet egy fával reprezentálni a következőképpen:
- A fa csúcsaiban $(a,b,c,d)\in\mathbb{R}^4$ négyesek vannak, nemnegatív valós számokkal.
- A fa gyökere az $(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$ vektor, ez a kiinduló állapot.
- Egy $(a,b,c,d)$ levélcsúcs értéke: $\max\{\min\{a,c\},\min\{b,d\}\}$.
- Egy $(a,b,c,d)$ belső csúcsnak ha a két gyereke $(a_1,b_1,c_1,d_1)$ és $(a_2,b_2,c_2,d_2)$, akkor a következőknek kell teljesülniük:
- $a_1+a_2=a$, $b_1+b_2=b$, $c_1+c_2=c$, $d_1+d_2=d$, tehát a gyerek vektorok összege a szülő vektor;
- van olyan $0\leq \lambda\leq 1$, melyre vagy $\lambda(a,b)=(a_1,b_1)$, vagy $\lambda(c,d)=(c_1,d_1)$.
- Egy belső csúcs értéke pedig a gyerekcsúcsai értékének összege.
- $(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$ gyerekei lehetnek $(\frac{1}{6},\frac{1}{6},\frac{1}{12},\frac{1}{12})$ és $(\frac{1}{12},\frac{1}{12},\frac{1}{6},\frac{1}{6})$, mert a két vektor összege épp az uniform vektor és az első koordináta-páron megmaradnak az arányok;
- ha itt megállna a játék, akkor a gyökércsúcs értéke $\frac{1}{12}+\frac{1}{12}=\frac{1}{6}$ lenne;
- de nem: legyen a $(\frac{1}{6},\frac{1}{6},\frac{1}{12},\frac{1}{12})$ csúcsnak a két gyereke $(\frac{1}{12},\frac{1}{12},0,\frac{1}{12})$ és $(\frac{1}{12},\frac{1}{12},\frac{1}{12},0)$, ami valid: a két gyerekvektor összege a szülő vektor és az első koordináta-páron megmaradnak az arányok; ezeknek a leveleknek az értéke $\frac{1}{12}$, összesen tehát $\frac{1}{6}$ lesz a $(\frac{1}{6},\frac{1}{6},\frac{1}{12},\frac{1}{12})$ csúcs értéke;
- a $(\frac{1}{12},\frac{1}{12},\frac{1}{6},\frac{1}{6})$-nek pedig ha a két gyereke $(0,\frac{1}{12},\frac{1}{12},\frac{1}{12})$ és $(\frac{1}{12},0,\frac{1}{12},\frac{1}{12})$, akkor szintén kihoztuk $\frac{1}{6}$-ra ennek a csúcsnak az értékét,
- így a gyökércsúcs értéke épp $\frac{1}{3}$ lesz.
18.248 csúcsú fát
aminek az értéke $0.3384736$ lett, ami hát tényleg nagyobb, mint $\frac{1}{3}$.
Azt tudjuk még, hogy az optimum értéke legfeljebb $\frac{47}{128}$, ami kb. $0.367188$. Az igazság a két érték közt lehet valahol, de vajon mennyi lehet?
A tippem egyébként $\frac{\sqrt{5}+1}{9}\approx 0.35956$ lenne, ha tennem kéne egy educated guesst.