Goldwasser–Micali cryptosystem
The first probabilistic public-key encryption scheme, and the first proven semantically secure.
Shafi Goldwasser and Silvio Micali described it in 1982, in the same work that defined semantic security. The point was that deterministic encryption such as textbook RSA leaks: the same plaintext always yields the same ciphertext. Here each bit is encrypted separately with fresh randomness, so two encryptions of the same message look nothing alike. Security rests on the difficulty of telling whether a number is a square modulo a composite N.
The price is absurd expansion: every single plaintext bit becomes a number the size of the modulus, thousands of bits. Nobody uses it in practice. The idea that encryption must be randomized, however, shaped every modern scheme and helped earn its authors the 2012 Turing Award.