A kriptográfus, aki biztosítja, hogy megbízhassunk számítógépeinkben | Quanta Magazin

Yael Tauman Kalai úttörő elméleti informatikus, aki lenyűgöző díjakat nyert, és megváltoztatta az emberek internetről alkotott véleményét. De gyerekként nem volt éppen minta diák.

– Zavarkeverő voltam – mondta. „Alapvetően – nem egészen, de alapvetően – kirúgtak a középiskolából.”

Kalai Tel Avivban, Izraelben született és nőtt fel tudományos családban. Édesapja, Yair Tauman közgazdász és játékteoretikus. A gimnáziumi órái unták – az egyik bejelentőlap mintegy 150 iskolai hiányzást dokumentált, emlékszik vissza, mivel inkább vízisízéssel és társasági élettel töltötte az idejét. De elemző készsége mindig ott volt.

„Amikor a szüleim nem engedtek kimenni, gyakran az egyetlen módja annak, hogy apám beleegyezzen, az volt, hogy azt mondtam neki: „Rendben, adj egy matematikai rejtvényt. Bármennyire is nehéz, de ha megoldom, megyek.” Általában ment.

A matematika iránti szunnyadó szerelme végül az egyetemen ébredt fel, amikor elkezdte felismerni annak szépségét. Végül rájött, hogy ezt a matematikát felhasználhatja számítógépekkel, és különösen az információbiztonsággal. Munkája ma már a matematika és a számítástechnika területein is átnyúlik, és ötletei alapjai voltak annak, hogyan védjük és ellenőrizzük a számításokat a digitális korban. Az elmúlt két évtizedben azon dolgozott, hogy biztosítsa okostelefonjaink, felhőkapcsolataink és még kriptovalutáink integritását is. Jelenleg a Microsoft kutatója és a Massachusetts Institute of Technology adjunktusa, a közelmúltban elnyerte a Computer Machinery Association for Computer Machinery rangos számítástechnikai ACM-díját „a számítástechnika igazolható delegálásában elért áttörésért és a kriptográfiához való alapvető hozzájárulásáért”. Legújabb munkája is a jövőbe tekint, miközben azon gondolkodik, hogyan befolyásolhatják a kvantumszámítógépek a biztonsági környezetet.

Quanta beszélt Kalaival a titkok kiszivárogtatásáról, a felhő igazolásáról és a kvantumszámítástechnika funkcionalitásáról. Az interjút az egyértelműség kedvéért sűrítettük és szerkesztettük.

Hogyan lett középiskolai bajkeverőből akadémikus?

Mindig is tudtam, hogy szeretem a matematikát, de a gimnáziumi matematika semmilyen szempontból nem volt érdekes. Aztán elmentem matematikát tanulni az egyetemre, és el voltam ragadtatva. Életemben először ültem és tanultam megállás nélkül, reggeltől estig. Eufóriában voltam. És meg kell mondanom, egy kicsit ideges voltam, mert azt gondoltam: „Nem hiszem el, hogy sokkal fiatalabb koromban élvezhettem ezt!”

Mi volt az, ami magával ragadott a matematikában?

Nagyon letisztult, elegáns és elvont. És a matematikában egyes fogalmak ellentmondanak az intuitívnak; Emlékszem, úgy éreztem, hogy a tanulmányozása megváltoztatott engem, mint embert. Megtanulsz alázatosnak lenni, mert újra és újra megtanulod, hogy a megérzéseid rosszak.

De amikor egy jó kutatási kérdést kerestem, minden egyre növekvőnek tűnt. Így hát elkezdtem az informatika felé haladni. És pont a kriptográfia hiányzott, mert valós problémákkal foglalkozik. Ma már mindenhol használják a kriptográfiát. Arra szolgál, hogy az általunk küldött üzenetek bizalmasak és hitelesek legyenek. Amikor valakivel SMS-t küldök, honnan tudhatom, hogy a kapott üzenetet elküldték? Honnan tudhatom, hogy az a személy, aki azt állítja, hogy ő küldte az üzenetet, valóban az küldte? Mit jelent ezt tudni? A fogalmak nagyon filozófiaiak, és az, ahogy matematikailag modellezzük, nagyon szép. Számomra eltalálta a matek tisztaságát és alkalmazhatóságát egyaránt.

Milyen titkosítási problémákon dolgozott?

A diplomamunkám a „Hogyan szivárogtassunk ki titkot” címet viselte. Itt van a probléma: Tudjuk, hogyan kell digitálisan aláírni – hogy azt mondjuk: „Én írtam ezt az üzenetet.” De mondjuk szeretnék aláírni valamit MIT professzorként, de nem akarom, hogy az emberek megtudják, hogy én vagyok az? Így a titok tartogat némi vizet, mert tudod, hogy egy MIT professzor írta alá, de nem tudod, hogy ki.

Ezt egy gyűrűs aláírásnak nevezett dologgal oldottuk meg, amelyet a számítástechnikában a tanúk által megkülönböztethetetlen bizonyításoknak nevezett fogalom ihletett. Tegyük fel, hogy van egy állítás, és kétféle módon bizonyíthatod. Azt mondjuk, hogy az állítás helyességének két „tanúja” van – mindegyik bizonyíték. A tanúk által megkülönböztethetetlen bizonyíték ugyanúgy néz ki, függetlenül attól, hogy melyiket használja: elrejti, hogy melyik tanúval indult.

A gyűrűs aláírások hasonlóak. A potenciális titok-kiszivárogtatók csoportjában mindenki úgy gondolhatja, hogy van titkos kulcsa. A gyűrűs aláírás pedig lényegében azt bizonyítja, hogy ezt az üzenetet valaki az egyik titkos kulccsal írta alá, de nem derül ki, hogy melyik titkos kulcsot ismeri. Elrejti, hogy kinek a titkos kulcsát használták.

Használja-e valaha egy intézmény ezt a rendszert?

Ez a szép és félelmetes dolog – meg tudom csinálni anélkül, hogy más részt vesz benne. A csoport tagjaként aláírhatok a csoport engedélye nélkül. Nem világos, hogy ez egy funkció vagy hiba, de az egyértelmű, hogy tudományos felfedezésről van szó. Gyűrűs aláírásokat használtak – van egy monero nevű kriptovaluta, amely azt állítja, hogy a tranzakciók titkosítására használják. De őszintén szólva nem igazán tudom, ki használja a munkánkat. Az igazság az, hogy túl elfoglalt vagyok ahhoz, hogy kövessem.

Hogyan fejlődött az Ön munkája eszközeink biztonságának elemzésévé?

A 2000-es évek elején Ph.D. fokozatom végén dolgoztam Shafi Goldwasserrel az MIT-n. Az emberek éppen a felhőalapú számítástechnikáról kezdtek beszélni, amelyet ma már minden nap használunk. Korábban volt egy hatalmas asztalod, ahol mindent elvégeztek. A nagy adatgyűjtés növekedésével a számítások költségesebbé váltak, és elkezdték távolról végezni. Az ötlet az, hogy van egy hatékony felhő, amely elvégzi a számításokat. De előfordulhat, hogy nem bízik a felhőplatformban, így honnan tudhatja, hogy megfelelően végzik-e a számítást? Néha ösztönözhet a csalásra, mert a számítás nagyon költséges lehet. És bizonyos beállításoknál aggódhat a véletlenszerű hibák miatt. Tehát valóban bizonyítékot szeretne kapni, hogy ez a számítás helyes.

De a bizonyítások általában nagyon hosszúak, és a gyenge eszközök nem tudják ellenőrizni a hosszú bizonyításokat. Még olyan eszközök esetében is, amelyek képesek, ez nagyon költséges. Tehát van mód arra, hogy csökkentsük a bizonyítékokat? Információelméletileg nem. De kiderül, hogy kriptográfiai eszközök használatával ehelyett tömör tanúsítványokat generálhatunk, amelyeket nagyon-nagyon nehéz meghamisítani. Ezeket tömör, nem interaktív argumentumoknak vagy SNARG-oknak nevezzük. Ez tényleg nem bizonyíték. De amíg nem tudsz megoldani egy olyan problémát, amelyet mi, kriptográfusok nagyon nehéznek tartunk, mint például a nagy számok faktorálása, addig nem hamisíthatod meg a tömör bizonyítékokat.

Hogyan születtek ezek a bizonyítékok?

1985-ben kezdődött Shafi Goldwasser, Silvio Micali és Charles Rackoff, akik együtt vezették be az interaktív bizonyítások fogalmát. Korábban, amikor az emberek a bizonyításokra gondoltak, arra gondoltak, hogy sorokat írjanak az adatokhoz, és Ön elolvashatja és ellenőrizheti, hogy helyesek-e vagy sem. Goldwasser, Micali és Rackoff egy teljesen más módszert vezetett be valaminek a bizonyítására: az interakciót. Van egy bizonyító és van egy ellenőrző, és oda-vissza üzeneteket váltanak. Ezután a hitelesítő eldönti, hogy meggyőződött-e vagy sem.

Hadd mondjak egy példát valamire, amit könnyebb interaktív bizonyításként csinálni, mint klasszikus bizonyítást. Tegyük fel, hogy sakkozunk. Tegyük fel, hogy be akarom bizonyítani neked, hogy van egy nyerő stratégiám. Nem számít, milyen mozdulatokat teszel, akkor is nyerni fogok. Hogyan bizonyítsam ezt be neked?

Klasszikusan ez egy hatalmas bizonyíték, mert be kell bizonyítanom, hogy a stratégiám minden lehetséges lépéskombinációval szemben működik. De kiderült, hogy az interakción keresztül nagyon tömören meg tudom csinálni. Ha nem hiszi, hogy van nyerő stratégiám, játsszunk. Megmutatom, hogy én nyerek. Természetesen ez önmagában nem meggyőző – csak azért, mert egyszer nyerhetek ellened, még nem jelenti azt, hogy bárki ellen is nyerhetek. Szóval adj egy nagymestert. Nyerni fogok egy nagymester ellen. Ez kezdi demonstrálni az interakció erejét.

De az interaktív bizonyíték hátránya, hogy nem vihető át. Tegyük fel, hogy adsz nekem egy százdolláros bankjegyet, és interakcióval bebizonyítod, hogy az valóban 100 dollárt ér. Azt akarom, hogy továbbadhassam. Másnak akarom adni, aki másnak adja. De ha csak egy interaktív bizonyítékom lenne, az semmit sem jelent; Nem adhatom másnak. Szóval az a szép a SNARG-ban, hogy odaadhatod valaki másnak.

Mint egy eredetiségigazolás?

Pontosan. Manapság a blokkláncokat használják a tranzakciók ellenőrzésére. Amikor megjelent a blokklánc, azt mondtam a tanítványaimnak, hogy küldjük el a bitcoin fejlesztőjét, Satoshi Nakamotót virágokkal és csokoládéval, mert tényleg annyira relevánssá tette a munkánkat.

Tehát hogyan távolíthatja el az átruházható tanúsítványok létrehozásához szükséges interakciót?

A titkosítással. Hadd próbáljak megérzést adni ennek működéséhez. Interaktív bizonyításainkban az ellenőrző általában csak véletlenszerűséget küld a bizonyítónak – ezt úgy is gondolhatja, hogy a hitelesítő véletlenszerűen ellenőrzi a bizonyítást. Aztán Amos Fiatnak és Adi Shamirnak támadt egy ötlete: Miért van szüksége erre a hitelesítőre, ha csak véletlenszerűséget küld? Talán lecserélhetjük ezt az ellenőrzőt valamilyen függvényre, például valami hash függvényre – ez egy véletlenszerűnek tűnő függvény, és nagyon fontos építőelem a kriptográfiában.

És kiderül, hogy igen, megtehetjük. Ma ezt folyamatosan csinálják. Ha iPhone-ja vagy Android-eszköze van, a Fiat-Shamir paradigmát használja, amikor telefonja távoli szerverekhez csatlakozik, ami gyakran előfordulhat a nap folyamán. És ezt a paradigmát használjuk a tömör bizonyítékok megalkotására, amelyek igazolják, hogy a távoli számítások helyesek.

Arról beszélt, hogy a gépeknek „kvantum utáni biztonságosaknak” kell lenniük. Az mit jelent?

A kvantumszámítógépek, ha valóban nagy léptékben léteznek, sokkal erősebbek lesznek, mint a klasszikus számítógépek. A klasszikus számítógépek bitekben dolgoznak, amelyek 0 vagy 1. A kvantumszámítógépekben vannak kvantumbitek, amelyek szuperpozícióban vannak 0 és 1 között. És ezek a qubitek összefonódnak, ami azt jelenti, hogy befolyásolják egymást. Ez adja igazán a kvantumszámítógépek erejét.

A jövőben nem biztos, hogy mindenkinek van kvantumasztala. Lehet, hogy van néhány drága kvantumeszköz, amely távoli számításokat végez az Ön helyett. Tegyük fel, hogy egy drága számítást szeretne delegálni az egyik ilyen kvantumeszközre, és szüksége van egy tanúsítványra, amely igazolja a kimenet helyességét – hogyan igazolja a kvantumszámítógépek helyességét? Most, hogy kvantumbiteket akarunk használni, nem klasszikus biteket, minden megváltozik, különösen akkor, ha azt akarom, hogy az ellenőrző egy klasszikus számítógép legyen.

2018-ban áttörés történt eredményez egy berkeley-i diák, Urmila Mahadev. Ő volt az első, aki klasszikus, számítástechnikailag biztonságos bizonyítékot mutatott be a kvantumszámítások ellenőrzésére.

Tehát használhat egy klasszikus számítógépet a kvantumszámítások ellenőrzésére? Ez lehetetlennek hangzik!

Hát nem csodálatos? A programbizottságban voltam, amikor Urmila megjelentette a dolgozatát, és egész éjszaka azt néztem – mennyi koffeint ittam! Elképedtem. Akkoriban teljes kvantumbábu voltam. Megértettem a kriptográfiai részt, de eltartott egy ideig, míg megértettem, hogy ez hogyan fér össze a kvantumrésszel. És gyönyörű volt.

A klasszikusról a kvantumszámításra való átállás meredek tanulási görbeként hangzik.

Tudom. Valójában semmit sem tudok a fizikáról, és rengeteg kvantumfizikai intuíció van benne. Nem értem a legalapvetőbb fogalmakat, mint például az energia és a hőmérséklet. Néha diákokkal dolgozom, és amint a kvantumszámításról beszélünk, én leszek a diák. Kezdek egy kicsit jobban megérezni az intuíciót. És azt kell mondanom, hogy nagyon élvezem, hogy ott ülök a kvantuminformációkról szóló tankönyvvel. Nincs is jobb diáknak lenni.