Криптосистема Гольдвассер — Микали
Первая вероятностная схема шифрования с открытым ключом и первая с доказанной семантической стойкостью.
Шафи Гольдвассер и Сильвио Микали описали её в 1982 году в той же работе, где определили семантическую стойкость. Идея в том, что детерминированное шифрование вроде «учебного» RSA протекает: один и тот же открытый текст всегда даёт один и тот же шифртекст. Здесь каждый бит шифруется отдельно со свежей случайностью, поэтому два шифрования одного сообщения ничем не похожи. Стойкость опирается на сложность определения того, является ли число квадратом по составному модулю N.
Цена — абсурдное раздувание: каждый бит открытого текста превращается в число размером с модуль, то есть в тысячи бит. На практике этой схемой никто не пользуется. Зато идея о том, что шифрование обязано быть рандомизированным, определила все современные схемы и помогла авторам получить премию Тьюринга 2012 года.