Score:2

Is there any reason to search for Z values other than 1 when transforming X,Y to Jacobian representation of an EC Point?

om flag

When exchanging a public key I usually receive some compressed form of X,Y coordinates. To use some speed ups I'd need to represent that in the Jacobean x,y,z form.

Z=1 satisfies everything and looking at the speed ups (https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates, http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html) I don't see an obvious reason why Z=1 would be slower (or faster?) than any other Z, is this a legitimate question? Can you point me in some direction about "does it even make sense to look for Z other than 1?".

kelalaka avatar
in flag
Isn't it clear? $Z^4$ that is 1 when $Z=1$ and for the other cases one need 3 doublings.
T. Rossi avatar
om flag
thanks for the quick answer, when I do a multiplication of a point for a large number I'll do a bunch of additions, doubling, tripling, etc, and I was wondering if choosing a different z would have an impact. I'm not sure it makes sense as a question thought thanks again for the patience.
kelalaka avatar
in flag
In scalar multiplication, a point is added, again and again (double-and-add), there is no fixed point there.
Score:2
in flag

The point doubling (Wiki link) requires Z^4 and when used with the double-and-add algorithm (needed for public point calculation, ECDH, and EC-based signatures) using $Z=1$ simplifies the calculation of Z^4 otherwise one may need 3 doublings. The double-and-add method where the res is not fixed to save time. Double-and-add Wikipedia version;

let bits = bit_representation(s) # the vector of bits (from MSB to LSB) representing s
let res = O # point at infinity
for bit in bits:
    res = res + res # double
    if bit == 1:            
        res = res + P # add
    i = i - 1
return res

This is the beginning of the long story. The "m-fold double" (repeated doubling) calculates $[2^m]P$ and only calculates Z^4 once. When you need $[k]P$, you may need to represent $k$ in the binary form then use m-fold doubling when necessary. To have benefited from this, one has to calculate the cost before deciding to use m-fold double or not.

The answer is not easy and complete, since this one requires Z1=Z2 with 5M + 2S for addition Wiki version has 12M + 4S cost. The 5M + 2S has still Z1 multiplication and if Z1=1 that has zero cost.

In a short sentence, in general, Z1=1 simplifies the equations.

Since $(X_1:Y_1:Z_1)$ represents $(Z/Z^2,Y/Z^3)$ and $(X_1:Y_1:Z_1)$ is an equivalance relation that is $$(X_1:Y_1:Z_1) \sim (\lambda X_1:\lambda Y_1:\lambda Z_1)$$ one can simple convert the $Z_1 =1$ with $$(X_1/Z_1:Y_1/Z_1:1)$$

Keep in mind that 1/Z1 is not division, rather the inverse of Z1 on the defining field.

The Z1 on the other hand, is not staying there with Z1=1 under the operations. To benefit from this, one has to find the inverse and execute two multiplication. Finding inverse, on the other hand, is what we don't want since it is costly.

So, at least there is a benefit at the beginning of scalar multiplication.

T. Rossi avatar
om flag
Thank you very much!!
kelalaka avatar
in flag
Far from a perfect answer, though....
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.