# Is this problem still as hard as discrete logarithm (modified ElGamal)?

I am trying to find a vulnerability or proof for the following problem:

ElGamal part.

Given $g\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$, select randomly $k\in\mathbb Z_p$ and calculate $h=g^k \mod p$. The public key is $(p, g, h)$ and private key is $k$.

To encrypt message $m\in\mathbb Z_p$, randomly select $r\in\mathbb Z_p$ and publish $(g^r, m\times g^{rk})$.

Additional part

Let $s$ be randomly selected from $\mathbb Z_p$. Publish $k+s$ and $g^{rs}$.

Problem

If we know $k+s$, $g^{rs}$ and public key $(g,g^k, p)$ is it possible to get $k$, $s$ or $g^{kr}$?

I have found this article (Is this problem same as discrete logarithm?) which is similar, but I cannot find a way it could help me with my problem.

Is this construction easily breakable? Can it be proved by transformation to discrete logarithm problem or other crypto problem?

## 1 Answer

Yes, the system is easily breakable. We have:

$$(g^r)^{k+s} / g^{rs} = g^{rk}$$

You don't list $g^r$ in your problem statement, however it is in the ciphertext, and so we can assume the attacker knows it.

• Indeed that was easy. I missed that one. Thank you. What I am trying to achieve is to publish a ciphertext that will be unmodifiable and later using homomorphic encryption publish some additional data that will allow to decrypt the ciphertext but will not allow to find a generic way to decrypt it (eg. AES is not enough, because I would have to give the symmetric key to someone and he could publish that. Then anyone can decrypt my ciphertext.). – Damian Sep 4 '18 at 20:42
• In one paper I have meet a bilinear map system $PG = (p, \mathbb G, \mathbb G_T, e)$, where $e$ is a function that holds $e(a^x,b^y) = e(a,b^{xy})$ and $e(a,b)^x = e(a,b^x) = e(a^x,b)$. Do you know a particular system that holds that? – Damian Sep 4 '18 at 20:43
• @Damian: that can be implemented by a standard pairing; that is, $\mathbb{G}$ is an elliptic curve group, $\mathbb{G}_T$ is a multiplicative group over an extension field, and $e$ is (say) a Tate pairing operation. – poncho Sep 4 '18 at 23:25
• Thanks, I need to check that Tate pairing. I am looking for something that is quite efficient. I liked ElGamal because I only have to do the power once and even if the message is big, I can divide it into chunks and do the multiplication of all chunks with previously calculated value. – Damian Sep 5 '18 at 6:14