1
$\begingroup$

SIKE involves a Diffie-Hellman like construction using isogenies between elliptic curves. Is it possible to express it as an instance of Diffie-Hellman? I.e. what is the underlying group if so, and further, why wouldn't Shor's algorithm apply and render it vulnerable?

$\endgroup$

2 Answers 2

4
$\begingroup$

I am one of the inventors of SIKE.

There is no actual Diffie-Hellman group in SIKE. If there were, then SIKE would be vulnerable to Shor's algorithm, as you said, largely defeating the purpose of a post-quantum cryptosystem.

Among other reasons, isogenies typically have a domain different from their codomain, so an isogeny cannot be iterated. You can compose two different isogenies (provided that their respective domains and codomains are compatible), but usually not an isogeny with itself.

$\endgroup$
3
  • $\begingroup$ I'm going to accept this -- can't really beat the actual author -- though I think the "real answer" is that SIKE is based on the group action view of DH, and Shor's algorithm does not generally apply to group action DH (correct me if I'm wrong here). I was misled since if you squint hard enough SIKE does sorta look like classic DH + SIDH has it in the name, but this was a good read for me to learn the basics: arxiv.org/pdf/1809.04803.pdf w/ slides: caramba.loria.fr/sem-slides/201905141330.pdf for anyone else confused $\endgroup$
    – nimish
    Commented Jun 2, 2020 at 6:03
  • 1
    $\begingroup$ SIKE does not use group actions. CSIDH uses group actions. Although Shor's polynomial-time quantum algorithm cannot handle group action DH, Kuperberg's subexponential-time quantum algorithm can. Hence CSIDH is vulnerable to Kuperberg's subexponential quantum algorithm, whereas SIKE is not. $\endgroup$
    – djao
    Commented Jun 3, 2020 at 6:22
  • $\begingroup$ Schooled! Thank you for your insight. $\endgroup$
    – nimish
    Commented Jun 3, 2020 at 17:46
2
$\begingroup$

what is the underlying group

Isogenies do not form a group; one easy way to show that is that inverses do not exist.

An isogeny is a mapping between two elliptic curves $A$ and $B$ that maps a specific subgroup (kernel) in $A$ to the identify in $B$.

If an isogeny $\phi$ has a kernel that consists of at least two elements ($A$'s identity and something else), then there cannot be an inverse $\phi^{-1}$ isogeny (because it would have to map the identity element back to $A$'s kernel, and an isogeny cannot map an element (including the identity element) to multiple elements.

why wouldn't Shor's algorithm apply

Shor's algorithm works by providing a way to compute the length of a cycle. By an extension of the above observation, we cannot have a cycle of isogenies, that is, a series of isogenies that map back to the original curve and preserve all the points, and hence there isn't a cycle for Shor's to determine the length of.

$\endgroup$

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.