Criptossistema de Goldwasser–Micali
O primeiro esquema probabilístico de criptografia de chave pública e o primeiro com segurança semântica comprovada.
Shafi Goldwasser e Silvio Micali o descreveram em 1982, no mesmo trabalho que definiu a segurança semântica. A questão era que a criptografia determinística, como o RSA de livro-texto, vaza informação: o mesmo texto claro sempre gera o mesmo texto cifrado. Aqui cada bit é cifrado separadamente com aleatoriedade nova, de modo que duas cifragens da mesma mensagem não se parecem em nada. A segurança se apoia na dificuldade de dizer se um número é um quadrado módulo um composto N.
O preço é uma expansão absurda: cada bit do texto claro vira um número do tamanho do módulo, com milhares de bits. Ninguém o usa na prática. Já a ideia de que a cifragem precisa ser randomizada moldou todos os esquemas modernos e ajudou a render aos autores o Prêmio Turing de 2012.