1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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$ $\endgroup$ – kelalaka Feb 5 at 21:20
  • $\begingroup$ 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. $\endgroup$ – vxek Feb 5 at 21:34
  • 1
    $\begingroup$ 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!. $\endgroup$ – kelalaka Feb 5 at 21:44
  • 1
    $\begingroup$ 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... $\endgroup$ – poncho Feb 5 at 22:29
  • $\begingroup$ 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 $\endgroup$ – vxek Feb 6 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.