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, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 3:45

0

Reset to default

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.