Single-scalar multiplication with sign bit

Question

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?

Answer 1

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.