U kojem računarskom univerzumu živimo?
Kako bi otkrili da li je uistinu moguća sigurna kriptografija, kriptografi žele saznati u kojem od pet mogućih svjetova živimo
Mnogi kompjuterski naučnici fokusiraju se na prevazilaženje teških računarskih problema. Međutim, postoji jedno područje u računarstvu u kojem je težina prednost i gdje su poželjne teške prepreke između vaših protivnika i vaših tajni – to područje zove se kriptografija.
Nažalost, ne znamo da li istinski sigurna kriptografija postoji. Hiljadama godina ljudi su stvarali šifre koje su se činile nedokučivim sve dok ih neko nije razbio. Danas se naše internet transakcije i državne tajne čuvaju metodama šifriranja koje se čine sigurnim, ali je moguće da bi u bilo kojem trenutku mogle podbaciti.
Kako bismo stvorili istinski sigurnu (i trajnu) metodu šifriranja, potreban nam je dovoljno težak računarski problem kako bismo stvorili dokazano nepremostivu prepreku za naše protivnike. Poznati su nam mnogi računarski problemi koji se čine teškim, no možda do sada nismo bili dovoljno pametni da ih riješimo. Ili su možda neki od tih problema teški, ali njihova težina nije takva kakva bi nam dopustila sigurno šifriranje. U osnovi, kriptografi se pitaju: Da li u svemiru postoji išta što je dovoljno teško da kriptografiju učini mogućom?
Russell Impagliazzo sa Univerziteta u Kaliforniji, San Diego, 1995. godine je razložio pitanje težine na skup potpitanja kojim bi se računarski naučnici mogli pozabaviti dio po dio. Kako bi sažeo razinu znanja u ovoj oblasti, opisao je pet mogućih svjetova koje je maštovito nazvao Algoritmika, Heuristika, Pesilend, Minikript i Kriptomanija – počevši od nižeg ka višem stepenu težine i kriptografske mogućnosti. Svaki od ovih svjetova mogao bi biti svijet u kojem živimo.
Algoritmika
U ovom svijetu, najprirodnija računarska pitanja su sva lagana, što kriptografiju čini nemogućom. Ovdje se skup problema sa efikasnim rješenjima - skup nazvan P - ne sastoji samo od problema za koja smo već iznašli rješenja. On isto tako uključuje sve probleme u drugom skupu nazvanom NP, a koji se sastoji od problema za koja je lako provjeriti predloženo rješenje ukoliko vam ga neko pruži.
Na površini, P i NP čine se kao različite kategorije. Na primjer, uzmimo problem pri odlučivanju da li će u kofer moći stati sve stvari koje želimo spakovati za putovanje. Ukoliko nam prijatelj pakuje stvari, lakše je provjeriti da li je sve spakovano - potrebno je samo pregledati da li nešto nedostaje. Dakle, problem sa pakovanjem kofera je u NP-u. No teže je kada sami pakujemo kofere - ponekad moramo isprobati mnogo različitih načina za raspoređivanje stvari. Nije jasno da li postoji efikasan algoritam koji rješava ovaj problem za sve moguće kombinacije stvari i kofera. To jest, ne znamo da li je ovaj problem u P-u.
Problem dešifriranja neke sheme šifriranja je isto tako u NP-u. Na kraju krajeva, ukoliko imamo neku šifriranu poruku, a neki prijatelj tvrdi da ju je dešifrirao, može se provjeriti da li je to tačno tako što se dešifrirana poruka ubaci u mašinu za šifriranje i provjeri da li se rezultat podudara sa originalnom šifriranom porukom. (Naravno, kako bi se ovo moglo uraditi potrebno je posjedovati jednu od mašina za šifriranje, a kriptografi jednu shemu ne smatraju sigurnom ukoliko ne može odoljeti napadima neprijatelja koji se dočepa jedne od tih mašina).
U Algoritmici, P i NP su isti skup problema. Dokaz toga bilo bi algoritamsko izobilje, s obzirom na to da bi to značilo da postoje brzi algoritmi za stvari kao što su pakovanja kofera i za sve druge naizgled teške probleme u NP-u. Međutim, to bi bila katastrofa za kriptografe jer bi dešifriranje bilo jedan od problema koje bismo mogli efikasno riješiti.
Mnogi računarski naučnici vjeruju kako se P razlikuje od NP iz prostog razloga što postoje mnogi problemi u NP-u koje nismo uspjeli efikasno riješiti. No niko nije uspio dokazati (ili opovrgnuti) ovo, iako se posljednjih pet desetljeća pitanje "P nasuprot NP" smatra najpoznatijim problemom u teorijskom računarstvu. Yuval Ishai sa izraelskog Instituta za tehnologiju Tehnion u Haifi, rekao je kako "osim stalnog neuspjeha najpametnijih ljudi, nemamo nikakvog dokaza da je teško dokazati da P nije jednako NP."
Heuristika
Na ovom svijetu, postoje problemi u NP-u koji nisu jednostavni za riješiti, ali svaki problem u NP-u je "u prosjeku" lagan, što znači da se u većini slučajeva može efikasno riješiti. Na primjer, ukoliko smo u Heuristici, onda postoji efikasan algoritam za pakovanje kofera koji je gotovo uvijek uspješan, ali i on može podbaciti za neke rijetke kombinacije kofera i stvari za pakovanje. (Ovi brzi i najčešće uspješni algoritmi obično se nazivaju "heuristici".)
S tačke gledišta kriptografije, ne postoji velika razlika između Heuristike i Algoritmike. Ukoliko osmislimo neku shemu šifriranja u Heuristici, nastat će neke brze metode dešifriranja koje se mogu upotrijebiti za gotovo sve poruke, što ovu shemu čini beskorisnom za praktičnu upotrebu.
Pesilend
Ovo je najgori od svih mogućih svjetova. U Pesilendu, nekih problemi u NP-u su čak i u prosjeku teški. Za ove probleme, svi efikasni algoritmi će podbaciti ne samo s vremena na vrijeme, već često. Ipak, ovi teški problemi nisu one vrste koja je korisna za skrivanje tajnih informacija.
"Zasigurno ne želimo živjeti u Pesilendu," kazao je Eric Allender sa Univerziteta Rutgers. "Tu imamo sve loše aspekte (računarske) kompleksnosti, ali bez prednosti kao što je kriptografija."
Minikript
U ovom svijetu, neki problemi u NP-u su u prosjeku teški i dovoljno su teški da izgrade najosnovniju građu kriptografije, a to je "jednosmjerna funkcija", što je funkcija koja se može efikasno izvršiti, ali se ne može efikasno poništiti. Kriptografi su dokazali da su za sigurnu kriptografiju neophodne jednosmjerne funkcije. Ukoliko ih imamo, dobit ćemo niz kriptografskih poslastica kao što su šifriranje tajnim enkripcijskim ključem, digitalni potpisi, i generatori pseudo-nasumičnih brojeva.
"Bez ikakve sumnje, jedan od najbitnijih problema u kriptografiji je da li postoje jednosmjerne funkcije", rekao je Rafael Pass sa Univerziteta Cornell i Cornell Tech. "Ukoliko ne postoje, sve ove stvari se mogu razbiti."
Kriptomanija
U ovom svijetu imamo dovoljno težine za stvaranje svega što ima u Minikriptu i pored toga još i za stvaranje naprednijih kriptografskih protokola kao što je šifriranje javnim ključem (u kojem ljudi mogu slati šifrirane poruke bez da znaju tajni ključ).
Eliminiranje svjetova
Ishai kaže da većina kriptografa vjeruje da postoji makar neka vrsta kriptografije, tako da vjerovatno živimo u Kriptomaniji ili Minikriptu. Ali oni ne očekuju da će se dokaz koji bi ovo potkrijepio pojaviti u dogledno vrijeme. Za takav dokaz bilo bi potrebno isključiti ostala tri svijeta - a samo za isključivanje Algoritmike neophodno je riješiti problem "P nasuprot NP" sa kojim se računarski naučnici već godinama bore.
No ipak, nedavno su Pass i studentica doktorskih studija Yanyi Liu pronašli novi pristup za pretraživanje po ovim svjetovima. Po prvi put, otkrili su prirodni problem - nazvan vremenski ograničena Kolmogorovljeva složenost ili skraćeno Kt - čiji nivo težine stvara jasnu liniju razdvajanja između svjetova koji uključuju kriptografiju i onih u kojima je nema. Liu i Pass su pokazali da ukoliko je Kt u prosjeku lagan, onda sigurna kriptografija ne postoji, tako da smo u Algoritmici, Heuristici ili Pesilendu. No ukoliko je Kt u prosjeku težak, onda možemo kreirati jednosmjerne funkcije, tako da smo makar u Minikriptu, a možda i u Kriptomaniji.
Ovaj novi rezultat znači da računarski naučnici mogu eliminirati Pesilend, najgori svijet, ukoliko mogu dokazati još jednu tvrdnju: Ukoliko je Kt u prosjeku lagan, onda je i svaki problem u NP-u lagan. U tom slučaju, stvari bismo suzili na one svjetove u kojima je Kt u prosjeku težak (Minikript i Kriptomanija) i na one u kojima je Kt - i svaki drugi problem u NP-u - u prosjeku lagan (Algoritmika i Heuristika).
Ryan Williams sa MIT-a kazao je kako su se istraživači neko vrijeme udaljavali od Pesilenda. "Mislim da je generalni koncenzus da se Pesilend može isključiti, ali da li ćemo to prije ili kasnije uraditi, to već ne znam."
Kriptografi bi isto tako mnogo željeli eliminirati Heuristiku, što bi uključilo dokazivanje da ukoliko je Kt u prosjeku lagan, onda je svaki problem u NP-u lagan u svim slučajevima (ne samo u prosjeku). Isključivanje ova dva svijeta značilo bi da živimo ili u Algoritmici, gdje je sve jednostavno sve vrijeme, ili da postoji dovoljno težine za osnovnu kriptografiju.
Kriptografi na ovaj cilj gledaju kao na sveti gral ove oblasti. Ishai ne očekuje da će se to dokazati tokom njegovog života, no čak i to je neizvjesno. "Kada se teški problemi odgonetnu, nekada to možemo predvidjeti, a nekada ne možemo," rekao je. "Ova nova linija rada nam je definitivno najbolja šansa."
Izvor: Quanta Magazine
S engleskog prevela: Amina Turudija, Prometej.ba