Skip to content

Probabilistic Encryption

Authors: Shafi Goldwasser; Silvio Micali
Year: 1984
Venue: JCSS 1984

type: scheme collection: schemes status: auto

Links: DOI

Visual lesson: Goldwasser–Micali · Scheme table row: Goldwasser–Micali

Summary

Auto-extracted summary (unreviewed)

Introduces probabilistic public-key encryption and the notion that nothing about the cleartext should be efficiently computable from the cyphertext (semantic security / polynomial indistinguishability), as a remedy for the weaknesses of deterministic trapdoor-function encryption such as RSA and Rabin. The first construction encrypts bit by bit using quadratic residues modulo a composite n = p1 p2, and its security is proved under the intractability of deciding quadratic residuosity; the scheme is also the first bitwise (XOR-)homomorphic encryption scheme and is applied to mental poker.

Abstract

A new probabilistic model of data encryption is introduced. For this model, under suitable complexity assumptions, it is proved that extracting any information about the cleartext from the cyphertext is hard on the average for an adversary with polynomially bounded computational resources. The proof holds for any message space with any probability distribution. The first implementation of this model is presented. The security of this implementation is proved under the intractability assumption of deciding Quadratic Residuosity modulo composite numbers whose factorization is unknown.
Source: manual

Extracted details

Field Value Source Confidence
contribution probabilistic model of encryption: encryption is a randomised algorithm, so a message has many cyphertexts llm 0.80
contribution formal security notions: semantic security and polynomial indistinguishability (polynomial security) for any message space and distribution llm 0.80
contribution shows that deterministic trapdoor-function encryption (RSA, Rabin) can leak partial information about structured messages llm 0.80
contribution Goldwasser-Micali cryptosystem: bit-by-bit encryption with quadratic residues modulo n = p1 p2, decryption via the factorization llm 0.80
contribution security proof reducing any partial-information leak to deciding quadratic residuosity modulo composites llm 0.80
contribution application to playing mental poker keeping all partial information secret llm 0.80
schemes Goldwasser-Micali probabilistic encryption llm 0.80
schemes quadratic residuosity assumption llm 0.80
schemes trapdoor predicates llm 0.80
tasks public-key encryption llm 0.80
tasks mental poker llm 0.80
security level security parameter k (bit length of the factors of the modulus); no concrete bit-security figure llm 0.80
threat model passive adversary with polynomially bounded computational resources llm 0.80
interaction other llm 0.80
limitations large message expansion since every bit is encrypted separately llm 0.80
limitations security rests on the unproven intractability of quadratic residuosity / factoring llm 0.80
limitations local PDF is an OCR'd scan, so extracted text may contain recognition errors llm 0.80
key result ciphertext expansion: one modulus-sized element per message bit (about k bits per bit) (quadratic-residue encryption modulo n = p1 p2) llm 0.80
key result security reduction: any efficient leak of partial information yields an efficient algorithm for deciding quadratic residuosity modulo n (assuming the quadratic residuosity assumption) llm 0.80

Scheme card: Goldwasser–Micali

Group 8. Partially homomorphic encryption
Kind Scheme
Hardness assumption Quadratic residuosity
Plaintext type Bits, XOR only
SIMD packing No
Bootstrapping n/a
Post-quantum No
Status Foundational
Fit for LLM inference First semantically secure scheme, XOR-homomorphic.

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: RSA 10 [p.2]
  • library: Concrete (Zama) 1 [p.3]
  • task: Language modeling / generation 6 [p.2]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s47-0_probabilistic-encryption.pdf schemes 30 26.7 MB 26123aa4cca8

Notes

Local PDF is a scan of the JCSS reprint (from Silvio Micali's MIT page) with an OCR text layer added; OCR text may contain errors.


Database key: probabilistic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set probabilistic-encryption COLUMN VALUE