Probabilistic Encryption

By Shafi Goldwasser, Silvio Micali. 1984

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Privacy in Deep Learning: A Survey (2020, background): “Semantic security [64] (computationally secure) is a standard privacy requirement of encryption schemes which states that the advantage (a measure of how successfully an adversary can attack a cryptographic algorithm) of an adversary with background information should be cryptographically small.”
XPIR : Private Information Retrieval for Everyone (2016, background): “This property offers strong guaranties on ciphertext secrecy as proved by Goldwasser and Micali [50].”
On the Difficulties of Disclosure Prevention in Statistical Databases or The Case for Differential Privacy (2010, background): “Readers familiar with semantic security – roughly, everything computable about the plaintext given the ciphertext should be computable without access to the ciphertext [24] – will note the similarity to Dalenius’ goal.”
Composition attacks and auxiliary information in data privacy (2008, background): “(the use of the term “semantic” for such deﬁnitions dates back to semantic security of encryption [18]).”
A model for asynchronous reactive systems and its application to secure message transmission (2001, methodology): “The proof is a hybrid argument as first used in [16], i.”
Formal certification of code-based cryptographic proofs (2009, background): “[18] S. Goldwasser and S. Micali.”
Modern Cryptography: Theory and Practice (2003, methodology): “The danger has become well understood after the well-known critique of Goldwasser-Micali on the deterministic trapdoor function model of Diffie-Hellman [125], and has been widely avoided in the standard applications of public-key cryptography (e.”
On the complexity of differentially private data release: efficient algorithms and hardness results (2009, background): “A scheme (Setup,Encrypt ,Decrypt ,Trace) is a t-resilient traitor tracing scheme if (i) the ciphertexts it generates are semantically secure (see [13]), and (ii) no PPT adversary A can “win” in the following game with non-negligible probability (over the coins of Setup, A,Trace): The adversary A rec”
Random oracles are practical: a paradigm for designing efficient protocols (1993, methodology): “For background, definitions, precise statements of results, and efficiency comparisons with known schemes see Section 3, but, briefly, what is argued there is the following: the first scheme achieves polynomial/semantic security as defined by 24; the second is secure against chosen-ciphertext…”
Deterministic and Efficiently Searchable Encryption (2007, background): “The classical notions of privacy for public-key encryption schemes, mainly indistinguishability or semantic security under chosen-plaintext or chosen-ciphertext attack [34, 43, 47, 28, 10], can only be met when the encryption algorithm is randomized.”
Secure Indexes (2003, methodology): “Hence, the documents can be compressed and encrypted with any compression algorithm and chosen ciphertext secure [14, 3, 21] cipher.”
Introduction to Modern Cryptography, Second Edition (2014, unknown): “The modern computational approach to cryptography was initiated in a groundbreaking paper by Goldwasser and Micali [80].”
Security of public-key cryptosystems based on Chebyshev polynomials (2004, background): “The first received an answer by Goldwasser and Micali in [16], where the notion of semantic security (w.”
Universal Re-encryption for Mixnets (2004, background): “Loosely speaking, this property stipulates the infeasibility of learning any information at all about a plaintext from a corresponding ciphertext [15].”