# Malleability of homomorphic encryption

El Gamal is a malleable homomorphic encryption system, so is Rabin. Are all homomorphic encryption systems malleable? Or are there any that are not malleable? Thanks!

• Can you define malleable? – mikeazo Dec 15 '14 at 0:57
• From Wikipedia - An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext which decrypts to a related plaintext. – user100503 Dec 15 '14 at 2:02
• Malleable and being (semi-)homomorphic is the almost same functionality, from a different point of view: Malleable usually is used, if that property is a security weakness (and it is more general: it is by definition not limited to the actual group structure). It is called homomorphic, if this functionality is used to achieve some more complex functionality. – tylo Dec 15 '14 at 12:14

Basically, homomorphic encryption denotes that, given encryptions $E_k(x)$ and $E_k(y)$ of some values $x$ and $y$, it is possible to obtain an encryption of $x\ast y$ under $k$ from $E_k(x)$ and $E_k(y)$, where $\ast$ is some binary operation, without knowledge of the key $k$. Typically, $\ast$ is the usual addition or multiplication on (bounded) integers, but the attack actually works for almost arbitrary operations (namely, there must be a pair $(x,y)$ such that $x\ast y\notin\{x,y\}$): Assume that an attacker knows $x$ and $y$ along with their encryptions $E_k(x)$ and $E_k(y)$. He may then compute $E_k(x)\mathbin{\hat\ast}E_k(y)$, where $\hat\ast$ denotes the "lifted" version of $\ast$, to obtain a ciphertext $\zeta$. By specification, $\zeta$ decrypts to $x\ast y$, which was assumed different from both $x$ and $y$. Hence, the attacker has obtained a ciphertext ($\zeta$) corresponding to a plaintext ($x\ast y$) he knows but whose ciphertext he has not observed before.
• This is pretty much what I used, except in your case the attacker gets to see only one ciphertext; he can instead use $E_k(x)\mathbin{\hat\ast}E_k(x)$ for some $x$ with $x\ast x\neq x$ as a forged ciphertext. – yyyyyyy Dec 15 '14 at 2:25
• In one direction, there is nothing to show: Being homomorphic implies already some meaningful relation (e.g. you can always compute $2 \cdot m,3 \cdot m,...$). And for the other direction: The expression "meaningful relation" is not specific enough to achieve a homomorphic relation between ciphertexts. – tylo Dec 15 '14 at 12:20