1
$\begingroup$

I want to know if there's an "easy" timing-free way to compute the sign of $y$-coordinate of $r G$, for a secret scalar $r$ and $G$ the generator of an elliptic curve.

We have several choices for scalar multiplication: 1) use a Montgomery ladder, which provides the $x$-coordinate, but tells you nothing about the $y$-coordinate; and 2) other methods such as multiply-and-add on the Edwards curve.

Montgomery ladders are lovely, because it's not too hard to get something which is pretty safe against timing attacks, so for ECDH it's an obvious choice. However, signature schemes require that you know the $y$-coordinate, which leads to very fiddly implementation requirements, like timing-free table lookups for windowed scalar-mul.

My question is whether there's a middle choice: using Montgomery for the $x$-coordinate, and some other method to obtain the sign of the $y$-coordinate, which can then be used by the verifier, avoiding the need to implement a timing-safe double-scalar-mul operation. I'm thinking of some kind of "differential sign-only" operation on the Montgomery curve.

In particular, I'm aware that the choice of "sign" is arbitrary: any half-sized subset of $Z_p$ can be designated as the "positive" set of $y$-coordinates. With this free choice of definition for the sign, is there a choice which makes the sign of $r G$ easy to determine, using a "simple" algorithm?

$\endgroup$
  • $\begingroup$ You can use the Montgomery ladder to compute $(x,y) = rG$. Some implementations e.g. for Montgomery curves use single coordinate ladders but e.g for a Weierstrass curve you can use a Montgomery ladder to compute both coordinates. $\endgroup$ – puzzlepalace May 17 '16 at 19:27
2
$\begingroup$

Using $x$-coordinates only, given a point $G = (x_0,y_0)$ on an elliptic curve $y^2 = x^3 + ax + b$ and a scalar $r$, the Montgomery ladder outputs the $x$-coordinate of $rG$. However, a closer look at the algorithm shows that the other accumulator used in the computation contains the $x$-coordinate of $(r+1)G$. Letting $x_1$ the $x$-coordinate of $rG$ and $x_2$ the $x$-coordinate of $(r+1)G$, we have that

$y_1 = \dfrac{2b+(a+x_0x_1)(x_0+x_1)−x_2(x_0−x_1)^2}{2y_0}$

is the $y$-coordinate of $rG$. Given $y_1$, its sign can readily be obtained.

See e.g. Éric Brier and Marc Joye, Weierstraß elliptic curves and side-channel attacks. In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pp. 335-345, Springer-Verlag, 2002.

$\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.