Goldwasser–Micali cryptosystem

Goldwasser–Micali cryptosystem
Name	Goldwasser–Micali cryptosystem
Authors	Shafi Goldwasser; Silvio Micali
Introduced	1982
Field	Public-key cryptography
Based on	Quadratic residuosity problem
Properties	Probabilistic encryption; semantic security (under assumptions)

Goldwasser–Micali cryptosystem The Goldwasser–Micali cryptosystem is a probabilistic public-key encryption scheme introduced in 1982 by Shafi Goldwasser and Silvio Micali that demonstrated rigorous notions of semantic security, combining complexity-theoretic foundations with practical cryptographic design. It established a formal connection between the hardness of number-theoretic problems and provable confidentiality, influencing subsequent work by researchers at institutions such as the Massachusetts Institute of Technology, IBM, and the University of California, Berkeley. The scheme leverages the quadratic residuosity problem and introduced techniques that informed constructions like probabilistic encryption, zero-knowledge proofs, and homomorphic encryption.

History and Motivation

Goldwasser and Micali presented their construction against the backdrop of earlier public-key systems developed by Whitfield Diffie, Martin Hellman, Ronald Rivest, Adi Shamir, and Leonard Adleman, aiming to formalize notions of secrecy beyond ad hoc heuristics used in schemes such as the RSA algorithm. Their work responded to discussions in venues including the IEEE Symposium on Foundations of Computer Science and the ACM Symposium on Theory of Computing, drawing on complexity-theoretic ideas from Alan Turing, John von Neumann, and Michael Rabin. The scheme motivated follow-up contributions by Oded Goldreich, Silvio Micali, and Avi Wigderson on zero-knowledge proofs, and influenced practical systems explored at organizations such as Bell Labs and Microsoft Research.

Mathematical Background

The construction rests on number theory concepts studied by Carl Friedrich Gauss and Adrien-Marie Legendre and formalized by Évariste Galois, with computational complexity perspectives advanced by Alan Turing and Stephen Cook. Central is the quadratic residuosity problem modulo a composite n = pq, where p and q are primes first considered in contexts by Pierre de Fermat and Leonhard Euler, and later algorithmically by Daniel Shanks and John Pollard. The scheme uses the Jacobi symbol, rooted in work by Carl Gustav Jacob Jacobi, and probabilistic primality tests pioneered by Robert Solovay, Volker Strassen, and Gary Miller. Security reductions appeal to worst-case hardness assumptions studied in complexity theory by Richard Karp and Richard Lipton. The cryptosystem’s homomorphic properties relate to algebraic structures examined by Évariste Galois and Emmy Noether.

Cryptosystem Description

Key generation samples two large primes p and q using algorithms influenced by the Miller–Rabin test and computes n = pq, an approach used in the RSA framework of Rivest, Shamir, and Adleman. A public value x is chosen such that the Jacobi symbol (x/n) = 1 while x is a non-residue modulo n, a criterion linked to work by Legendre and Gauss on quadratic residues. Encryption encodes each plaintext bit b as a random y squared times x^b modulo n, a mechanism similar in spirit to randomized padding techniques later used in protocols at the Internet Engineering Task Force and influenced designs by Bruce Schneier and Ronald Rivest. Decryption uses knowledge of p and q to test quadratic residuosity via algorithms related to modular exponentiation methods explored by Johann Carl Friedrich Gauss and computational optimizations by Donald Knuth. The scheme’s per-bit encryption yields ciphertext expansion, a design tradeoff analyzed in engineering contexts at Bell Labs and academic settings like Stanford University.

Security Properties and Proofs

Goldwasser and Micali established semantic security under the quadratic residuosity assumption, formalizing confidentiality notions that complemented contemporaneous work by Shafi Goldwasser and Silvio Micali in complexity theory and cryptography. Their proofs apply reduction techniques rooted in complexity-theoretic frameworks developed by Michael Rabin, Manuel Blum, and Oded Goldreich, and influenced soundness arguments in interactive proofs researched by Goldreich, Micali, and Wigderson. The scheme is provably secure against passive adversaries under the assumption that distinguishing quadratic residues from non-residues with Jacobi symbol one is computationally infeasible, an assumption related to hardness results studied by Andrew Odlyzko and Carl Pomerance in analytic number theory. The construction also admits semantic security under adaptive chosen-plaintext attacks as formalized in standards influenced by the National Institute of Standards and Technology and discussions at the International Association for Cryptologic Research.

Implementation and Performance

Implementations of the scheme have been explored in academic prototypes at institutions such as MIT, Harvard, and the University of California, Berkeley, and evaluated in engineering contexts like IBM Research and AT&T Labs. Performance bottlenecks arise from per-bit ciphertext expansion and repeated modular exponentiations, issues addressed by algorithmic optimizations from Ronald Rivest, Clifford Cocks, and Peter Montgomery. Practical deployments often favor alternatives such as RSA-OAEP and schemes based on the Diffie–Hellman problem used in standards by the Internet Engineering Task Force, yet Goldwasser–Micali remains valuable pedagogically in coursework at Carnegie Mellon University and cryptography seminars at the Simons Institute. Libraries implementing related primitives draw on work by the OpenSSL project, GNU Project contributors, and researchers at Microsoft Research.

Variants and Extensions

Subsequent research produced variants improving efficiency or extending functionality, including schemes incorporating batch encryption studied at IBM Research and homomorphic variants influencing fully homomorphic encryption work by Craig Gentry. Extensions connect to probabilistic encryption frameworks examined by Oded Goldreich and theoretical primitives used by Shafi Goldwasser in zero-knowledge systems, and to constructions exploiting alternative hardness assumptions such as the discrete logarithm problem investigated by Neal Koblitz and Victor Miller. Hybrid approaches combine Goldwasser–Micali-like randomness with symmetric-key methods popularized by Claude Shannon and Horst Feistel to mitigate ciphertext expansion, a strategy employed in engineering contexts including work at Bell Labs and Microsoft Research.

Category:Public-key cryptography