1

For any point $P$ on an elliptic curve such that $P = X*Q$ where $X$ is an unknown integer and $Q$ is another point on the curve, what information can we extract about $X$ from $P$?

I understand we cannot get the complete value of $X$, but is there any information available which gives part of the value of $X$ such as whether $X$ is even or odd or whether $X$ is greater or smaller than another $X'$ value by, for example, comparing $2$ points together?

FFjet
  • 5,041
  • Are you asking given $P$ and $Q$ finding $X$ such that $P=[X]Q$ – kelalaka Sep 10 '19 at 20:15
  • Yes. I believe we can't find the full X value but we may be able to find some property of that X. Such as whether its even or odd or something similar. –  Sep 10 '19 at 20:16

1 Answers1

1

This is called the Elliptic Curve Discrete Logarithm Problem. Formally;

Given two points on the Elliptic Curve (EC) $P$ and $Q$ find an integer $x$ such that $P =[x]Q$ where $[x]Q$ is the scalar multiplication on the curve.

The generic attacks for finding the value of $x$ has $\mathcal{O}(\sqrt{n})$ complexity where the $n$ is the number of elements of the Curve.

The basics security of Elliptic Curve Cryptography relies on this problem. Curve25519, Bitcoin curve Secp256k1, etc has around $2^{256}$ elements, therefore, they provide around 128-bit security.

Extracting information about the $x$ is really depending on the curve. Some curves are not safe so the problem is tractable. For example, Nigel Smart showed that EC with trace one are not safe.

We describe an elementary technique which leads to a linear algorithm for solving the discrete logarithm problem on elliptic curves of trace one. In practice, the method described means that when choosing elliptic curves to use in cryptography one has to eliminate all curves whose group orders are equal to the order of the Finite FIeld.

So you can find $x$ in linear time.

Also, Shoup showed that in the Generic Group Model the Discrete Logarithm is hard.

kelalaka
  • 1,637