Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]

[Robert Ransom <[e-mail]>]

On 12/1/14, Adam Langley <[e-mail]> wrote:
> On Sun, Nov 30, 2014 at 7:33 PM, Robert Ransom <[e-mail]>
> wrote:
>> Third, you appear to be arguing that ECDH operations would not use the
>> Montgomery curve *isomorphic* to the Edwards curve in your Internet
>> draft, but use a *different* Montgomery curve (PinkBikeShed) which is
>> merely *isogenous* to the curve that you are proposing, in order to
>> reduce the modifications required to make the many existing
>> independent, interoperable implementations of Curve25519 operate on
>> your curve.  This would *slightly* reduce the technical disadvantage
>> of your proposal compared to Curve25519, but would clearly not
>> eliminate it.  If you do intend to propose PinkBikeShed for ECDH,
>> rather than the Montgomery curve isomorphic to the one specified in
>> your Internet draft, then that needs to be stated explicitly in your
>> draft.
>
> Yes, I agree. The draft should specify the Montgomery curve and the
> isogeny maps.

You are listed as a co-author of the draft.  If you believed that
those pieces of information should be included in it, why did you not
include them into the draft?

> I also very much hope that the CFRG doesn't just specify
> curves, but also will provide detailed guidance about their use --
> that's also missing from the draft at the moment.

The previous proposal draft-turner-thecurve25519function-01 includes a
complete statement of the Montgomery ladder.  It was submitted ‘in
full conformance with the provisions of BCP 78 and BCP 79’, and does
not include any notice forbidding modifications to it.  Thus, other
IETF participants -- including you -- are permitted to copy text from
that draft into other Internet drafts.  Why did you not include that
description of the Montgomery ladder into the draft that you
co-authored?

Your co-authors wrote a paper (listed as one of the draft's
references) which specifies algorithms to perform several
scalar-multiplication tasks.  Did you ask them to provide plain-text
descriptions of those algorithms for inclusion in the draft itself?


>> Interesting suggestion.
>>
>> Both 89747 and 121665 are 17 bits long (they are between 2^17 and 2^18
>> - 1), and 89747 has a slightly greater Hamming weight than 121665 (10
>> rather than 9); I would expect any performance improvement on due to
>> that change in curve parameter to be quite small and only applicable
>> to a very few implementation strategies.  Have you done any
>> benchmarking to quantify the performance improvement that you are
>> claiming as a technical benefit of PinkBikeShed?
>
> I've not done any benchmarking, it's just a guess. But the Edward's d
> parameter for the curve isomorphic to Curve25519 isn't 121665, it's
> +/- 121665/121666 [http://eprint.iacr.org/2007/286.pdf, section 2].
> That value doesn't have a small representation so I think that the
> PinkBikeShed curve does get to use a multiplication by a small
> constant in place of a multiplication by a large constant. That might
> be a small help.

In order to claim that your proposal only requires changing the
curve-parameter constant (A - 2)/4 from one small integer to another
in an existing Curve25519 implementation, you proposed to use the
Montgomery curve with A=358990 (i.e. PinkBikeShed) for ECDH.
PinkBikeShed is isomorphic to an Edwards curve with d equal to a ratio
of small integers, exactly like Curve25519.

Both Curve25519 and PinkBikeShed are *isogenous* to Edwards curves
with small-integer d; neither of them is *isomorphic* to one.


>> Do you believe that that possible performance improvement is a
>> sufficiently large technical benefit over Curve25519 to outweigh the
>> technical disadvantages of your proposal that you were aware of at the
>> time that you submitted it?
>
> No. I think the prevalence of Curve25519 alone is enough that the CFRG
> should adopt it. PinkBikeShed isn't what I want, but it's close and
> it's something that I can live with in order to move forward.

Do you believe that there is *any* benefit (technical, procedural, or
otherwise) in further consideration of the draft that you co-authored,
draft-black-rpgecc-00, over the previously submitted
draft-turner-thecurve25519function-01?


Robert Ransom