2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Can you define malleable? $\endgroup$ – mikeazo Dec 15 '14 at 0:57
  • $\begingroup$ 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. $\endgroup$ – user100503 Dec 15 '14 at 2:02
  • 3
    $\begingroup$ 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. $\endgroup$ – tylo Dec 15 '14 at 12:14
4
$\begingroup$

The answer may depend on your exact definitions of "homomorphic" and "malleable", but I'll give it a shot.

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.

Therefore, any homomorphic encryption scheme is malleable.

$\endgroup$
  • $\begingroup$ Thank you. That makes sense. I am wondering if there is a way to formally prove it. I will use your explanation to come up with a general proof. $\endgroup$ – user100503 Dec 15 '14 at 2:08
  • $\begingroup$ The above is more of an intuition why "homomorphic" should generally imply "malleable". If you post the definitions you're using, I will try to come up with a more formal proof (which can't possibly make sense without definitions). $\endgroup$ – yyyyyyy Dec 15 '14 at 2:10
  • $\begingroup$ Your definition of homomorphism is what I am using. For malleable, if an attacker can derive ciphertext c2 from observed ciphertext c1, where plaintext m2 is meaningfully related to plaintext m1 then the encryption scheme is considered malleable $\endgroup$ – user100503 Dec 15 '14 at 2:14
  • $\begingroup$ 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. $\endgroup$ – yyyyyyy Dec 15 '14 at 2:25
  • $\begingroup$ 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. $\endgroup$ – tylo Dec 15 '14 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.