# 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})$.

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?

$$(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.
• 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? 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. Sep 4 '18 at 23:25