Let $E$ be an elliptic curve over a finite field $\mathbb{F}_p$ of characteristic $p$. Let $P,Q\in E(\mathbb{F}_q)$, such that $Q=mP+n\tau(P)$, where $\tau$ is the p-th power of frobenious map and $m$ and $n$ are integers. It is clear that the problem of finding $m$ and $n$ from $Q$ and $P$ must be at least as hard as the discrete logarithm problem. I am looking for some algorithm which can solve this kind of problems. Is there an algorithm for general cases, for example when we have three points $Q,P_1,P_2\in E(\mathbb{F}_q)$ such that $Q=mP_1+nP_2$ (number of points can be more than 3).
$\begingroup$
$\endgroup$
9
-
$\begingroup$ If you choose known multiples of $P$, $P_i$, won't this be exactly the discrete logarithm for $Q$ unknown multiple of $P$? $\endgroup$– joroCommented Nov 20, 2015 at 13:15
-
$\begingroup$ Sorry, but I can't understand. In my example $P$ and $\tau(P)$ are independent. Could you explain for me, please? $\endgroup$– somayeh didariCommented Nov 20, 2015 at 13:31
-
$\begingroup$ Suppose given $P,Q$, you want to solve DL $Q=x P$. Give three points $P_1=2P,P_2=10P,P_3=100P$. If you can solve $Q=a_1 P_1 + a_2 P_2 + a_3 P_3$, then $Q= (2a_1+10 a_2 + 100 a_3)P$ modulo the order. $\endgroup$– joroCommented Nov 20, 2015 at 13:35
-
$\begingroup$ Why does $\tau(Q)$ lie on $E$? You either want $E$ to be defined over $\mathbb{F}_p$ or $\tau$ to be the $q$-th power Frobenius. $\endgroup$– R.P.Commented Nov 20, 2015 at 13:42
-
$\begingroup$ Ok I think I get your point Joro! You mean if I can find such relation, I can solve ECDLP. is is true? $\endgroup$– somayeh didariCommented Nov 20, 2015 at 13:45
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
1
Answering because of too many comments.
If you can solve ECDLP, you can solve your problem and the converse holds too.
The simplest cases is if the group order $r$ is prime.
Then all points are of maximal order $r$.
Choose a point $G$ and solve ECDLP $P_i=g_i G$ and $Q=q G$.
Then you must solve $q = \sum x_i g_i \mod{r}$, for $x_i$, which is easy.
For the converse, set $P_i = i G$. Solving $ Q= a_1 P_1 + ... a_n P_n$ solves the discrete logarithm $Q= x P \implies x= \sum (a_i i) \mod{r}$.
In the case when $r$ is not prime, the only problem is if the "generator" is not unique. In this case, try all "generators", e.g. see this: https://www.ma.utexas.edu/users/voloch/Preprints/EC-Generators.pdf
-
$\begingroup$ Suppose that $E$ has two generators $G_1$ and $G_2$, then every $P_i$ is of the form $P_i=x_i G_1+y_i G_2$. You mean having an Oracle to solve ECDLP, we can find $x_i$ and $y_i$? I can't do that! $\endgroup$ Commented Nov 20, 2015 at 15:14