0

Q: Let $\{P_1, P_2\}$ be a basis for $E[m]$. The Basis Problem for $\{P_1, P_2\}$ is to express an arbitrary point $P \in E[m]$ as a linear combination of the basis vectors, i.e., to find $n_1$ and $n_2$ so that $P = n_1 P_1 + n_2 P_2$. Prove that an algorithm that solves the basis problem for $\{P_1,P_2\}$ can be used to solve the ECDLP for points in $E[m]$.

(First, quick question, is $E[m]$ just an elliptic curve over any finite field $m$?)

My Work:

The ECDLP problem is given points $P, Q$ where $Q \in \left<P \right>$, solve for $n$ such that $nP = Q$

If we have a solution to the Basis Problem then we can express:

$P = n_{p_1} P_1 + n_{p_2} P_2$

$Q = n_{q_1} P_1 + n_{q_2} P_2$

then we want to solve for $n$ in

\begin{align*} nP &= Q \\ n \cdot \left(n_{p_1} P_1 + n_{p_2} P_2 \right) &= n_{q_1} P_1 + n_{q_2} P_2 \\ (n \cdot n_{p_1} - n_{q_1}) P_1 + (n \cdot n_{p_2} - n_{q_2}) P_2 &= \mathcal{O} \\ \end{align*}

I'm stuck on what to do next.

clay
  • 2,713
  • 23
  • 34

1 Answers1

1

The points $P_1,P_2$ together form a basis of $E[m]$. Hence for any $\alpha,\beta\in\mathbb{Z}/m\mathbb{Z}$ such that $\alpha P_1+\beta P_2=\mathcal{O}$ we can conclude that $\alpha=\beta=0$.

As for the quick question, by definition $$E[m]=\left\{P\in E\mid [m]P=\mathcal{O}\right\},$$ i.e. all the points that have order dividing $m$. It is a subgroup of the group of points on $E$. A standard theorem says that in most cases, $$E[m]\cong \mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z},$$ hence in that case we can choose a basis $P_1,P_2$ as you do. Then any point $P\in E[m]$ can be uniquely expressed as $P=n_{p_1}P_1+n_{p_2}P_2$ for $n_{p_1},n_{p_2}\in\mathbb{Z}/m\mathbb{Z}$.

CurveEnthusiast
  • 942