Probabilistic encryption & how to play mental poker keeping secret all partial information

By Shafi Goldwasser, Silvio Micali. 1982

This paper proposes an Encryption Scheme that possess the following property : An adversary, who knows the encryption algorithm and is given the cyphertext, cannot obtain any information about the clear-text. Any implementation of a Public Key Cryptosystem, as proposed by Diffie and Hellman in [8], should possess this property. Our Encryption Scheme follows the ideas in the number theoretic implementations of a Public Key Cryptosystem due to Rivest, Shamir and Adleman [13], and Rabin [12].

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

A Review of Homomorphic Encryption Libraries for Secure Computation (2018, background): “Partially Homomorphic Encryption (PHE) schemes such as [9,10,11,12,13,14,15,16,17,18,19] allow only one type of operation any number of times - either addition or multiplication on encrypted data as compared to Somewhat Homomorphic schemes that support both.”
Riffle (2016, background): “To show zero-knowledge, let us assume that the encryption scheme is semantically secure [31], as assumed by [9].”
A Survey on Homomorphic Encryption Schemes (2017, methodology): “Until Gentry’s breakthrough in [Gen-try 2009], all the attempts [Rivest et al. 1978b; Goldwasser and Micali 1982; ElGamal 1985; Benaloh 1994; Naccache and Stern 1998; Okamoto and Uchiyama 1998; Pail-lier 1999; Damgård and Jurik 2001; Kawachi et al. 2007; Yao 1982; Boneh et al. 2005; Sander et al.…”
Secure Multiparty Computation for Privacy-Preserving Data Mining (2009, background): “We also assume the encryption scheme to be semantically secure [23].”
Papaya: Practical, Private, and Scalable Federated Learning (2021, methodology): “There are many existing additive homomorphic encryption schemes such as the works in (ElGamal, 1985; Goldwasser & Micali, 1982; Paillier, 1999; Cohen & Fischer, 1985).”
Protocols for secure computations (1982, methodology): “The other solution makes use of a probabilistic encryption method invented by Goldwasser and Micali [2].”
Evaluating 2-DNF Formulas on Ciphertexts (2005, background): “Current homomorphic public key systems [20, 13, 28] have limited homomorphic properties: given two ciphertexts Encrypt(PK, x) and Encrypt(PK, y), anyone can compute either the sum Encrypt(PK, x+y), or the product Encrypt(PK, xy), but not both.”
Lecture Notes on Cryptography (2001, background): “A one-way predicate, first introduced in [101, 102] is a notion which preceeds hard core predicates for one-way functions and is strongly related to it.”
Towards Statistical Queries over Distributed Private User Data (2012, methodology): “Each per-bucket binary value is individually encrypted using the Goldwasser-Micali (GM) bit-cryptosystem [27, 28] with the analyst’s public key.”
A Survey of Homomorphic Encryption for Nonspecialists (2007, methodology): “(i)We begin with the rather simple scheme of Goldwasser-Micali [34, 46].”
How to generate and exchange secrets (1986, background): “... means that if A behaves according to the protocol, then B will have no more information about the values of iA,UA than in the situation where an oracle does the computation for B and just hands B a value UB. Classical exam ples where privacy is the main concern include oblivious trans fer (Rab”
Cryptanalysis of a homomorphic encryption scheme from ISIT 2008 (2012, methodology): “After the introduction of privacy homomorphism, many schemes have been proposed, such as additive homomorphic encryption schemes [16], [1], [23], [30], [24], [9], [15], [18], [20], [25] and multiplicative homomorphic encryption schemes [10].”