Cryptosystème de Goldwasser–Micali

Shafi Goldwasser et Silvio Micali l'ont décrit en 1982, dans le travail même qui définissait la sécurité sémantique. Le constat : le chiffrement déterministe, comme le RSA « de manuel », fuit, puisque le même message clair donne toujours le même chiffré. Ici, chaque bit est chiffré séparément avec un aléa neuf, si bien que deux chiffrements du même message ne se ressemblent en rien. La sécurité repose sur la difficulté de décider si un nombre est un carré modulo un entier composé N.

Le prix à payer est une expansion absurde : chaque bit de clair devient un nombre de la taille du module, soit des milliers de bits. Personne ne l'emploie en pratique. Mais l'idée que le chiffrement doit être randomisé a façonné tous les schémas modernes et contribué au prix Turing 2012 de ses auteurs.