4
$\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$
3
  • $\begingroup$ Can you define malleable? $\endgroup$
    – mikeazo
    Dec 15, 2014 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, 2014 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, 2014 at 12:14

1 Answer 1

7
$\begingroup$

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

Basically, homomorphic encryption means that given encryptions $E_k(x)$ and $E_k(y)$ of some values $x$ and $y$, you can obtain an encryption of $x\ast y$ under the same key $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)$. They may then compute $E_k(x)\mathbin{\hat\ast}E_k(y)$, where $\hat\ast$ denotes the "lifted" implementation of $\ast$ on ciphertexts, to obtain a ciphertext $\zeta$. By definition, $\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 they know ($x\ast y$) but whose ciphertext they haven't observed before.

Therefore, any homomorphic encryption scheme is malleable.

$\endgroup$
5
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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