Kriptografi oblikujejo pristop za popolno zasebnost iskanja | Revija Quanta

Vsi vemo, da moramo biti previdni pri podrobnostih, ki jih delimo na spletu, vendar so informacije, ki jih iščemo, lahko tudi razkrivajoče. Poiščite navodila za vožnjo in našo lokacijo bo veliko lažje uganiti. Preverite, ali je geslo v kopici ogroženih podatkov, in tvegamo, da ga sami razkrijemo.

Te situacije sprožajo ključno vprašanje v kriptografiji: Kako lahko potegnete informacije iz javne baze podatkov, ne da bi razkrili karkoli o tem, do česa ste dostopali? To je enakovredno odjavi knjige iz knjižnice, ne da bi knjižničar vedel, katero.

Izdelava strategije, ki rešuje to težavo - znano kot pridobivanje zasebnih informacij - je "zelo uporaben gradnik v številnih aplikacijah za ohranjanje zasebnosti," je dejal David Wu, kriptograf na teksaški univerzi v Austinu. Od devetdesetih let prejšnjega stoletja so raziskovalci to vprašanje odpravili in izboljševali strategije za zasebni dostop do baz podatkov. Eden glavnih ciljev, ki je še vedno nemogoč z velikimi bazami podatkov, je enakovreden zasebnemu iskanju v Googlu, kjer lahko anonimno presejete kopico podatkov, ne da bi pri tem opravili kakršno koli težko računalniško delo.

Zdaj so trije raziskovalci izdelana dolgo iskano različico pridobivanja zasebnih informacij in jo razširil za izgradnjo splošnejše strategije zasebnosti. Delo, ki je prejelo a Najboljša nagrada za papir junija na letnem Simpozij o teoriji računalništva, podira veliko teoretično oviro na poti do resnično zasebnega iskanja.

"[To je] nekaj v kriptografiji, kar smo si verjetno vsi želeli, a nismo povsem verjeli, da obstaja," je dejal Vinod Vaikuntanathan, kriptograf na tehnološkem inštitutu v Massachusettsu, ki ni sodeloval pri tem dokumentu. "To je pomemben rezultat."

Problem dostopa do zasebnih baz podatkov se je izoblikoval v devetdesetih letih. Sprva so raziskovalci domnevali, da je edina rešitev skeniranje celotne zbirke podatkov med vsakim iskanjem, kar bi bilo, kot če bi knjižničar prebrskal vsako polico, preden bi se vrnil s knjigo. Konec koncev, če bi iskanje preskočilo kateri del, bi knjižničar vedel, da vaše knjige ni v tem delu knjižnice.

Ta pristop deluje dovolj dobro na manjših lestvicah, toda ko zbirka podatkov raste, se čas, potreben za njeno skeniranje, povečuje vsaj sorazmerno. Ko berete iz večjih podatkovnih zbirk – in internet je precej velik – postopek postane prehibo neučinkovit.

V zgodnjih 2000-ih so raziskovalci začeli sumiti, da bi se lahko izognili oviri celotnega skeniranja s "predobdelavo" baze podatkov. V grobem bi to pomenilo kodiranje celotne baze podatkov kot posebne strukture, tako da bi strežnik lahko odgovoril na poizvedbo tako, da prebere le majhen del te strukture. Dovolj skrbna predhodna obdelava bi lahko v teoriji pomenila, da gre en sam strežnik, ki gosti informacije, skozi postopek samo enkrat, kar vsem prihodnjim uporabnikom omogoča, da zasebno pridobijo informacije brez dodatnega truda.

za Daniel Wichs, kriptografa na univerzi Northeastern in soavtorja novega članka, se je to zdelo prelepo, da bi bilo res. Okoli leta 2011 je začel poskušati dokazati, da je tovrstna shema nemogoča. "Bil sem prepričan, da tega ni mogoče storiti," je dejal.

Toda leta 2017 sta dve skupini raziskovalcev objavljeno Rezultati ki si je premislil. Izdelali so prve programe, ki so lahko izvajali tovrstno iskanje zasebnih informacij, vendar niso mogli dokazati, da so programi varni. (Kriptografi dokazujejo varnost sistema tako, da pokažejo, da je vdiranje v sistem enako težko kot rešitev nekega težkega problema. Raziskovalci ga niso mogli primerjati s kanoničnim težkim problemom.)

Wichs je torej kljub temu, da se mu je obnovilo upanje, domneval, da je katera koli različica teh programov, ki bi bila varna, še daleč. Namesto tega sta on in njegovi soavtorji - Wei-Kai Lin, zdaj na Univerzi v Virginiji, in Ethan Mook, prav tako pri Northeastern — delali na težavah, za katere so mislili, da bodo lažje, kar je vključevalo primere, ko več strežnikov gosti zbirko podatkov.

Z metodami, ki so jih preučevali, je mogoče informacije v bazi podatkov pretvoriti v matematični izraz, ki ga lahko strežniki ovrednotijo ​​in izvlečejo informacije. Avtorji so ugotovili, da bi bilo mogoče narediti ta postopek ocenjevanja učinkovitejši. Poigravali so se z idejo iz leta 2011, ko so drugi raziskovalci našli način za hitro ovrednotenje takega izraza s predhodno obdelavo in ustvarjanjem posebnih, kompaktnih tabel vrednosti, ki vam omogočajo, da preskočite običajne korake vrednotenja.

Ta metoda ni prinesla nobenih izboljšav in skupina je skoraj obupala – dokler se niso spraševali, ali bi to orodje morda dejansko delovalo v zaželenem primeru z enim strežnikom. Ugotovili so, da je treba polinom izbrati dovolj previdno, in en sam strežnik bi ga lahko predhodno obdelal na podlagi rezultata iz leta 2011 – s čimer bi dobili varno in učinkovito shemo iskanja, o kateri je Wichs razmišljal leta. Nenadoma so kljub vsemu rešili težji problem.

Avtorji sprva niso verjeli. "Ugotovimo, kaj je s tem narobe," se je spomnil razmišljanja Wichs. "Vedno smo poskušali ugotoviti, kje se pokvari."

Toda rešitev je obdržala: res so odkrili varen način za predhodno obdelavo baze podatkov z enim strežnikom, tako da bi lahko kdorkoli skrivaj črpal informacije. "Resnično presega vse, kar smo pričakovali," je dejal Yuval Ishai, kriptograf pri Technionu v Izraelu, ki ni bil vključen v to delo. To je rezultat, "nismo bili dovolj pogumni niti zahtevati," je dejal.

Ko so zgradili svojo skrivno shemo iskanja, so se avtorji obrnili k resničnemu cilju zasebnega internetnega iskanja, ki je bolj zapleteno kot črpanje informacij iz baze podatkov, je dejal Wichs. Shema zasebnega iskanja sama po sebi sicer omogoča različico zasebnega iskanja, podobnega Googlu, vendar je izjemno delovno intenzivna: Googlov algoritem zaženete sami in na skrivaj črpate podatke iz interneta, ko je to potrebno. Wichs je dejal, da je pravo iskanje, pri katerem pošljete zahtevo in se usedete, medtem ko strežnik zbira rezultate, v resnici tarča širšega pristopa, znanega kot homomorfno šifriranje, ki prikrije podatke, tako da lahko nekdo drug z njimi manipulira, ne da bi o njih sploh vedel. .

Običajne strategije homomorfnega šifriranja bi naletele na isto težavo kot pridobivanje zasebnih informacij, pri čemer se za vsako iskanje prebijajo po vsej internetni vsebini. Toda z uporabo svoje zasebne metode iskanja kot gradbenega odra so avtorji izdelali novo shemo, ki izvaja izračune, ki so bolj podobni programom, ki jih uporabljamo vsak dan, prikrito črpajo informacije, ne da bi pretresli ves internet. To bi zagotovilo povečanje učinkovitosti pri iskanju po internetu in vseh programih, ki potrebujejo hiter dostop do podatkov.

Medtem ko je homomorfno šifriranje uporabna razširitev sheme zasebnega iskanja, Ishai pravi, da iskanje zasebnih informacij vidi kot temeljnejšo težavo. Rešitev avtorjev je »čarobni gradnik« in njihova strategija homomorfnega šifriranja je naravno nadaljevanje.

Zaenkrat nobena shema ni praktično uporabna: predhodna obdelava trenutno pomaga v skrajnih primerih, ko se velikost baze podatkov poveča proti neskončnosti. Toda dejanska uvedba pomeni, da se ti prihranki ne morejo uresničiti, postopek pa bi pojedel preveč časa in prostora za shranjevanje.

Na srečo, je dejal Vaikuntanathan, imajo kriptografi dolgo zgodovino optimizacije rezultatov, ki so bili sprva nepraktični. Če bo prihodnje delo lahko racionaliziralo pristop, verjame, da so zasebna iskanja iz velikanskih baz podatkov morda dosegljiva. "Vsi smo mislili, da smo tam nekako obtičali," je dejal. "Danielov rezultat daje upanje."

Quanta izvaja vrsto anket, da bi bolje služil svojemu občinstvu. Vzemite našo anketa bralcev računalništva in vključeni boste v brezplačno zmago Quanta trgovsko blago.