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]
Related papers¶
- Benaloh's Dense Probabilistic Encryption Revisited misfiled as this paper — the PDF was originally filed under this paper
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