Let $P$ be a point on an elliptic curve $E$ and let $Q = \phi(P)$, where $\phi: E \to E'$ is an isogeny of degree $d$.
Given $E, E', P, Q$ and $d$, is it possible to find an isogeny $\phi': E \to E'$, not necessarily equal to $\phi$, such that $\phi'(P) = Q$?
If so, how? And what is the complexity of such an algorithm?
Follow up question: if it is possible, it is also possible for two pairs of points?
Given $E$, $E'$, and $d$, to find any isogeny $\phi\colon E \to E'$ of degree $d$ in general takes $O(d)$ time (arXiv:cs/0609020) using the current fastest known approach. It seems unlikely to me that the "extra" information of $P$ and $Q$ would make any difference.
Note that the combination of domain, codomain, and isogeny degree forms a very powerful constraint on the isogeny. I'm not sure, but I think in most natural situations (those where $d$ is not abormally large) this information would uniquely specify the isogeny up to automorphism, so $(E, E', d)$ alone would narrow the isogeny down to a small finite list of possibilities (no more than six), even without knowing $P$ and $Q$.