Anonymita ako cieľ štúdia súkromia a hra na deanonýmizáciu
Anonymita je konečným cieľom pri štúdiu súkromia a deanonýmizáciu si možno predstaviť ako hru. Predstavíme si protivníka s prístupom k určitým informáciám, ktorý sa snaží správne odhadnúť, ktorý z kandidátov bol zodpovedný za určitú udalosť v systéme. Na obranu proti tomuto protivníkovi je potrebné ho udržať v neistote, čo môže znamenať obmedzenie jeho prístupu k informáciám alebo použitie náhodnosti na zvýšenie množstva informácií, ktoré potrebuje na úspech.
Mnohí čitatelia poznajú hru „Hádaj, kto?“. Túto hru možno popísať ako hru s tahmi, ktorá kombinuje dve inštancie všeobecnejšej hry „dvadsať otázok“. V hre „dvadsať otázok“ si tajne vyberiete prvok z danej množiny a váš súper sa ho snaží uhádnuť položením maximálne 20 otázok s odpoveďou áno alebo nie. V „Hádaj, kto?“ sa hráči striedajú a prvý, kto správne uhádne, vyhráva. Množina prvkov je v tejto hre pevne daná a pozostáva z 24 kreslených postavičok s rôznymi rozlišovacími znakmi, ako je farba vlasov alebo štýl. Každá postavička má jedinečné meno, ktoré ju jednoznačne identifikuje.
Odpovede na otázky áno alebo nie môžu byť reprezentované ako bit – nula alebo jedna. Dvadsať bitov môže vyjadriť v základnej sústave 2 akékoľvek celé číslo v rozsahu od 0 do 1 048 575, čo je 2²⁰-1. Ak je množina úplne usporiadaná, každý prvok môže byť indexovaný podľa svojej pozície v tomto poradí, čo ho jednoznačne identifikuje. Takže 20 bitov môže adresovať jeden z viac ako milióna prvkov.
Aj keď 2²⁰ je maximálny počet prvkov množiny, ktoré je možné jednoznačne identifikovať pomocou odpovedí na 20 otázok áno alebo nie, v reálnych situáciách bude mať 20 odpovedí často menej informácií. Vo väčšine prípadov sa veci nebudú dokonale ladiť a nie každá otázka rozdelí kandidátov nezávisle od ostatných otázok. Niektoré odpovede môžu byť zaujaté, zatiaľčo iné môžu korelovať s odpoveďami na iné otázky.
Predstavte si, že namiesto otázky „Má tvoja postavička okuliare?“ by ste sa vždy pýtali: „Podľa abecedného poradia, je meno tvojej postavičky pred [medziľahlým menom zostávajúcej postavy]?“ Toto je binárne vyhľadávanie, ktoré maximalizuje informatívnosť každej odpovede. Pri každom kroku medianálne meno rozdelí množinu zostávajúcich postavičiek a otázka eliminuje jednu z dvoch polovíc. Opakované rozdeľovanie na polovicu zúži vyhľadávanie čo najrýchlejšie, pretože je potrebný len logaritmický počet krokov, čo je oveľa rýchlejšie ako lineárne prehľadávanie.
Ak hráč nie je úprimný, môže podvádzať bez toho, aby bol odhalený. Namiesto výberu prvku množiny na začiatku a úprimných odpovedí môže vždy poskytnúť odpoveď, ktorá ponechá čo najviac kandidátov. Adaptívne Zvolené odpovede minimalizujú rýchlosť, ktorou súper získa užitočné informácie. V tomto takzvanom byzantskom prostredí už optimálna strat
Yuval Kogman
