# How hard will it be to solve an equation in elliptic curve group/ cyclic group where Discrete Logarithm is hard?

Given an Elliptic curve group $$E(\mathbb{F}_q)$$ where the Discrete Logarithm Problem (DLP) is hard and a base point $$G \in E(\mathbb{F}_q)$$ with large prime order $$n$$, what will be the advantage of a polynomial-time bounded adversary $$\mathcal{A}$$ to solve the following problem:

• Given $$\alpha = X+Y$$ and $$\beta = X+Y+Z+r.a.G$$, $$\mathcal{A}$$ should output the point $$Z$$.
$$X,Y,Z \in E(\mathbb{F}_q)$$, and $$r,a \in \mathbb{Z}^*_n$$. It is worth nothing that $$r,a$$ are sampled at random.

One can assume that $$\beta$$ is an encryption of the message $$X+Y+Z$$ using ElGamal Cryptosystem over Elliptic Curve.

P.S: I have the impression that this problem can be reduced to breaking the DLP problem, but I am not certain.

• Why did you not simplify $\beta - \alpha$? If we have $\alpha$ and $\beta$ then $Z = T + r'[G]$ where $T = \beta - \alpha$ and $r' = -r \cdot a$ Feb 5, 2021 at 21:20
• Thank you for that hint. I did not see that $\beta - \alpha$ reduced it to DLP. Do you think that if $k \leftarrow H(X+Y)$ is used to generate a key, adding $Z$ (which is sampled at random) such that $k \leftarrow H(X+Y+Z)$ will be enough to generate a new key with good entropy? assuming that the adversary knows $\alpha$ and $\beta$ and the problem given in the question is indeed hard.
– vxek
Feb 5, 2021 at 21:34
• I assumed that $\alpha$ and $\beta$ is known. As of it $H(\alpha)$ is known, too. If $Z$ is a random point on a curve with $n-bit$ point indexing then it will provide $n+1$-bit entropy to $k \leftarrow H(X+Y+Z)$. It is not $2n$ due to the point compression!. Feb 5, 2021 at 21:44
• Note that if the attacker is also given $r \cdot G$ and $a \cdot G$ (as implied by the "ElGamal cryptosystem comment), then this is really the Computational Diffie Hellman problem, not DLP... Feb 5, 2021 at 22:29
• From Elgamal cryptosystem, $a$ and $r$ are supposed to be private. Regarding $k \leftarrow H(X+Y+Z)$, since $Z$ adds $n+1$ bit, will $k$ be "safe" enough to be used as encryption key? Assuming Computational Diffie Hellman
– vxek
Feb 6, 2021 at 3:45