Goldwasser-Micali-Kryptosystem
Das erste probabilistische Public-Key-Verschlüsselungsverfahren und das erste mit bewiesener semantischer Sicherheit.
Shafi Goldwasser und Silvio Micali beschrieben es 1982 in derselben Arbeit, die die semantische Sicherheit definierte. Der Punkt: Deterministische Verschlüsselung wie das Lehrbuch-RSA verrät etwas, denn derselbe Klartext ergibt stets denselben Geheimtext. Hier wird jedes Bit einzeln mit frischem Zufall verschlüsselt, sodass zwei Verschlüsselungen derselben Nachricht völlig verschieden aussehen. Die Sicherheit beruht darauf, dass sich schwer entscheiden lässt, ob eine Zahl ein Quadrat modulo einer zusammengesetzten Zahl N ist.
Der Preis ist eine absurde Datenexpansion: Jedes einzelne Klartextbit wird zu einer Zahl von der Größe des Moduls, also Tausenden Bits. In der Praxis nutzt es niemand. Die Idee, dass Verschlüsselung randomisiert sein muss, prägte jedoch jedes moderne Verfahren und trug den Autoren 2012 den Turing-Preis ein.