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 ?
$\begingroup$
$\endgroup$
-
2$\begingroup$ "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. $\endgroup$ – Chris Peikert Sep 14 '14 at 14:12
-
$\begingroup$ @ChrisPeikert can u give any reference paper on the impossibility result of CCA2 and Homomorphism ? $\endgroup$ – sashank Jun 29 '15 at 10:56
-
1$\begingroup$ 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. $\endgroup$ – Chris Peikert Jul 14 '15 at 6:30
-
$\begingroup$ yes @ChrisPeikert i spent some time and realized the same $\endgroup$ – sashank Jul 14 '15 at 8:36
$\begingroup$
$\endgroup$
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).
