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?