-1
$\begingroup$

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).

$\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$
    – joro
    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$ 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$
    – joro
    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.
    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$ Nov 20, 2015 at 13:45

1 Answer 1

0
$\begingroup$

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

$\endgroup$
1
  • $\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$ Nov 20, 2015 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.