2
$\begingroup$

I'm facing the following problem: Suppose that we have a finite field $\mathbb{F}_p$ and an elliptic curve $E$ defined over it. Suppose that for $m\in \mathbb{Z}$ not multiple of the characteristic of the base field. So we have an isomorphism $$E[m]\longleftrightarrow (\mathbb{Z}/m\mathbb{Z})^2$$ Suppose we know that $$E[m]\subset E(\mathbb{F}_q)$$ where $q$ is a power of $p$. Suppose also that we have given generators $P,Q\in E[m]$ and a third point $R\in E[m]$. I want to find $a,b \in [0,m-1]$ for which $$R=aP+bQ$$ What is the computational cost of this problem? The most efficient algorithm i'm thinking about consists of trying to solve a lot of ECDLP $$R-aP=bQ$$ where $a\in [0,m-1]$. This of course has a computational cost $O(m\sqrt{m})$ since for the single ECDLP there are algorithm with computational cost $O(\sqrt{m})$. Thanks to all for your time.

$\endgroup$
3
$\begingroup$

There's probably an even quicker way, but here's one idea. Compute the Weil pairings $<P,Q>$ and $<R,Q>=<P,Q>^a$ and $<P,R>=<P,Q>^b$. Then you just have to solve the DLP twice in $\mathbb F_q^*$ to find $a$ and $b$, and there are subexponential algorithms for DLP over finite fields. And the Weil pairing is polynomial (essentially linear) time.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer and your time. This is very effective way to compute it. Now i have another curiosity: if the 2 points are not known to be the generators of a torsion subgroup, are there effective algorithms solving the "double discrete logarithm" problem: $$R=aP+bQ$$ Thanks again. $\endgroup$
    – Anselm
    Jun 18 '19 at 21:14

Your Answer

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

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