Score:3

Is there any "exception-free" coordinates system for Weierstrass curves?

vu flag

I'm referencing RFC-6090 for an attempt at implementing ECC in my spare-time project.

In the RFC, pseudo-code examples are given to illustrate how to handle points-at-infinity in point arithmetic, and this involved several special cases. This is because the point doubling and point add formula in affine and homogeneous coordinates cannot correctly handle point at infinity.

So I want to ask: is there a coordinates system where the point doubling and adding formula can handle point at infinity cases?

Ruggero avatar
kr flag
What are you trying to implement exactly ? generic point operations or a specific crypto function ?
DannyNiu avatar
vu flag
@Ruggero Point addition and doubling, but with less case labels for point at infinity. I assumed there may be a special coordinates system that can make this easy.
Score:3
kr flag

For the homogenous coordinate systems it is possible to use addition and doubling formulas which are complete and exception-less for all odd order elliptic curves. These were originally derived by Bosma and Lenstra and optimized more recently by Renes et al. in this paper.

The main issue is that they are slower than incomplete formulas. The limitation of being valid only on odd order curves is not significant as most standards constains only prime-order short weierstass.

Here's a table, from the paper, describing the required field operation and comparing it with standard Jacobian: Table 3

DannyNiu avatar
vu flag
How much slower is the complete formula? By how many orders of magnitude? Or are they slower than side-channel-masked described in RFC-6090?
Ruggero avatar
kr flag
@DannyNiu I've added a table showing the field operation required by this complete formulas vs incomplete Jacobian, they should be <2x slower. The authors also implemented them in openssl in a windowed ladder and it was 1.4x slower.
DannyNiu avatar
vu flag
I was going to request a Markdown version of the table, since my national firewall doesn't like Imgur which hosted the screenshot of the table. But anyway the table is too complex to be formatted in Markdown, and it's in the paper. I'll look into it.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.