Partial Homomorphic Schemes that are probabilistic

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 ?

• "Padding" can mean a lot of things. ElGamal and Pallier are homomorphic in their semantically secure versions, which some might consider "padded." But for padding methods that provide CCA2 security (which is often the purpose of padding), it is impossible: CCA2 and homomorphism are contradictory. Sep 14 '14 at 14:12
• @ChrisPeikert can u give any reference paper on the impossibility result of CCA2 and Homomorphism ? Jun 29 '15 at 10:56
• It's an easy exercise: a CCA2 attacker can homomorphically modify its challenge ciphertext (e.g., add 1 to the underlying plaintext), then ask its decryption oracle to decrypt the result. This reveals the plaintext in the challenge ciphertext. Jul 14 '15 at 6:30
• yes @ChrisPeikert i spent some time and realized the same Jul 14 '15 at 8:36

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$.