Kryptosystem Goldwasser–Micali
Pierwszy probabilistyczny schemat szyfrowania z kluczem publicznym i pierwszy z dowodem bezpieczeństwa semantycznego.
Shafi Goldwasser i Silvio Micali opisali go w 1982 roku, w tej samej pracy, która zdefiniowała bezpieczeństwo semantyczne. Chodziło o to, że szyfrowanie deterministyczne, jak podręcznikowy RSA, przecieka informację: ten sam tekst jawny zawsze daje ten sam szyfrogram. Tutaj każdy bit szyfruje się osobno ze świeżą losowością, więc dwa szyfrowania tej samej wiadomości wcale nie są do siebie podobne. Bezpieczeństwo opiera się na trudności rozpoznania, czy liczba jest kwadratem modulo liczba złożona N.
Cena jest absurdalna: każdy bit tekstu jawnego zamienia się w liczbę wielkości modułu, czyli tysiące bitów. W praktyce nikt tego nie używa. Idea, że szyfrowanie musi być losowe, ukształtowała jednak każdy nowoczesny schemat i pomogła autorom zdobyć Nagrodę Turinga w 2012 roku.