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.