Re: [Cfrg] Elliptic Curves - curve form and coordinate systems

[Michael Hamburg <[e-mail]>]

So, here is my view on this.

For ECDH, it is strongly preferable to have x-only output, so that the Montgomery ladder works.  It is also preferable if the ECDH ephemerals can be produced by the Montgomery ladder with minimal or no modification, because that reduces code size for embedded applications.  The fastest and simplest ECDH variable-base implementations will use the Montgomery ladder, so sending the y-coordinate is a waste.  Therefore, there’s a big advantage to x-only or x+sign for the wire format.

Between x-only and x+sign, there’s very little difference for ECDH.  The sign takes an extra bit (+0 bytes for Curve25519 and +1byte for Goldilocks).  If a sign bit is required, Montgomery ladder ECDH-only implementations can set it arbitrarily (eg, to 0).  If the bit is omitted, non-Montgomery implementations can choose it arbitrarily, since it doesn’t affect the shared secret.



For non-ECDH, x-only is insufficient, and most systems will need to decompress points if they’re compressed.  There’s very little security or performance difference between the two options: compression prevents some attacks but adds complexity; it saves time and energy on radio links but costs time and energy on wired ones or when the point is cached.  I prefer compressed points, but I admit that this is largely for aesthetic reasons.

However, if we choose x+sign then we can use it for both point formats.  That’s a big enough deal to make me prefer it.



It is also possible to use an implicit sign bit, eg “y/x is always positive” (positive meaning even, or maybe less than p/2).  This can be done with Andrey Jivsov’s trick of negating the secret key if y/x is not positive.  But that doesn’t work as a wire format for eg PAKE or MQV.  A more general solution is to invert x if y isn’t positive (the decaf trick), since (x,y) -> (1/x,-y/x^2) is the 2-torsion action and negates y/x.

As with x+sign, this implicit sign bit would not be used in the Montgomery ladder’s output, so it would affect only signatures and the like.  The advantage of implicit sign bit is that it gives all EC points the same format as the Montgomery ladder for very little cost.

— Mike

> On Mar 13, 2015, at 10:46 AM, Andrey Jivsov <[e-mail]> wrote:
> 
> On 03/13/2015 09:33 AM, Nico Williams wrote:
>> On Fri, Mar 13, 2015 at 10:50:08AM -0400, Rene Struik wrote:
>>> a) use of public key in computations.
>>> Here, Andrey Jivsov's point was that receipt of a full point (x,y)
>>> on a curve, rather than a compressed point or simply the
>>> x-coordinate, does not artificially impose a performance penalty on
>>> all implementations except x-coordinate-only ones (Montgomery).
>> A "penalty" of some sort is involved in *all* possible choices, and
>> there isn't one that is ideal for all use-cases.  Others have pointed
>> this out.
>> 
>> ECDH-only applications will exist and will be a/the common case.  Add to
>> this the simplicity arguments, and clearly x-only Montgomery is a better
>> choice for ECDH.
>> 
>> Some trade-offs:
>> 
>>  - x-only -> you must either have a Montgomery ladder implementation
>>              *and* other implementations if you *also* support
>>              signatures
>> 
>>              or
>> 
>>              you must have point conversion code *and* use it for ECDH
>>              (10% penalty)
>> 
>>    Obviously (I think), the first choice is better: it's a development-
>>    and compile-time cost, with the small additional run-time cost of
>>    extra text footprint IF you need both around (point coversion also
>>    has this extra text footprint at run-time).
>> 
>>  - (x,y)  -> bandwidth waste Montogmery ladder implementations
> 
> Is "wasting" of 32 extra per TLS/SSH session that important?
> 
> Considering average TLS session reuse rate today, this is 16 bytes per TLS session (and is likely to be fewer bytes than this).
> 
>> 
>>    This is not nothing (see Mike H.'s posts).
>> 
>> Similarly for (x,sign(y)).
>> 
>>> b) representation of public key in white list.
>>> Here, one can use many methods to map a public key Q to a condensed
>>> (perhaps, even human-recognizable) format f(Q).
>>> This condensed format could take the form affine format curve point,
>>> compressed format, hash, leftmost n-octets, hash value, etc.
>> For (b), I don't see why x-only isn't good enough.  Can you elaborate?
>> 
>> Nico
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg