Kétszemélyes cryptogenography 0.3384 fölé

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.

Például, ha $A$ az owner, akkor egy lehetséges lefutás:

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

Ennek a lefutásnak az esélye $\frac{1}{3}$. Egy másik lefutás:

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

Ennek szintén $\frac{1}{3}$ az esélye. A harmadik lefutás:

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

Tehát ha $A$ az owner, akkor a három egyforma valószínű futásból kettőben a tényleges titok értékét hirdeti ki, ami $\frac{2}{3}$ esély. Ha nem $A$ az owner, akkor szintén ugyanez történik, ki lehet számolni azt is.

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.

Tehát a protokoll lefutása után az ellenség kiszámítja (ismerve a protokollt ezt meg tudja tenni), hogy ki kettejük közül a valószínűbb owner, és ezt a játékost jelöli meg. Ebben a protokollban mindig azt jelöli meg az ellenség, aki a második körben csendben volt.

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

Olyan protokollt kell terveznünk, ami maximalizálja ezt az esélyt.

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.

Tehát ebben a protokollban $1/3$ az esélye annak, hogy az igazi titok kerül bejelentésre, az owner pedig megússza.

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.

Például:

• $(\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.

Ez a fa ezekkel az $\frac{1}{12}$-ekkel és $\frac{1}{6}$-okkal egyébként a cikkben elolvasható módon éppen megfelel a TwoBit protokollnak. A cikkben azt csinálták, hogy felépítettek egy keresőprogrammal egy

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.