Názory k článku Anonymita a analýza toku dát v p2p sieťach
-
Thx :-)
Ešte posledný detail k matematicky dokázateľnej bezpečnosti onion routingových sietí:
Takmer všetky bezpečnostné modely predpokladajú existenciu náhodného orákula (http://en.wikipedia.org/wiki/Random_oracle_model). Ak k teórii zložitosti pridáte axiom existencie náhodného orákula, vyjde NP != P (Shoup 1997: Lower Bounds for Discrete Logarithms and Related Problems, http://citeseer.ist.psu.edu/context/47027/140283; a veta Baker-Gill-Solovay 1975, pre popis pozrite napr. sem: http://theory.csail.mit.edu/~madhu/ST05/scribe/lect02.pdf).
Druhá vec je existencia, resp. konštruovateľnosť náhodného orákula v našom bežnom svete. Žiadny konečný algoritmus (napr. pseudonáhodný generátor - PRNG) nemôže byť náhodným orákulom, to je v spore s definíciou náhody (keby som si tak pamätal, kto to definoval). Tá definícia znie zhruba: náhodný reťazec je taký, čo nie je možné zapísať v počte znakov menšom ako dĺžka samotného reťazca. Pretože algoritmus má konečný zápis, nemôže byť náhodné orákulum.
Niečo podobné dostanete, ak si zoberiete deterministický Turingov stroj, dáte mu algoritmus, ktorý zastane práve pre jeden vstup z 1..m, pre ostatné počíta nekonečne dlho (zacyklí sa). Úlohou je napísať algoritmus, ktorý rozhodne v polynomiálnom čase, pre ktorý vstup algoritmus zastane. Pre ten stroj nie je možné napísať konečný algoritmus, ktorý by úlohu vedel vypočítať v polynomiálnom čase vzhľadom k počtu bitov m. Ku každému konečnému algoritmu nájdete protipríklad nejakého špeciálneho PRNG. Toto je vlastne "vyskočenie von z teórie zložitosti", nástrojom je buď diagonalizácia (ako pri halting probléme) alebo transfinitná indukcia.
Po ľudsky povedané, je to dôvod, prečo vždy pri prelomení nejakej ochrany sa vyvinie ochrana nová a tá sa znova prelomí a tak až do nekonečna.
Náhodné orákulum by ste v našom svete najskôr skonštruovali využitím kvantovej teórie. Náhodné generátory založené na tepelnom šume by mohli byť jedným príkladom, niekde som videl náhodný generátor založený na lávovej lampe :-). Ten fungoval tak, že kamera fotila lávové lampy, to sa prehnalo nejakou MD5-kou a výsledok boli nejaké (aspoň zdanlivo) náhodné čísla. Do toho fyzikom radšej vŕtať nebudem.
No hádam mám tú úvahu správne, inak dostanem od logikov po prstoch. Ale risknem to ;-) -
V matematike by ste náhodné orákulum asi mohli hľadať v obecnom probléme diskrétneho logaritmu (generalized discrete logarithm problem, GDLP, pre definíciu si napr. vygooglite Handbook of Applied Cryptography) alebo v jeho podmnožine, diskrétny logaritmus na multiplikatívnych grupách Z_p^* (DLP), p prvočíslo (multiplikatívna grupa telesa celých čísel modulo p).
Za základ g si ale neberte generátor grupy Z_p^*, ale prvok vysokého prvočíselného rádu q, q delí p-1 (rád grupy), dostanete tak grupu rádu q. (Kľudne si môžte zobrať aj generátor, úlohu tým nezjednodušíte, ale mne sa zdá, že pri tom prvku s prvočíselným rádom sa o tom lepšie rozmýšľa ;-)).
Pokiaľ viem, nikto neukázal, že takáto grupa je náhodné orákulum, ani neukázal opak. Problém asi bude v tom, že krátky zápis grupy je v spore s definíciou náhody. Pri GDLP toto ale neplatí. -
A pri GDLP zase nenapcháte vstup na pásku Turingovho stroja v "krátkom zápise" (spor s definíciou náhody), GDLP musí byť reprezentované orákulom. Ak teda pridáme axiom "neexistuje náhodné orákulum" do teórie zložitosti, malo by z toho vyjsť, že pre každý konečný vstup musí existovať konečný algoritmus, ktorý rieši úlohu v polynomiálnom čase.
Po pridaní axiomu "neexistuje náhodné orákulum" pre každý problém s konečným vstupom (dĺžka ohraničená nejakou konštantou n) dokážeme vytvoriť algoritmus s konečným popisom, ktorý ho rieši v polynomiálnom čase (trápne zakódujeme všetky odpovede do stavov pre všetky možné vstupy, napr. ako haštabuľku). Problémy, ktoré boli nepolynomiálne vo svete s náhodným orákulom, budú polynomiálne tu, pretože zakódovanie ich vstupu je také dlhé ako samotný problém.
BTW, keď tak moje úvahy ignorujte alebo mi tam nájdite chybu ;-)
ČLÁNKY DO MAILU