Kryptograf, który zapewnia, że ​​możemy ufać naszym komputerom | Magazyn Quanta

Yael Tauman Kalai jest pionierem informatyki-teoretykiem, który zdobył imponujące nagrody i zmienił sposób, w jaki ludzie myślą o Internecie. Ale jako dziecko nie była wzorową uczennicą.

„Byłam rozrabiaką” – powiedziała. „W zasadzie – niezupełnie, ale w zasadzie – wyrzucono mnie ze szkoły średniej”.

Kalaj urodził się i wychował w Tel Awiwie w rodzinie akademickiej. Jej ojciec, Yair Tauman, jest ekonomistą i teoretykiem gier. Jej lekcje w szkole średniej nudziły ją — wspomina, że ​​jedna karta ocen dokumentowała około 150 nieobecności w szkole, ponieważ wolała spędzać czas na nartach wodnych i towarzysko. Ale jej zdolności analityczne były zawsze obecne.

„Kiedy rodzice nie pozwalali mi wychodzić, często jedynym sposobem, aby mój tata się zgodził, było powiedzenie mu: „OK, daj mi zagadkę matematyczną”. Tak mocno, jak chcesz, ale jeśli rozwiążę, idę”. Zwykle szła.

Jej uśpiona miłość do matematyki w końcu obudziła się na studiach, kiedy zaczęła dostrzegać jej piękno. W końcu odkryła, że ​​może wykorzystać tę matematykę w komputerach, a konkretnie w zabezpieczaniu informacji. Obecnie jej praca obejmuje dziedziny matematyki i informatyki, a jej pomysły były fundamentalne dla tego, jak chronimy i weryfikujemy obliczenia w erze cyfrowej. Przez ostatnie dwie dekady pracowała nad zapewnieniem integralności naszych smartfonów, połączeń w chmurze, a nawet kryptowalut. Obecnie badaczka w firmie Microsoft i adiunkt w Massachusetts Institute of Technology, niedawno zdobyła prestiżową nagrodę ACM w dziedzinie informatyki przyznawaną przez Association for Computer Machinery za „przełom w weryfikowalnym delegowaniu obliczeń i fundamentalny wkład w kryptografię”. Jej najnowsza praca również patrzy w przyszłość, rozważając, w jaki sposób komputery kwantowe mogą wpłynąć na krajobraz bezpieczeństwa.

Quanta rozmawiał z Kalai o ujawnianiu tajemnic, weryfikowaniu chmury i funky obliczeń kwantowych. Wywiad został skrócony i zredagowany dla przejrzystości.

Jak przeszedłeś od licealnego awanturnika do naukowca?

Zawsze wiedziałem, że kocham matematykę, ale matematyka w szkole średniej nie była w żaden sposób interesująca. Potem poszłam na studia matematyczne i byłam zachwycona. Po raz pierwszy w życiu siedziałem i uczyłem się bez przerwy, od rana do wieczora. Byłem w euforii. I muszę powiedzieć, że byłem trochę zdenerwowany, ponieważ pomyślałem: „Nie mogę uwierzyć, że mogłem się tym cieszyć, kiedy byłem dużo młodszy!”

Co było takiego w matematyce, że cię urzekło?

Jest bardzo czysty, elegancki i abstrakcyjny. A niektóre koncepcje w matematyce są sprzeczne z intuicją; Pamiętam uczucie, że studiowanie tego zmieniało mnie jako osobę. Uczysz się pokory, ponieważ wciąż na nowo dowiadujesz się, że twoje przeczucia są błędne.

Ale kiedy szukałem dobrego pytania badawczego, wszystko wydawało się stopniowe. Zacząłem więc kierować się w stronę informatyki. A kryptografia była dokładnie tym, czego mi brakowało, ponieważ zajmuje się problemami świata rzeczywistego. Dziś kryptografia jest używana wszędzie. Służy do zapewnienia poufności i autentyczności wysyłanych przez nas wiadomości. Kiedy piszę z kimś SMS-a, skąd mam wiedzieć, że otrzymana wiadomość jest wiadomością, która została wysłana? Skąd mam wiedzieć, że osoba, która twierdzi, że wysłała wiadomość, jest tą, która ją faktycznie wysłała? Co to znaczy wiedzieć, że? Koncepcje są bardzo filozoficzne, a sposób, w jaki modelujemy je matematycznie, jest naprawdę piękny. Dla mnie to strzał w dziesiątkę, zarówno czystość matematyki, jak i możliwość zastosowania.

Nad jakimi problemami kryptograficznymi pracowałeś?

Moja praca magisterska nosiła tytuł „Jak ujawnić sekret”. Oto problem: wiemy, jak podpisać cyfrowo — powiedzieć: „To ja napisałem tę wiadomość”. Ale powiedzmy, że chcę coś podpisać jako profesor MIT, ale nie chcę, żeby ludzie wiedzieli, że to ja? W ten sposób tajemnica ma trochę wody, ponieważ wiesz, że podpisał ją profesor MIT, ale nie wiesz kto.

Rozwiązaliśmy ten problem za pomocą czegoś, co nazwaliśmy sygnaturami pierścieniowymi, które zostały zainspirowane pojęciem w informatyce zwanym dowodami nie do odróżnienia od świadków. Powiedzmy, że istnieje stwierdzenie i dwa różne sposoby jego udowodnienia. Mówimy, że jest dwóch „świadków” prawdziwości tego stwierdzenia — każdy z dowodów. Dowód, którego nie można odróżnić od świadka, wygląda tak samo bez względu na to, którego użyjesz: ukrywa, od którego świadka zacząłeś.

Podpisy pierścieniowe są podobne. W grupie potencjalnych „wycieków tajemnic” możesz myśleć o każdej osobie jako posiadającej tajny klucz. A podpis na pierścieniu zasadniczo dowodzi, że ta wiadomość została podpisana przez kogoś z jednym z tajnych kluczy, ale nie ujawnia, który tajny klucz zna. Ukrywa czyj tajny klucz został użyty.

Czy instytucja kiedykolwiek używałaby tego systemu?

To jest w tym piękne i przerażające - mogę to zrobić bez udziału nikogo innego. Mogę podpisać się jako członek grupy bez zgody grupy. Nie jest jasne, czy jest to funkcja, czy błąd, ale jasne jest, że jest to odkrycie naukowe. Zastosowano podpisy pierścieniowe — istnieje kryptowaluta o nazwie monero, która mówi, że używa jej do zachowania prywatności transakcji. Ale szczerze mówiąc, tak naprawdę nie wiem, kto korzysta z naszej pracy. Prawda jest taka, że ​​jestem zbyt zajęty, żeby to śledzić.

Jak Twoja praca przekształciła się w analizę bezpieczeństwa naszych urządzeń?

Na początku lat 2000. kończyłem doktorat, pracując z Shafim Goldwasserem na MIT. Dopiero teraz zaczęto mówić o przetwarzaniu w chmurze, z którego teraz korzystamy na co dzień. Wcześniej miałeś ogromny pulpit, na którym wszystko było zrobione. Wraz ze wzrostem gromadzenia dużych ilości danych obliczenia stały się bardziej kosztowne i zaczęto je wykonywać zdalnie. Pomysł polega na tym, że istnieje potężna chmura, która wykonuje dla ciebie obliczenia. Ale możesz nie ufać platformie chmurowej, więc skąd wiesz, że wykonują obliczenia poprawnie? Czasami może istnieć zachęta do oszukiwania, ponieważ obliczenia mogą być bardzo kosztowne. A potem w niektórych ustawieniach możesz martwić się przypadkowym błędem. Więc naprawdę chcesz dowodu, że to obliczenie jest poprawne.

Ale zazwyczaj dowody są bardzo długie, a słabe urządzenia nie mogą ich zweryfikować. Nawet w przypadku urządzeń, które to potrafią, jest to bardzo kosztowne. Czy jest więc sposób na zmniejszenie dowodów? Teoretycznie nie. Okazuje się jednak, że za pomocą narzędzi kryptograficznych możemy zamiast tego generować zwięzłe certyfikaty, które bardzo, bardzo trudno sfałszować. Są to tak zwane zwięzłe, nieinteraktywne argumenty lub SNARG. To nie jest dowód, naprawdę. Ale tak długo, jak nie możesz rozwiązać jakiegoś problemu, który my, kryptografowie, uważamy za bardzo trudny, na przykład faktoring dużych liczb, nie możesz sfałszować zwięzłych dowodów.

Jak powstały te dowody?

Zaczęło się w 1985 roku od Shafiego Goldwassera, Silvio Micali i Charlesa Rackoffa, którzy wspólnie wprowadzili pojęcie dowodów interaktywnych. Wcześniej, kiedy ludzie myśleli o dowodach, myśleli o pisaniu wierszy danych, które można przeczytać i sprawdzić, czy są poprawne, czy nie. Goldwasser, Micali i Rackoff wprowadzili zupełnie inny sposób udowodnienia czegoś: za pomocą interakcji. Jest weryfikator i weryfikator, a oni wymieniają wiadomości tam iz powrotem. Następnie weryfikator decyduje, czy są przekonani, czy nie.

Podam przykład czegoś, co łatwiej zrobić jako dowód interaktywny niż dowód klasyczny. Załóżmy, że gramy w szachy. Załóżmy teraz, że chcę ci udowodnić, że mam zwycięską strategię. Bez względu na to, jakie ruchy wykonasz, i tak wygram. Jak mam ci to udowodnić?

Klasycznie jest to ogromny dowód, ponieważ muszę udowodnić, że moja strategia działa przeciwko wszystkim możliwym kombinacjom ruchów. Okazuje się jednak, że dzięki interakcji mogę to zrobić bardzo zwięźle. Jeśli nie wierzysz, że mam zwycięską strategię, po prostu zagrajmy. Pokażę ci, że wygram. Oczywiście samo to nie jest przekonujące — to, że raz mogę wygrać z tobą, nie oznacza, że ​​mogę wygrać z kimkolwiek. Więc daj mi arcymistrza. Wygram z arcymistrzem. To zaczyna pokazywać siłę interakcji.

Ale wadą interaktywnego dowodu jest to, że nie można go przenosić. Powiedzmy, że dajesz mi studolarowy banknot i poprzez interakcję udowadniasz, że rzeczywiście jest on wart 100 dolarów. Chcę móc to przekazać. Chcę dać to komuś innemu, kto da to komuś innemu. Ale gdybym miał tylko dowód interaktywny, to nic nie znaczy; Nie mogę tego dać nikomu innemu. Tak więc fajną rzeczą w SNARG jest to, że możesz je przekazać komuś innemu.

Jak certyfikat autentyczności?

Dokładnie. Blockchains to główne miejsce, w którym są dziś używane do weryfikacji transakcji. Kiedy pojawił się blockchain, powiedziałem moim studentom, że powinniśmy wysłać twórcę bitcoina, Satoshi Nakamoto, kwiaty i czekoladki, ponieważ naprawdę sprawił, że nasza praca była tak istotna.

Jak więc usunąć interakcję w celu utworzenia tych zbywalnych certyfikatów?

Z kryptografią. Pozwól, że spróbuję dać ci intuicję, jak to działa. W naszych interaktywnych dowodach weryfikator zazwyczaj po prostu wysyła losowość do dowodzącego — można to sobie wyobrazić jako weryfikatora losowo sprawdzającego dowód. Wtedy Amos Fiat i Adi Shamir wpadli na pomysł: po co ci ten weryfikator, skoro on tylko wysyła losowość? Być może możemy zastąpić ten weryfikator jakąś funkcją, na przykład czymś, co nazywa się funkcją haszującą — jest to funkcja, która wygląda losowo i jest bardzo ważnym elementem konstrukcyjnym w kryptografii.

I okazuje się, że tak, możemy. Dziś robi się to cały czas. Jeśli masz iPhone'a lub Androida, używasz paradygmatu Fiata-Shamira, gdy Twój telefon łączy się ze zdalnymi serwerami, co może zdarzać się często w ciągu dnia. I to właśnie tego paradygmatu używamy do konstruowania zwięzłych dowodów potwierdzających, że zdalne obliczenia są poprawne.

Mówiłeś o maszynach, które muszą być „bezpieczne po kwantowo”. Co to znaczy?

Komputery kwantowe, jeśli rzeczywiście zaczną istnieć na dużą skalę, będą znacznie potężniejsze niż komputery klasyczne. Klasyczne komputery działają na bitach, które wynoszą 0 lub 1. W komputerach kwantowych masz bity kwantowe, które są w superpozycji między 0 a 1. Kubity te są splątane, co oznacza, że ​​wpływają na siebie nawzajem. To właśnie daje komputerom kwantowym ich moc.

W przyszłości może nie być tak, że każdy ma kwantowy komputer stacjonarny. Może istnieć kilka drogich urządzeń kwantowych, które wykonują dla ciebie zdalne obliczenia. Załóżmy, że chcesz delegować kosztowne obliczenia do jednego z tych urządzeń kwantowych i potrzebujesz certyfikatu, który weryfikuje poprawność danych wyjściowych — w jaki sposób poświadczasz poprawność komputerów kwantowych? Teraz, gdy chcemy używać bitów kwantowych, a nie bitów klasycznych, wszystko się zmienia, zwłaszcza gdy chcę, aby weryfikatorem był klasyczny komputer.

W 2018 roku nastąpił przełom dalsze przez studentkę z Berkeley, Urmilę Mahadev. Jako pierwsza pokazała klasyczny, bezpieczny obliczeniowo dowód do weryfikacji obliczeń kwantowych.

Więc możesz użyć klasycznego komputera do weryfikacji obliczeń kwantowych? To brzmi niemożliwie!

Czy to nie niesamowite? Byłem w komitecie programowym, kiedy Urmila opublikowała swój artykuł, i spędziłem całą noc, patrząc na to - ilość kofeiny, którą wypiłem! Byłem oszołomiony. W tamtym momencie byłem kompletnym kwantowym manekinem. Zrozumiałem część kryptograficzną, ale zrozumienie, jak to współgra z częścią kwantową, zajęło mi trochę czasu. I to było piękne.

Przejście od komputerów klasycznych do komputerów kwantowych brzmi jak stroma krzywa uczenia się.

Ja wiem. Właściwie nie wiem nic o fizyce i jest w tym dużo kwantowo-fizycznej intuicji. Nie rozumiem najbardziej podstawowych pojęć, takich jak energia i temperatura. Czasami pracuję ze studentami i gdy tylko mówimy o komputerach kwantowych, staję się studentem. Zaczynam zdobywać trochę więcej intuicji. I muszę powiedzieć, że bardzo mi się to podoba, siedzenie tam z podręcznikiem informacji kwantowej. Nie ma nic lepszego niż bycie studentem.