A kriptográfusok megközelítést dolgoznak ki a teljes keresési adatvédelem érdekében | Quanta Magazin

Mindannyian tudjuk, hogy óvatosnak kell lennünk az online megosztott részletekkel kapcsolatban, de az általunk keresett információk árulkodóak is lehetnek. Keressen autós útvonalakat, és sokkal könnyebben kitalálható lesz a helyünk. Ellenőrizze, hogy van-e jelszó a feltört adathalmazban, és azt kockáztatjuk, hogy mi magunk szivárogtatjuk ki.

Ezek a helyzetek egy kulcskérdést vetnek fel a kriptográfiában: Hogyan lehet információkat kinyerni egy nyilvános adatbázisból anélkül, hogy bármit is felfedne arról, amit elért? Ez egyenértékű azzal, mintha kivennénk egy könyvet a könyvtárból anélkül, hogy a könyvtáros tudná, melyiket.

Egy olyan stratégia kidolgozása, amely megoldja ezt a problémát – az úgynevezett privát információk visszakeresése – „nagyon hasznos építőelem számos magánélet-megőrző alkalmazásban” – mondta. David Wu, az austini Texasi Egyetem kriptográfusa. Az 1990-es évek óta a kutatók nem foglalkoznak ezzel a kérdéssel, javítva az adatbázisokhoz való privát hozzáférésre vonatkozó stratégiákat. Az egyik fő cél, amely nagy adatbázisokkal még mindig lehetetlen, egy privát Google-keresésnek felel meg, ahol névtelenül böngészhet át rengeteg adatot anélkül, hogy komoly számítási erőfeszítéseket tenne.

Most három kutatónak van kidolgozott régóta keresett változata a privát információ-visszakeresésnek, és kiterjesztette azt egy általánosabb adatvédelmi stratégia felépítésére. A mű, amelyre a A legjobb papír díja júniusban az éves Szimpózium a számítástechnika elméletéről, egy nagy elméleti akadályt dönt át a valóban privát keresés felé vezető úton.

„[Ez] valami olyasmi a kriptográfiában, amit azt hiszem, mindannyian szerettünk volna, de nem igazán hittük el, hogy létezik” – mondta. Vinod Vaikuntanathan, a Massachusetts Institute of Technology kriptográfusa, aki nem vett részt a lapban. – Ez mérföldkőnek számító eredmény.

A privát adatbázisokhoz való hozzáférés problémája az 1990-es években öltött testet. Eleinte a kutatók azt feltételezték, hogy az egyetlen megoldás az, hogy minden keresés során átvizsgálják a teljes adatbázist, ami olyan lenne, mintha egy könyvtáros minden polcot átkutatna, mielőtt visszaküldené a könyvét. Végül is, ha a keresés bármelyik részt kihagyna, a könyvtáros tudni fogja, hogy az Ön könyve nincs a könyvtár azon részében.

Ez a megközelítés elég jól működik kisebb méretekben, de az adatbázis növekedésével a vizsgálathoz szükséges idő legalább arányosan növekszik. Ahogy nagyobb adatbázisokból olvasunk – és az internet is elég nagy –, a folyamat rendkívül hatástalanná válik.

A 2000-es évek elején a kutatók gyanakodni kezdtek, hogy az adatbázis „előfeldolgozásával” kikerülhetik a teljes letapogatási akadályt. Ez nagyjából azt jelentené, hogy az egész adatbázist speciális struktúraként kódolják, így a szerver a struktúra egy kis részének beolvasásával válaszolhatna a lekérdezésre. A kellően gondos előfeldolgozás elméletileg azt jelentheti, hogy egyetlen szerver, amely információkat tárol, csak egyszer megy át a folyamaton, így minden jövőbeli felhasználó minden további erőfeszítés nélkül privát módon szerezheti meg az információkat.

A Daniel Wichs, a Northeastern University kriptográfusa és az új tanulmány társszerzője, ez túl szépnek tűnt ahhoz, hogy igaz legyen. 2011 körül elkezdte bebizonyítani, hogy ez a fajta rendszer lehetetlen. „Meg voltam győződve arról, hogy ezt semmiképpen nem lehet megtenni” – mondta.

De 2017-ben két kutatócsoport közzétett eredmények hogy meggondolta magát. Megépítették az első olyan programokat, amelyek képesek voltak ilyen jellegű privát információk visszakeresésére, de nem tudták bizonyítani, hogy a programok biztonságosak. (A kriptográfusok azzal demonstrálják a rendszer biztonságát, hogy megmutatják, hogy feltörni olyan nehéz, mint valamilyen nehéz feladat megoldása. A kutatók nem tudták összehasonlítani egy kanonikus nehéz problémával.)

Így Wichs még reményének megújításával is azt feltételezte, hogy ezeknek a programoknak bármely biztonságos verziója még messze van. Ehelyett ő és szerzőtársai - Wei-Kai Lin, most a Virginia Egyetemen, és Ethan Mook, szintén a Northeasternnél – olyan problémákon dolgozott, amelyekről azt hitték, hogy könnyebbek lesznek, amelyek olyan esetekre vonatkoztak, amikor több szerver üzemelteti az adatbázist.

Az általuk vizsgált módszerekben az adatbázisban lévő információ matematikai kifejezéssé alakítható, amelyet a szerverek kiértékelve kinyerhetik az információt. A szerzők úgy gondolták, hogy az értékelési folyamatot hatékonyabbá lehet tenni. Eljátszadoztak egy 2011-es ötlettel, amikor más kutatók megtalálták a módját, hogy gyorsan kiértékeljenek egy ilyen kifejezést az előfeldolgozással, speciális, kompakt értéktáblázatok létrehozásával, amelyek lehetővé teszik a normál értékelési lépések kihagyását.

Ez a módszer nem hozott semmilyen javulást, és a csoport közel állt a feladáshoz – egészen addig, amíg el nem töprengtek, vajon ez az eszköz valóban működhet-e az áhított egykiszolgálós esetben. Úgy látták, elég körültekintően válasszon polinomot, és egyetlen szerver képes előfeldolgozni azt a 2011-es eredmény alapján – ezzel a biztonságos, hatékony keresési sémát eredményezve, amelyen Wichs évek óta gondolkodott. Hirtelen végül is megoldották a nehezebb problémát.

A szerzők először nem hitték el. „Nézzük ki, mi a baj ezzel” – emlékezett Wichs a gondolataira. "Folyamatosan próbáltuk kitalálni, hol romlik el."

A megoldás azonban megmaradt: valóban felfedeztek egy biztonságos módot egy egykiszolgálós adatbázis előfeldolgozására, így bárki titokban gyűjthet információkat. „Ez valóban meghaladja mindazt, amit reméltünk” – mondta Yuval Ishai, az izraeli Technion kriptográfusa, aki nem vett részt ebben a munkában. Ennek az az eredménye, hogy „nem voltunk elég bátrak, hogy kérjünk” – mondta.

Titkos keresési sémájuk felépítése után a szerzők a valós célhoz, a privát internetes kereséshez fordultak, ami bonyolultabb annál, mint információdarabkákat adatbázisból kivonni, mondta Wichs. A privát keresési séma önmagában is lehetővé teszi a privát Google-szerű keresés egy változatát, de rendkívül munkaigényes: Ön saját maga futtatja a Google algoritmusát, és szükség esetén titokban lehívja az adatokat az internetről. Wichs szerint a valódi keresés, amikor elküld egy kérést, és hátradől, amíg a szerver gyűjti az eredményeket, valójában egy szélesebb körű megközelítés, az úgynevezett homomorf titkosítás célpontja, amely úgy álcázza az adatokat, hogy valaki más manipulálhassa azokat anélkül, hogy bármit is tudna róla. .

A tipikus homomorf titkosítási stratégiák ugyanazt a buktatót sújtják, mint a személyes információk visszakeresése, és minden kereséskor végigpörgetik az internet tartalmát. De a privát keresési módszerük állványként való felhasználásával a szerzők felépítettek egy új sémát, amely olyan számításokat futtat, amelyek jobban hasonlítanak az általunk mindennap használt programokra, rejtett információkat gyűjtve anélkül, hogy az egész internetet elsöpörnék. Ez növelné a hatékonyságot az internetes kereséseknél és minden olyan programnál, amelynek gyors adathozzáférésre van szüksége.

Míg a homomorf titkosítás a privát keresési séma hasznos kiterjesztése, Ishai azt mondta, hogy a privát információk visszakeresését tekinti az alapvetőbb problémának. A szerzők megoldása a „mágikus építőelem”, homomorf titkosítási stratégiájuk pedig természetes követés.

Egyelőre egyik séma sem használható gyakorlatilag: az előfeldolgozás jelenleg a szélsőségeken segít, amikor az adatbázis mérete a végtelen felé ugrik. De a tényleges telepítés azt jelenti, hogy ezek a megtakarítások nem valósulhatnak meg, és a folyamat túl sok időt és tárhelyet emészt fel.

Szerencsére, mondta Vaikuntanathan, a kriptográfusok hosszú múltra tekintenek vissza az eredmények optimalizálása terén, amelyek kezdetben nem voltak praktikusak. Ha a jövőbeli munkával ésszerűsíteni tudja a megközelítést, úgy véli, hogy az óriási adatbázisokból történő privát keresések elérhetőek lehetnek. „Mindannyian azt hittük, hogy itt ragadtunk” – mondta. "Dániel eredménye reményt ad."

Quanta felméréssorozatot végez közönségünk jobb kiszolgálása érdekében. Vidd a miénket számítástechnikai olvasói felmérés és ingyenesen nyerhetsz Quanta áru.