Voir la source de Cryptosystème de Goldwasser-Micali

=== Syntaxe générale ===
Le cryptosystème de Goldwasser et Micali est un schéma de [[Cryptographie asymétrique|chiffrement à clé publique]] : il est constitué de trois [[Algorithme|algorithmes]] :

* un algorithme de génération des clés, [[algorithme probabiliste|probabiliste]], qui prend en entrée un [[paramètre de sécurité]] et retourne un couple <math>(\mathsf{sk}, \mathsf{pk})</math>constitué d'une clé privée et de la clé publique correspondante ;
* un algorithme de chiffrement, également probabiliste<ref group="Note">Un algorithme de chiffrement déterministe ne peut pas être sémantiquement sûr.</ref>, qui prend en entrée le paramètre de sécurité, un message clair, et une clé publique, et retourne un message chiffré ;
* et un algorithme de déchiffrement, déterministe, qui prend en entrée le paramètre de sécurité, un message chiffré, et une clé privée, et retourne un message.