The Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982.
GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions.
The GM cryptosystem is semantically secure based on the assumed intractability of the quadratic residuosity problem modulo a composite N = pq where p, q are large primes.
Recipients use the factorization of N as a secret key, and decrypt the message by testing the quadratic residuosity of the received ciphertext values.
This has significant advantages, as it prevents an adversary from recognizing intercepted messages by comparing them to a dictionary of known ciphertexts.
The scheme relies on deciding whether a given value x is a square mod N, given the factorization (p, q) of N. This can be accomplished using the following procedure: The modulus used in GM encryption is generated in the same manner as in the RSA cryptosystem.
There is a simple reduction from breaking this cryptosystem to the problem of determining whether a random value modulo N with Jacobi symbol +1 is a quadratic residue.