Partial Homomorphic Schemes that are probabilistic

Question

As mentioned in wikipedia there are many Partial Homomorphic Encryption(PHE) scheme like RSA, Elgamal, Pailler etc.

Pailler encryption scheme seems to be probabilistic

Are there any other PHE schemes that are probabilistic in nature ?

Answer 1

Actually, only probabilistic schemes will be of interest, since all other schemes (such as the "plain" homomorphic version of RSA) will not provide semantic security. This is problematic, because for many applications of homomorphic encryption plaintext messages can then easily be guessed by "trial encrypting" potential candidates and comparing the ciphertexts. So you want only schemes that are IND-CPA secure.

Yes, Paillier is probabilistic by nature. ElGamal is also probabilistic by nature and as already said by Chris Peikert in the comments it provides IND-CPA security if used correctly (although the homomorphism may then not be of interest for practical applications anymore).

The impossibility of IND-CCA2 secure homomorphic encryption follows this argumentation: Recall the IND-CCA2 game. In the IND game, the avdersary submits two distinct messages $m_0\neq m_1$ and the challenger flips a random bit $b$, encrypts $m_b$ and gives the ciphertext to $m_b$ to the adversary. Now in the IND-CCA2 setting the adversary has access to a decryption oracle in the pre- and the post-challenge phase. Let us now consider the scheme is homomorphic. Thus the adversary can take the challenge ciphertext and any other message of its choice, say $m'$, compute the corresponding ciphertext and perform the homomorphic operation on the ciphertexts corresponding to $m_b$ and $m'$. Then, the adversary submits the resulting ciphertext to the decryption oracle (it is allowed to do so because the restriction on the decryption oracle is only not to submit the challenge ciphertext). Then, when given the plaintext message from the decryption oracle the adversary simply undoes the operation (from the homomorphism) with $m'$ on the plaintext space and if the resulting message equals $m_0$ it outputs $0$ and $1$ otherwise. Consequently, the adversary wins with probability $1$.

So the best you can hope to get for homomorphic schemes is IND-CCA1 security (so called lunch-time attacks, where the adversary has no longer access to a decryption oracle after seeing the ciphertext corresponding to the challenge message).