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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Jun 4, 2021 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
    Commented Jun 4, 2021 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
    Commented Jun 8, 2021 at 12:01
  • 2
    $\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
    Commented Jun 9, 2021 at 20:05

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.