Silvio Micali (ur. 13 października 1954 w Palermo) – włosko-amerykański informatyk teoretyczny i kryptograf, profesor Massachusetts Institute of Technology (MIT). Jest znany z prac nad podstawami nowoczesnej kryptografii, dowodami z wiedzą zerową, generatorami pseudolosowymi, bezpiecznym obliczaniem wielostronnym i bezpiecznymi protokołami kryptograficznymi. Wspólnie z Shafi Goldwasser został laureatem Nagrody Turinga za 2012 rok za wkład w stworzenie podstaw teorii kryptografii złożonościowej.

Micali należy do badaczy, którzy w latach 80. XX wieku przekształcili kryptografię z dziedziny opartej głównie na konstrukcjach praktycznych w ścisłą teorię matematyczno-informatyczną. Jego prace wprowadzały definicje bezpieczeństwa, redukcje do założeń obliczeniowych oraz metody dowodzenia własności protokołów kryptograficznych.

Życiorys i kariera Micali ukończył matematykę na Uniwersytecie Rzymskim „La Sapienza” w 1978 roku, a doktorat z informatyki uzyskał na Uniwersytecie Kalifornijskim w Berkeley w 1983 roku pod kierunkiem Manuela Bluma; rozprawa nosiła tytuł Randomness Versus Hardness. Od 1983 roku jest związany z MIT, gdzie został profesorem informatyki w Department of Electrical Engineering and Computer Science oraz badaczem w Computer Science and Artificial Intelligence Laboratory.

W jego dorobku znajdują się prace z kryptografii, teorii złożoności obliczeniowej, algorytmów probabilistycznych, mechanizmów aukcyjnych i technologii rozproszonych. W 2017 roku Micali założył , projekt dotyczący zdecentralizowanych protokołów konsensusu i infrastruktury blockchain.

Kryptografia probabilistyczna Jednym z klasycznych wkładów Micaliego była praca z Shafi Goldwasser nad szyfrowaniem probabilistycznym. Autorzy pokazali, że bezpieczny schemat szyfrowania powinien uwzględniać losowość i precyzyjną definicję bezpieczeństwa, w której przeciwnik, obliczeniowo ograniczony, nie potrafi odróżniać szyfrogramów ani wydobywać częściowej informacji o wiadomości.

Podejście to stało się podstawą nowoczesnego rozumienia bezpieczeństwa semantycznego i bezpieczeństwa przez nierozróżnialność. W odróżnieniu od wcześniejszego, często nieformalnego opisu „trudności złamania” szyfru, prace Goldwasser i Micaliego umożliwiły formułowanie twierdzeń typu: jeśli dane założenie obliczeniowe jest prawdziwe, to schemat spełnia określoną definicję bezpieczeństwa.

Dowody z wiedzą zerową Micali, Goldwasser i wprowadzili pojęcie interaktywnych dowodów z wiedzą zerową. W takim protokole dowodzący przekonuje weryfikatora o prawdziwości twierdzenia, nie ujawniając żadnej dodatkowej informacji poza samą prawdziwością tego twierdzenia. Koncepcja ta stała się jednym z najbardziej wpływowych pojęć współczesnej kryptografii i teorii złożoności.

Dowody z wiedzą zerową znalazły zastosowania w uwierzytelnianiu, protokołach identyfikacji, bezpiecznym obliczaniu, prywatności i późniejszych systemach kryptograficznych. Ich znaczenie wykracza poza praktyczną kryptografię, ponieważ zmieniły rozumienie relacji między dowodem, informacją i obliczalną weryfikacją.

Bezpieczne protokoły i generatory pseudolosowe Wspólnie z i Avim Wigdersonem Micali pracował nad bezpiecznym obliczaniem wielostronnym, czyli protokołami, w których kilka stron może obliczyć wspólną funkcję swoich danych wejściowych bez ujawniania ich poza tym, co wynika z wyniku obliczenia. Ten kierunek stał się jednym z fundamentów teorii protokołów kryptograficznych.

Micali współtworzył także wyniki dotyczące generatorów pseudolosowych i funkcji pseudolosowych. Prace te wiążą losowość obliczeniową z założeniami o trudności problemów i są ważne zarówno dla kryptografii, jak i dla ogólnej teorii obliczeń losowych. W późniejszej pracy z Michaelem Rabinem i Salilem Vadhanem wprowadził weryfikowalne funkcje losowe, łączące pseudolosowość z publicznie sprawdzalnym dowodem poprawności wartości funkcji.

Nagrody i wyróżnienia Najważniejszym wyróżnieniem Micaliego jest Nagroda Turinga za 2012 rok, przyznana wspólnie z Shafi Goldwasser i ogłoszona przez Association for Computing Machinery (ACM) w marcu 2013. Uzasadnienie ACM wskazywało na ich przełomowy wkład w kryptografię, w tym w szyfrowanie probabilistyczne, dowody z wiedzą zerową, protokoły kryptograficzne i teorię bezpieczeństwa opartą na złożoności obliczeniowej.

W 1993 roku, razem z Shafi Goldwasser i Charlesem Rackoffem oraz autorami równolegle nagrodzonej pracy o systemach Arthura-Merlina, otrzymał Nagrodę Gödla za artykuł o złożoności wiedzy w interaktywnych systemach dowodowych. Micali jest członkiem m.in. National Academy of Sciences, National Academy of Engineering i American Academy of Arts and Sciences. W 2017 roku został wybrany członkiem Association for Computing Machinery.

Znaczenie Znaczenie Micaliego polega przede wszystkim na współtworzeniu języka, w którym współczesna kryptografia formułuje swoje cele i dowody bezpieczeństwa. Takie pojęcia jak bezpieczeństwo semantyczne, wiedza zerowa, pseudolosowość i bezpieczne obliczanie wielostronne stały się standardowymi elementami teorii, a także podstawą wielu późniejszych zastosowań praktycznych.

Jego dorobek dobrze pokazuje przesunięcie kryptografii w stronę nauki o formalnych protokołach: zamiast oceniać system wyłącznie przez brak znanych ataków, definiuje się model przeciwnika, cel bezpieczeństwa i redukcję do określonego problemu obliczeniowego. Ten styl argumentacji jest obecnie typowy dla projektowania i analizy wielu systemów kryptograficznych.

Wybrane publikacje Manuel Blum, Silvio Micali, How to generate cryptographically strong sequences of pseudorandom bits, SIAM Journal on Computing 13(4), 1984, s. 850–864, doi:10.1137/0213053. Shafi Goldwasser, Silvio Micali, Probabilistic encryption, Journal of Computer and System Sciences 28(2), 1984, s. 270–299, doi:10.1016/0022-0000(84)90070-9. Oded Goldreich, Shafi Goldwasser, Silvio Micali, How to construct random functions, Journal of the ACM 33(4), 1986, s. 792–807, doi:10.1145/6490.6503. Oded Goldreich, Silvio Micali, Avi Wigderson, How to play any mental game, Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987, s. 218–229, doi:10.1145/28395.28420. Shafi Goldwasser, Silvio Micali, Charles Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing 18(1), 1989, s. 186–208, doi:10.1137/0218012. Silvio Micali, Michael Rabin, Salil Vadhan, Verifiable random functions, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999, s. 120–130, doi:10.1109/SFFCS.1999.814584.

Zobacz też dowód z wiedzą zerową informatyka teoretyczna kryptografia Nagroda Turinga

Przypisy

Kategoria:Włoscy informatycy Kategoria:Amerykańscy informatycy Kategoria:Amerykańscy kryptolodzy Kategoria:Laureaci Nagrody Turinga Kategoria:Laureaci Nagrody Gödla Kategoria:Członkowie National Academy of Sciences Kategoria:Członkowie Amerykańskiej Akademii Sztuk i Nauk Kategoria:Absolwenci i studenci Uniwersytetu w Rzymie Kategoria:Absolwenci Uniwersytetu Kalifornijskiego w Berkeley Kategoria:Ludzie urodzeni w Palermo Kategoria:Urodzeni w 1954