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.