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


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 1


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.

  • $\begingroup$ 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.). $\endgroup$
    – Damian
    Sep 4, 2018 at 20:42
  • $\begingroup$ 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? $\endgroup$
    – Damian
    Sep 4, 2018 at 20:43
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Sep 4, 2018 at 23:25
  • $\begingroup$ 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. $\endgroup$
    – Damian
    Sep 5, 2018 at 6:14

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.