Re: [CFRG] compact representation and HPKE

[Loup Vaillant-David <[e-mail]>]

On Wed, 2021-02-10 at 04:42 -0800, Dan Harkins wrote:
>  
> For all of these curves, p = 3 mod 4 so doing a modular square root
> is just exponentiation to (p + 1)/4. Not sure how onerous an
> additional exponentiation is.

I've just checked by removing the final inversion from my X25519
implementation (which uses an x-only ladder), the cost is less than
10%. Comparatively even less if you're using a more expensive ladder.


> But then Mike Hamburg was saying that one can do a x-only Montgomery
> Ladder for these curves if an exponentiation is, indeed, onerous so
> there are options to consider.

To be checked, but an x-only ladder is likely to be faster on its own.
So not only do you gain speed by avoiding an exponentiation, you gain
speed by running a faster ladder.

While we *may* beat x-only ladders by using a complete addition law and
fixed windows, it would be more complex, and require more memory (stack
in most implementations). And a naive x-y ladder is about half the
speed of the x-only ladder, if not less (assuming constant time
implementations). This is horrible for embedded applications.

Alternatively, we could recover the y-coordinate *after* performing an
x-only ladder. With luck, it might not even cost an additional
exponentiation. Still, this feels like an avoidable complication, not
worth the single bit of security you could get by recovering the sign
of a point.

As an implementer, I have a very strong preference for x-only ladders:
not only are they fast, they're easiest to implement. Less room for
error.

Loup.