GoldwasserMicali

GoldwasserMicali, or the Goldwasser–Micali cryptosystem, is a probabilistic public-key encryption scheme introduced in 1982 by Shafi Goldwasser and Silvio Micali. It is based on the quadratic residuosity problem and operates over Blum integers, numbers of the form n = pq where p and q are primes congruent to 3 modulo 4. The public key consists of n and a fixed value y that is a quadratic non-residue modulo p and modulo q; the private key is the factorization (p, q). The scheme is notable for achieving semantic security under the assumption that quadratic residuosity is hard.

Key generation begins by selecting suitable primes p and q, forming n = pq, and choosing a y in Z_n^* that is a non-residue modulo p and q. Encryption of a single bit b uses a random r in Z_n^*. The ciphertext is c ≡ r^2 (mod n) if b = 0, or c ≡ y r^2 (mod n) if b = 1. This yields probabilistic encryption because different random r produce different ciphertexts for the same bit.

Decryption requires the private factors p and q. Given c, the recipient tests whether c is a quadratic residue modulo p and modulo q. If c is a residue modulo both primes, the decrypted bit is 0; if it is a non-residue modulo either prime, the decrypted bit is 1. The correctness rests on y being a non-residue modulo p and q, so multiplying a square by y flips residuosity.

Security relies on the hardness of distinguishing quadratic residues from non-residues modulo n without knowledge of p and q. While historically important and foundational for probabilistic public-key encryption, Goldwasser–Micali is not widely used in modern practice due to efficiency considerations, having influenced later schemes and the broader study of semantic security.