0
$\begingroup$

In the proof of soundness for the SIDH ZK proof protocol (section 6.2 in DJP11) the authors refer to the "Theorem of the dual isogeny". What do they mean by this?

In particular, I don't understand why it easy to compute $\hat{\psi}$ when using Charles as a black box but not otherwise.

$\endgroup$
2
$\begingroup$

The theorem of the dual isogeny states that for every isogeny $ψ:E→E'$ of degree n there exists an associated isogeny $\hat{ψ}:E'→E$ of the same degree such that $ψ∘\hat{ψ}$ and $\hat{ψ}∘ψ$ are equal to multiplication by $n$ on the respective curves. See Silverman, The Arithmetic of Elliptic Curves, Chapter III.

On top of that, there are efficient algorithms to compute $\hat{ψ}$ given $ψ$, and vice-versa. See, e.g., https://eprint.iacr.org/2019/499. This has nothing to do with using Charles as a black box.

$\endgroup$
4
  • $\begingroup$ My confusion stems from the fact that if it is easy to compute $\hat{\psi}$ given $\psi$, then this is also easy for Vic, and using the fact that $\langle \hat{\psi}(R) \rangle$ is the kernel of the secret isogeny $\phi: E \to E/S$, Vic would then be in possession of the secret key S. $\endgroup$ – jvdh Jun 4 at 8:11
  • $\begingroup$ $\hat{\psi}(R)$ is undefined, because $R \in E$, but the domain of $\hat{\psi}$ is $E'$, and $E' \neq E$. $\endgroup$ – djao Jun 4 at 13:47
  • $\begingroup$ That's why I don't understand the proof in DJP11, where it is said that $\langle \hat{\psi}(R) \rangle$ is the kernel of $\phi$ . In YAJJS17, one computes $\hat{\psi}(\psi(S))$ to recover $S$, which makes sense to me $\endgroup$ – jvdh Jun 8 at 12:01
  • 1
    $\begingroup$ The confusion appears to stem from an unfortunate clash of notation. In diagram 6.1, $R$ generates the kernel of $ψ$. But, in the sentence you are quoting, it is said "Let $R$ be a generator of the kernel of $ϕ'$"; Using a different letter there would have been less confusing. $\endgroup$ – Luca De Feo Jun 9 at 20:05

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.