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

[Andrey Jivsov <[e-mail]>]

On 03/15/2015 11:50 PM, Michael Hamburg wrote:
>> On Mar 15, 2015, at 10:26 PM, Andrey Jivsov <[e-mail]> wrote:
>>
>> In my proposal the v, the second coordinate, is only sent in the first flight (or a part of the public key in general). That's where we can expect that the Montgomery ladder will be less common. The second flight, the shared secret calculation, doesn't use v and thus there is no change to the Montgomery ladder.
>> Each 32 bytes arrive every 1/((200*10^6/8)/32) = 0.00000128 seconds (every 1.2 microsec on 200 Mbps). While we seem OK with the *whole* quad-code CPU, the CPU is a precious resource on a busy server (so in reality we are not OK in this scenario). Why pay 10% penalty?
>>
>> If we look at https://tools.ietf.org/html/rfc5246#section-6.2.1, the World is wasting 2 bytes per each
>> 2^14 bytes of traffic in the best case scenario. There is also some waste in 4K handshake and block cipher padding that could be eliminated.
> I understand that there are implementations out there other than the Montgomery ladder, and they
> require more compute time if you don’t send a v coordinate.  It may be worth discussing further
> whether the communication cost to send v is more or less than the cost for the recipient to compute
> it, though I still expect that in most cases it is cheaper to recompute v.
>
> But this just doesn’t make sense for ECDH.  You want to force *every* implementation, of
> which the considerable majority will probably be the Montgomery ladder, to send and receive an
> 32 extra bytes.  You want to add non-negligible extra complexity to the simplest implementations
> (IOT) to make this happen.  You want this so that a small (and so far hypothetical) minority of
> implementations can make a tradeoff of compute time vs communication that *still* might be
> unfavorable.  I just don’t see how this adds up.

The protocols that cannot afford a few additional lines of code like in 
the diff 
https://github.com/brainhub/curve25519-donna/commit/abc601836b75ba6399c775842647e0f3b66061c4 
might standardize on u only ( as I wrote in 
http://www.ietf.org/mail-archive/web/cfrg/current/msg06480.html ). I 
would like to hear more about these protocols, though.

On the Internet in general (YouTube, Netflix streaming) and TLS in 
particular, it's hard to see that ~32 bytes per (not reused) handshake 
matter. This part of the Internet is currently using uncompressed points 
and RSA.

>
> Cheers,
> — Mike
>
> PS: If you think it’s good to add 32 bytes to public keys to speed up signature verification, please
> consider the following proposal.  Instead of adding a second coordinate, add the u coordinate
> of 2^128 * P and a sign bit.
>
> Compared to your proposed algorithm, this u coordinate saves 128 doublings (~~ 128*6.2 M in
> extensible or extended+Hisil’s lookhaead coordinates) at the cost of an extra decompression
> (~256*0.9 M), an extra wNAF table precomputation (~8*8M), and an extra fixed table for g,
> with a net savings of about 499M.  That’s more than double what the v-coordinate saves, and
> almost the same math works for Ed448.
>
> I don’t actually want to do this.  I’m just pointing out that “we should always trade space for time”
> is a silly argument, and if you buy it then there are better ways to do it.
>