2
$\begingroup$

I was recently reading this paper on SIKE and I'm trying to understand the details of the implementation.

I've noticed the point tripling algorithm (algorithm 6) was already described in a different paper. Nevertheless, the SIKE paper uses a slightly different algorithm for calculating [3]P. I've quickly checked - it seems to me that both algorithms give different result (am I wrong?). Any idea why the algorithm from SIKE spec is preferred over the algorithm from the other paper. Is it somehow faster?

$\endgroup$
6
$\begingroup$

Not a complete answer, just trying to shed some of your doubts.

I've noticed the point tripling algorithm (algorithm 6) was already described in a different paper. Nevertheless, the SIKE paper uses a slightly different algorithm for calculating [3]P.

Although the official dates may indicate that the SIKE spec was published after the Faz-Hernández, López, Ochoa-Jiménez, Rodríguez-Henríquez paper (let's call it FLOR), the two were really being written about at the same time, so it's completely possible that we missed some optimizations.

As far as I can remember (speaking only for myself), the Montgomery ladder algorithm in FLOR had been previously presented at a conference, so we included it in the spec, but we did not know about the tripling formula at the moment of writing.

I've quickly checked - it seems to me that both algorithms give different result (am I wrong?).

I haven't checked, but it is completely possible that the two formulas give different, projectively equivalent, coordinates.

Any idea why the algorithm from SIKE spec is preferred over the algorithm from the other paper. Is it somehow faster?

Probably not faster, since FLOR explicitly say their formula is. However you have to follow the spec if you want to implement SIKE. It is important for the KEM that algorithm isogen returns exactly what's expected from the spec, and not something that is only projectively equivalent; so you cannot replace another formula inside the algorithm, unless the output is equal.

If it is confirmed that the FLOR formula is the best available formula, we may update the spec at the next round of the NIST competition.

$\endgroup$

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.