Kryptografit kehittävät lähestymistavan täydelliseen haun tietosuojaan | Quanta-lehti

Tiedämme kaikki olla varovaisia ​​verkossa jakamissamme yksityiskohdissa, mutta etsimämme tiedot voivat myös olla paljastavia. Hae ajo-ohjeita, niin sijaintimme on paljon helpompi arvata. Tarkista salasana vaarantuneista tiedoista, niin vaarannamme vuotaa sen itse.

Nämä tilanteet ruokkivat kryptografian avainkysymystä: Kuinka voit hakea tietoja julkisesta tietokannasta paljastamatta mitään siitä, mitä olet käyttänyt? Se vastaa kirjan lukemista kirjastosta ilman, että kirjastonhoitaja tietää, mikä.

Tämän ongelman ratkaisevan strategian laatiminen – joka tunnetaan nimellä yksityisen tiedon haku – on "erittäin hyödyllinen rakennuspalikka useissa yksityisyyttä suojaavissa sovelluksissa", sanoi. David Wu, kryptografi Texasin yliopistossa Austinissa. 1990-luvulta lähtien tutkijat ovat hylänneet kysymyksen ja parantaneet strategioita tietokantojen yksityiseen käyttöön. Yksi tärkeä tavoite, joka on edelleen mahdoton suurilla tietokannoilla, vastaa yksityistä Google-hakua, jossa voit selata kasan tietoja anonyymisti ilman raskaita laskennallisia nostoja.

Nyt on kolme tutkijaa muotoillun kauan etsitty versio yksityisten tietojen hausta ja laajennettiin sitä rakentamaan yleisempi tietosuojastrategia. Teos, joka sai a Paras paperi -palkinto kesäkuussa vuosijuhlissa Symposium tietojenkäsittelyteoriasta, kaataa suuren teoreettisen esteen tiellä kohti todella yksityistä hakua.

"[Tämä on] jotain kryptografiaa, jonka kai me kaikki halusimme, mutta emme aivan uskoneet sen olemassaoloon", sanoi Vinod Vaikuntanathan, Massachusetts Institute of Technologyn kryptografi, joka ei ollut mukana artikkelissa. "Se on merkittävä tulos."

Yksityisten tietokantojen käyttöongelma muotoutui 1990-luvulla. Aluksi tutkijat olettivat, että ainoa ratkaisu oli skannata koko tietokanta jokaisen haun yhteydessä, mikä olisi kuin kirjastonhoitajan tutkaisi jokaista hyllyä ennen kirjan palauttamista. Loppujen lopuksi, jos haku ohittaisi jonkin osan, kirjastonhoitaja tietäisi, että kirjasi ei ole kyseisessä kirjaston osassa.

Tämä lähestymistapa toimii riittävän hyvin pienemmässä mittakaavassa, mutta tietokannan kasvaessa sen skannaamiseen kuluva aika kasvaa ainakin suhteessa. Kun luet isommista tietokannoista – ja Internet on melko suuri tietokanta – prosessista tulee kohtuuttoman tehoton.

2000-luvun alussa tutkijat alkoivat epäillä, että he voisivat väistää täyden skannauksen esteen "esikäsittelyllä" tietokannan. Karkeasti ottaen tämä tarkoittaisi koko tietokannan koodaamista erityisrakenteeksi, jotta palvelin voisi vastata kyselyyn lukemalla vain pienen osan rakenteesta. Riittävän huolellinen esikäsittely voi teoriassa tarkoittaa, että yksittäinen palvelin, joka isännöi tietoja, käy läpi prosessin vain kerran, itsestään, jolloin kaikki tulevat käyttäjät voivat napata tietoja yksityisesti ilman lisäponnistuksia.

varten Daniel Wichs, kryptografi Northeastern Universitystä ja uuden paperin toinen kirjoittaja, vaikutti liian hyvältä ollakseen totta. Vuoden 2011 tienoilla hän alkoi yrittää todistaa, että tällainen suunnitelma oli mahdoton. "Olin vakuuttunut siitä, että tämä ei ole mahdollista", hän sanoi.

Mutta vuonna 2017 kaksi tutkijaryhmää julkaistu Tulokset joka muutti hänen mielensä. He rakensivat ensimmäiset ohjelmat, jotka pystyivät hakemaan tällaista yksityistä tietoa, mutta he eivät pystyneet osoittamaan, että ohjelmat olivat turvallisia. (Salakirjoittajat osoittavat järjestelmän turvallisuuden osoittamalla, että sen rikkominen on yhtä vaikeaa kuin jonkin vaikean ongelman ratkaiseminen. Tutkijat eivät pystyneet vertaamaan sitä kanoniseen kovaan ongelmaan.)

Joten vaikka hänen toivonsa oli uusiutunut, Wichs oletti, että mikä tahansa näiden ohjelmien suojattu versio oli vielä kaukana. Sen sijaan hän ja hänen kirjoittajansa - Wei-Kai Lin, nyt Virginian yliopistossa ja Ethan Mook, myös Northeasternissä – työskenteli ongelmien parissa, joiden he ajattelivat olevan helpompia, mikä koski tapauksia, joissa useat palvelimet isännöivät tietokantaa.

Heidän tutkimissaan menetelmissä tietokannan tiedot voidaan muuntaa matemaattiseksi lausekkeeksi, jota palvelimet voivat arvioida poimiakseen tiedon. Kirjoittajat ajattelivat, että arviointiprosessia voisi olla mahdollista tehostaa. He leikkivät idealla vuodelta 2011, jolloin muut tutkijat olivat löytäneet tavan arvioida tällainen lauseke nopeasti esiprosessoimalla se luomalla erityisiä, kompakteja arvotaulukoita, joiden avulla voit ohittaa normaalit arviointivaiheet.

Tämä menetelmä ei tuottanut parannuksia, ja ryhmä oli lähellä luovuttamista - kunnes he miettivät, voisiko tämä työkalu todella toimia halutussa yhden palvelimen tapauksessa. Valitse polynomi riittävän huolellisesti, he näkivät, ja yksi palvelin pystyi esikäsittelemään sen vuoden 2011 tuloksen perusteella - mikä tuotti turvallisen ja tehokkaan hakujärjestelmän, jota Wichs oli pohtinut vuosia. Yhtäkkiä he lopulta ratkaisivat vaikeamman ongelman.

Aluksi kirjoittajat eivät uskoneet sitä. "Otetaan selvää, mikä tässä on vialla", Wichs muisti ajattelevansa. "Yritimme jatkuvasti selvittää, missä se hajoaa."

Mutta ratkaisu kesti: He olivat todella löytäneet turvallisen tavan esikäsitellä yhden palvelimen tietokanta, jotta kuka tahansa voisi hakea tietoja salassa. "Se on todella enemmän kuin kaikki mitä olimme toivoneet", sanoi Yuval Ishai, kryptografi Technionissa Israelissa, joka ei ollut mukana tässä työssä. Se on seuraus "emme olleet tarpeeksi rohkeita edes pyytämään", hän sanoi.

Salaisen hakujärjestelmän rakentamisen jälkeen kirjoittajat kääntyivät yksityisen Internet-haun todelliseen tavoitteeseen, joka on monimutkaisempaa kuin tiedon hakeminen tietokannasta, Wichs sanoi. Yksityinen hakujärjestelmä mahdollistaa yksityisen Googlen kaltaisen haun version, mutta se on erittäin työvoimavaltaista: Käytät Googlen algoritmia itse ja noutat tarvittaessa tietoja salaa Internetistä. Wichs sanoi, että todellinen haku, jossa lähetät pyynnön ja istut alas, kun palvelin kerää tuloksia, on todella kohteena laajemmalle lähestymistavalle, joka tunnetaan nimellä homomorfinen salaus, joka naamioi tiedot niin, että joku muu voi manipuloida sitä tietämättä siitä koskaan mitään. .

Tyypilliset homomorfiset salausstrategiat osuisivat samaan pulaan kuin yksityisen tiedon haku, joka tunkeutuisi Internetin kaiken sisällön läpi jokaisella haulla. Mutta käyttämällä yksityistä hakumenetelmäänsä rakennustelineinä, kirjoittajat rakensivat uuden järjestelmän, joka suorittaa laskelmia, jotka ovat enemmän kuin päivittäin käyttämiämme ohjelmia ja keräävät tietoa salaa lakaisematta koko Internetiä. Tämä tehostaisi Internet-hakuja ja kaikkia ohjelmia, jotka tarvitsevat nopean pääsyn tietoihin.

Vaikka homomorfinen salaus on hyödyllinen laajennus yksityiselle hakujärjestelmälle, Ishai sanoi, että hän näkee yksityisen tiedonhaun perustavanlaatuisempana ongelmana. Kirjoittajien ratkaisu on "maaginen rakennuspalikka", ja heidän homomorfinen salausstrategiansa on luonnollinen jatko.

Toistaiseksi kumpikaan kaava ei ole käytännössä hyödyllinen: Esikäsittely auttaa tällä hetkellä äärimmäisissä tilanteissa, kun tietokannan koko nousee kohti ääretöntä. Mutta todellisuudessa sen käyttöönotto tarkoittaa, että nämä säästöt eivät toteudu, ja prosessi kuluttaisi liikaa aikaa ja tallennustilaa.

Onneksi, Vaikuntanathan sanoi, kryptografeilla on pitkä historia alun perin epäkäytännöllisten tulosten optimoinnissa. Jos tuleva työ voi virtaviivaistaa lähestymistapaa, hän uskoo, että yksityiset haut jättimäisistä tietokannoista voivat olla ulottuvilla. "Me kaikki luulimme, että olimme jotenkin jumissa siellä", hän sanoi. "Danielin tulos antaa toivoa."

Quanta tekee sarjan kyselyjä palvellakseen paremmin yleisöämme. Ota meidän tietojenkäsittelytieteen lukijakysely ja pääset mukaan voittamaan ilmaiseksi Quanta kauppatavaraa.