0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Please state your question a bit more precise. For instance, you haven't defined $c_2$ or $t$. $\endgroup$ – user27950 Oct 8 '16 at 6:13
  • $\begingroup$ @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. $\endgroup$ – SEJPM Oct 8 '16 at 11:48
  • $\begingroup$ @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... $\endgroup$ – Hilder Vítor Lima Pereira Oct 8 '16 at 12:03
  • 1
    $\begingroup$ @Vitor yes, that's what I think and have answered :) $\endgroup$ – SEJPM Oct 8 '16 at 12:12
2
$\begingroup$

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$.

$\endgroup$

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.