Criptosistema de Goldwasser–Micali
El primer esquema de cifrado probabilístico de clave pública y el primero con seguridad semántica demostrada.
Shafi Goldwasser y Silvio Micali lo describieron en 1982, en el mismo trabajo que definió la seguridad semántica. El problema de fondo era que el cifrado determinista, como RSA de libro de texto, filtra información: el mismo texto claro produce siempre el mismo texto cifrado. Aquí cada bit se cifra por separado con aleatoriedad nueva, de modo que dos cifrados del mismo mensaje no se parecen en nada. La seguridad descansa en lo difícil que es saber si un número es un cuadrado módulo un N compuesto.
El precio es una expansión absurda: cada bit de texto claro se convierte en un número del tamaño del módulo, miles de bits. Nadie lo usa en la práctica. La idea de que el cifrado debe ser aleatorio, en cambio, marcó todos los esquemas modernos y contribuyó al Premio Turing de sus autores en 2012.