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

[Watson Ladd <[e-mail]>]

On Mar 16, 2015 1:05 AM, "Andrey Jivsov" <[e-mail]> wrote:
>
> 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.

Your patch is not computing the correct sign bit.

Why is having an alternative ECDH algorithm so important?  It's not any
faster, or easier to test, or simpler. The alternative implementations you
are suggesting are less secure and less fast.

>
> 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.
>>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg