# ElGamal malleability for a given function f(m)

Given the function $f(m)=m^3$, where $m$ is a plaintext message, what is a function for which ElGamal would be malleable to produce $f(m)$. I know for $t * c_2$ that this would yield $t * m$ but I haven't been able to figure out how it works with powers of $m$.

• Please state your question a bit more precise. For instance, you haven't defined $c_2$ or $t$. – user27950 Oct 8 '16 at 6:13
• @Cryptostasis I'm pretty sure $c_2$ is a cipher text (more precisely: the blinded message) and $t$ is just a number. Because this sounds like a demonstration of the multiplicative homomorphic property of ElGamal. – SEJPM Oct 8 '16 at 11:48
• @SEJPM So, do you think he is asking how to operate homomorphically to get an encryption of $m^3$ given an encryption of $m$? Sometimes I have a hard time to understand some questions here... – Hilder Vitor Lima Pereira Oct 8 '16 at 12:03
• @Vitor yes, that's what I think and have answered :) – SEJPM Oct 8 '16 at 12:12

To understand how this works, let's first recap how ElGamal works:

All parties agree on system parameters $(\mathbb G_q,q,g)$ first such that and the order of $g$ in $\mathbb G_q$ is $q$. All the formulaes to follow need to be read as being done in $\mathbb G_q$ written multiplicatively, except if specified otherwise.

Next the recipient picks a random $x\in\mathbb Z_q$ and publishes $\beta=g^x$ as his public key and keeps $x$ as his private key.

Now finally the sender picks a random $y\in\mathbb Z_q$ himself and computes $c_1=g^y$ and $\beta^y=g^{xy}$. He uses this "shared secret" to multiplicatively blind the message $m\in\mathbb G_q$ as $c_2=m\cdot \beta^y$. The cipher text is now $(c_1,c_2)$.

Now you want to modify $(c_1,c_2)$ to $(c_1',c_2')$ such that $m'=m^k$ for arbitrary choices of $k$.

This is indeed trivial. First observe what happens if you calculate $(c_1',c_2')=(c_1^k,c_2^k)$. As you may already see, this means you actually calculate $(g^{yk},(g^{xy}\cdot m)^k)$ and this is exactly $(g^{yk},g^{xyk}\cdot m^k)$ which in turn decrypts to $m^k\bmod p$ as the recipient will just compute $c_1^x\equiv g^{xyk}$ to unblind the message $m'$.

In the above explanations, plug $\mathbb F_p$ (with $\mathbb P\ni q=(p-1)/2\wedge p\in\mathbb P$) in as your group $\mathbb G_q$ and $k=3$ to get the answer to exactly your question. Alternatively you may plug the group of the points on your favorite elliptic curve in as your $\mathbb G_q$ and pick $k=42$.