-1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\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 '18 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 '18 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 '18 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 '18 at 6:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.