ゴールドワッサー–ミカリ暗号
最初の確率的公開鍵暗号方式であり、意味論的安全性が初めて証明された方式。
シャフィ・ゴールドワッサーとシルビオ・ミカリが1982年に、意味論的安全性を定義した研究の中で発表した。狙いは、教科書的なRSAのような決定的暗号化は情報を漏らす、という問題の解消だった。同じ平文は常に同じ暗号文になるからだ。この方式では各ビットを毎回新しい乱数で個別に暗号化するので、同じメッセージの二つの暗号文は似ても似つかない。安全性の根拠は、合成数Nを法として、ある数が平方数かどうかを見分ける問題の困難さにある。
代償は途方もないデータ膨張で、平文の1ビットが法と同じ大きさ、つまり数千ビットの数になる。実際に使う人はいない。しかし「暗号化はランダム化されていなければならない」という発想は、あらゆる現代の方式を形作り、二人が2012年にチューリング賞を受ける一因にもなった。