Goldwasser–Micali-cryptosysteem
Het eerste probabilistische publieke-sleutelversleutelingsschema, en het eerste dat bewijsbaar semantisch veilig was.
Shafi Goldwasser en Silvio Micali beschreven het in 1982, in hetzelfde werk waarin semantische veiligheid werd gedefinieerd. Het punt was dat deterministische versleuteling, zoals leerboek-RSA, lekt: dezelfde klaartekst geeft altijd dezelfde cijfertekst. Hier wordt elk bit apart versleuteld met verse willekeur, zodat twee versleutelingen van hetzelfde bericht totaal niet op elkaar lijken. De veiligheid berust op de moeilijkheid om te bepalen of een getal een kwadraat is modulo een samengestelde N.
De prijs is absurde uitzetting: elk klaartekstbit wordt een getal ter grootte van de modulus, duizenden bits. In de praktijk gebruikt niemand het. Het inzicht dat versleuteling gerandomiseerd moet zijn, vormde echter elk modern schema en droeg bij aan de Turing Award van 2012 voor de auteurs.