Silvio Micali

Silvio Micali
Ilustracja
Silvio Micali (2010)
Państwo działania

 Włochy
 Stany Zjednoczone

Data i miejsce urodzenia

13 października 1954
Palermo

profesor
Specjalność: kryptografia, informatyka teoretyczna, teoria złożoności obliczeniowej, protokoły kryptograficzne
Alma Mater

Uniwersytet Rzymski „La Sapienza”,
Uniwersytet Kalifornijski w Berkeley

Doktorat

1983 – informatyka
Uniwersytet Kalifornijski w Berkeley
promotor: Manuel Blum

nauczyciel akademicki
Uczelnia

Massachusetts Institute of Technology

Stanowisko

profesor

Okres zatrudn.

od 1983

Nagrody

Nagroda Gödla (1993),
Nagroda Turinga (2012)

Strona internetowa

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.

W latach 80. XX wieku prace Micaliego i jego współpracowników przyczyniły się do oparcia kryptografii na teorii złożoności obliczeniowej. Wprowadzały one formalne 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.

Jego zainteresowania badawcze obejmują kryptografię, wiedzę zerową, generowanie ciągów pseudolosowych, bezpieczne protokoły, projektowanie mechanizmów i blockchain. W 2017 roku Micali założył Algorand(inne języki) – w pełni zdecentralizowany, bezpieczny i skalowalny blockchain.

Kryptografia probabilistyczna

Jednym z klasycznych wkładów Micaliego była praca z Shafi Goldwasser nad szyfrowaniem probabilistycznym. Autorzy wprowadzili model szyfrowania, w którym zaszyfrowanie wiadomości wykorzystuje losowość, i sformułowali dla niego formalne definicje bezpieczeństwa. Udowodnili, że przy odpowiednich założeniach o trudności pewnych problemów przeciwnik o wielomianowo ograniczonych zasobach obliczeniowych nie potrafi wydobyć z szyfrogramu częściowej informacji o wiadomości ani odróżnić szyfrogramów dwóch wybranych przez siebie 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 Charles Rackoff(inne języki) 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 odegrała istotną rolę w rozwoju kryptografii i teorii złożoności obliczeniowej.

Według ACM dowody z wiedzą zerową były „uderzającą nową ideą filozoficzną”, która dostarczyła podstawowego języka do opisu bezpieczeństwa protokołów kryptograficznych przez kontrolę wycieku wiedzy. Poza kryptografią dowody interaktywne mogą być weryfikowane znacznie szybciej niż dowody klasyczne.

Bezpieczne protokoły i generatory pseudolosowe

Wspólnie z Odedem Goldreichem(inne języki) i Avim Wigdersonem Micali podał algorytm działający w czasie wielomianowym, który dla opisu dowolnej gry z niepełną informacją i dowolnej liczby graczy tworzy protokół jej rozgrywania niewyjawiający żadnej częściowej informacji, o ile większość graczy jest uczciwa. Według ACM ta praca, a także praca Michaela Ben-Ora, Goldwasser i Wigdersona wykazały, że każde obliczenie wielostronne można przeprowadzić bezpiecznie, nie ujawniając uczestnikom więcej wiedzy, niż wymaga zamierzony wynik.

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(inne języki) wprowadził weryfikowalne funkcje losowe, łączące pseudolosowość z publicznie sprawdzalnym dowodem poprawności wartości funkcji.

Nagrody i wyróżnienia

Micali otrzymał Nagrodę Turinga za 2012 rok, przyznaną wspólnie z Shafi Goldwasser i ogłoszoną przez Association for Computing Machinery (ACM) w marcu 2013. Komunikat ACM wskazywał 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. W 2004 roku otrzymał nagrodę RSA w dziedzinie matematyki. Micali jest członkiem m.in. National Academy of Sciences, National Academy of Engineering i American Academy of Arts and Sciences. W 2017 roku otrzymał tytuł ACM Fellow.

Znaczenie

Według ACM Goldwasser i Micali zapoczątkowali dziedzinę bezpieczeństwa dowodliwego (provable security), która położyła matematyczne podstawy nowoczesnej kryptografii. Prezes ACM Vint Cerf wskazywał w 2013 roku, że ich pojęcia bezpieczeństwa spełniają szyfry stosowane w przeglądarkach internetowych, a także metoda szyfrowania numerów kart kredytowych podczas zakupów w internecie.

Według ACM, formalizując pogląd, że bezpieczeństwo kryptograficzne musi mieć charakter obliczeniowy, a nie absolutny, przekształcili kryptografię ze sztuki w naukę, a ich definicja bezpieczeństwa szyfrowania jako „gry” z udziałem przeciwnika stała się znakiem rozpoznawczym nowoczesnej kryptografii.

Wybrane publikacje