Re: [Cfrg] Elliptic Curves - curve form and coordinate systems (ends on March 12th)

[Andrey Jivsov <[e-mail]>]

On 03/12/2015 01:40 PM, Michael Hamburg wrote:
> Or maybe I’m misunderstanding.  Are you still figuring that an ECDH implementation will only use the u output from the Montgomery ladder?

Correct, the Montgomery implementation would always use u (disregard v 
on input).

The shared secret is u, as produced by the existing Montgomery ladder 
code. If the implementation is a mix of e.g. Twisted Edwards calculation 
for fixed base and Montgomery for variable base, the Montgomery ladder 
code doesn't change at all.

Ephemeral keys can be pre-calculated (or reused) and thus the <1% cost 
applies to the worst-case scenario. Public keys in certificates live for 
years.

>
> In that case, the ladder doesn’t have this added complexity, but I prefer Adam’s suggestion to use a sign bit instead of sending the full v coordinate.  In that case also, ECDH wouldn’t output the sign bit, so it wouldn’t be a completely unified point format, but that’s fine.

Adam's proposal is a step in the direction I advocate, except that I 
point that sending only 1 bit, i.e. the point compression, has 10% 
penalty during decompression. For this reason I think that the sender 
should "help" the recipient avoid it for about 10% saving for both.

The cost of decompression is 10% for each ECDHE or signature verification.

I wonder how many trees will die due to everybody decompressing the v 
for the life of each certificate :-) ?

>
> Cheers,
> — Mike
>
>> On Mar 12, 2015, at 1:26 PM, Michael Hamburg <[e-mail]> wrote:
>>
>> Hi Andrey,
>>
>> Have you considered the extra complexity to compute which is the correct v at the end of the Montgomery ladder?  If you want a unified point format that every operation uses, you need a way to compute the sign of v.
>>
>> I get 4 u0 v1 v2 = (1 - u1 u2 - u0 u2 + u0 u1) (1 - u1 u2 + u0 u2 - u0 u1) and symmetrically.  This doesn’t require a square root if you know the input’s v coordinate, but it does increase complexity.  At some point you might as well go full decaf, particularly if there’s no trivial patch to existing curve25519() functions.
>>
>> Cheers,
>> — Mike
>>
>>> On Mar 12, 2015, at 1:04 PM, Andrey Jivsov <[e-mail]> wrote:
>>>
>>> I apologize (need more coffee). I meant to write v = SQRT(u^3 + 486662*u^2 + u). The SQRT can be calculated (for almost free) during X/Z calculation by the sender at the end of scalarmult, because the sender must do 1/Z, but there is no apparent way to avoid SQRT for the receiver (unless the received doesn't need v and only works on u). The sign is embedded in v (and v can be adjusted  p-v as needed for signatures; ECDH doesn't care).
>>>
>>> On 03/12/2015 12:53 PM, Adam Langley wrote:
>>>> On Thu, Mar 12, 2015 at 12:19 PM, Andrey Jivsov <[e-mail]> wrote:
>>>>> I propose the Montgomery curve representation (u, v), which can be used for
>>>>> signatures on the same curve.
>>>>>
>>>>> "u" is identical to the sec 9 of
>>>>> https://tools.ietf.org/html/draft-agl-cfrgcurve-00.
>>>>> "v" is calculated (at virtually no additional computational cost) as v = u^3
>>>>> + 486662*u^2 + u
>>>> I'm going to display my ignorance here, but if "v" can be calculated
>>>> from just u with very little cost, why send it at all? The receiver
>>>> could equally calculate it if useful, no?
>>>>
>>>>> * The format is friendly for crypto algorithms that need to add points (as
>>>>> opposed to ECDH only)
>>>> Wouldn't they need to know an extra bit? Given a point on the
>>>> Montgomery curve, (u,v), the "v" value is v^2, right? Doesn't that
>>>> discard the sign of v?
>>>>
>>>>
>>>> Cheers
>>>>
>>>> AGL
>>>>
>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> [e-mail]
>>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg