2
$\begingroup$

I need to compute an isogeny from $E: y^2 = x^3 + ax + b$, given a generator point for its kernel subgroup, using Python. The point has smooth order.

I need both the parameters for the curve and polynomials for point mappings.

I have already read about Vélu's formulas, but it seems it will take a lot of time to compute each point in the subgroup, and more time to evaluate the curve parameters.

I know PARI and MAGMA provide an algorithm for that, but I need to understand the algorithm to write it on my own.

I am trying to use this for computing SIDH.

$\endgroup$
4
$\begingroup$

The complexity of Vélu's formulas scales linearly with the size of the kernel subgroup, so directly applying them to a point of huge order is not feasible for isogenies of "cryptographic" degree.

Instead, SIDH implementations decompose an isogeny of degree $\ell^n$ into $n$ isogenies of degree $\ell$. An easy way to do this is the following: Suppose given a point $P\in E$ of order $\ell^n$, where $\ell$ is "small"; we wish to compute $E/\langle P\rangle$. We decompose the isogeny $\varphi\colon E\to E/\langle P\rangle$ as: $$ E = E_0 \xrightarrow{\psi_1} E_1 \xrightarrow{\psi_2} E_2 \xrightarrow{\psi_3} \dots \xrightarrow{\psi_{n-1}} E_{n-1} \xrightarrow{\psi_n} E_n = E/\langle P\rangle \text, $$ where each $\psi_i$ has degree $\ell$. A straightforward calculation shows that the kernels of the isogenies $\psi_i$ can be obtained by pushing $P$ through the previous isogenies $\psi_1\dots\psi_{i-1}$ and multiplying by an appropriate cofactor: $$ \operatorname{ker}\psi_i = \langle[\ell^{n-i}](\psi_{i-1}\circ\dots\circ\psi_1)(P)\rangle \text. $$ Since $\lvert\operatorname{ker}\psi_i\rvert=\ell$ is small, computing each $\psi_i$ is efficient. (Of course, this representation can also be used to efficiently evaluate $\varphi$ at a given point by simply passing the point through the chain of $\psi_i$s.)

Notice that it is this decomposition that gives the legitimate users of the system an advantage over attackers: It allows Alice and Bob to compute an isogeny in time logarithmic of the computational effort that an attacker needs to perform. In that sense, it is serves the same purpose as square-and-multiply (and its variants) for group-based Diffie-Hellman instantiations.

Finally, note that this straightforward strategy for computing $E/\langle P\rangle$ is not necessarily the most efficient possible: Depending on the relative costs of isogeny computations and point multiplications, there may be better strategies; see the original SIDH paper (Section 4.2.2) for details.

$\endgroup$
0
$\begingroup$

Use Velu formula with all the points of the subgroup. Sure it would take too long for a large subgroup, and this is why group order is considered like $2^m 3^n$. I think you understand it ok with the subgroup.

$\endgroup$
  • $\begingroup$ say, im using p=2^(372)3^(239) - 1 so the ord(R) is 2^(372) right? that means the kardinality of the subgroup will be 2^(372), isnt that too much point to evaluate? $\endgroup$ – Hanif Mar 29 '18 at 2:37
  • 3
    $\begingroup$ Hello, have you read sections 1.3.4–1.3.7 of the SIKE spec? csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/… If that's not clear enough, I'd be happy to give more explanations. $\endgroup$ – Luca De Feo Mar 29 '18 at 15:30
  • $\begingroup$ @LucaDeFeo: yes actually i just read SIKE spec and there is some thing still bugging me. I quite understand about the section 1.3.6 about computing $(l_A)^{e_A}$ degree isogeny by composing $l_A$ degree isogeny $e_A-1$ times, but i still dont understand section 1.3.7 about the strategy $(s_1,... s_{t-1})$ of size $t-1$ that you mention in the section. Also what is the different between SIKE and SIDH? sorry to ask but i cant figure the difference between them $\endgroup$ – Hanif Apr 2 '18 at 16:49
  • $\begingroup$ Section 1.3.7 describes an algorithm to compute the same results faster. You can disregard it if you're trying to understand the mathematics behind SIDH, but it is very important for implementers. $\endgroup$ – Luca De Feo Apr 3 '18 at 17:12
  • 1
    $\begingroup$ SIDH is an ephemeral key exchange protocol, like Diffie Helman. SIKE is a suite comprising a public key encryption protocol (à la El Gamal), and a Key encapsulation protocol (similar to El Gamal + AES). They are all based on the same primitive. $\endgroup$ – Luca De Feo Apr 3 '18 at 17:14

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.