Re: [Cfrg] Progress on curve recommendations for TLS WG

On Sun, Jul 27, 2014 at 1:04 PM, Paterson, Kenny
<Kenny.Paterson@rhul.ac.uk> wrote:
> Dear CFRG,
>
> We made good progress last week in Toronto and on the mailing list in
> discussing requirements for curve selection, as well as getting into some
> of the specifics of the different curve options.
>
> The chairs have had requests to increase the time given to our discussion
> of requirements in the light of the Toronto meeting, and we are happy to
> accommodate that. We therefore plan to extend the previously announced
> schedule so that this initial phase will run for another 2 weeks (until
> Friday 8th August). We will then run the second phase (focussing on
> concrete curve proposals) for 4 weeks, as previously planned.
>
> Whilst it may be tempting to jump in and start discussing concrete
> performance aspects of the different, specific curve proposals, or drift
> off onto other topics entirely, the chairs would like to ask everyone to
> try to focus on requirements for a bit longer. Here are a few questions to
> help keep things on track and seed further discussion:
>
>
> - What is the cost of keeping backwards compatibility with existing
> defined point formats in RFC 4492, if any, for different curve shapes
> (Edwards, twisted Edwards, Montgomery, Weierstrass-only form)?

The cost is the cost of the isogeny in and out. It should be possible
to make a table of isogenies between each format
and when they exist: the information is out there but scattered.

However, RFC 4492 treats point formats as opaque, and while crypto
libraries may assume all curves use a particular
format, this hasn't stopped them from adding Curve25519 support
through different API paths.

>
> - If ephemeral really means ephemeral, what are the implications for the
> mix of fixed-base/variable-base computations in ECDHE and what, if any,
> are the implications for the choice of curve type?

If ephemeral means ephemeral, then we have 1 fixed+1 variable
multiplication. Variable multiplication alone no longer is as
important.

>
> - Correspondingly, what are the implications for our choices if we accept
> that ephemeral reuse is the expected behaviour?

If all multiplications are variable base for ECDHE, Montgomery is the
clear winner here. (Actually, Gaudry genus 2, but
people seem less excited by it)

>
> - Do the current proposals (Curve25519 and friends, and the NUMS curves)
> provide an adequate degree of rigidity that is likely to satisfy the
> widest set of commentators? Or should we be thinking about generating
> fresh curves using a public process having verifiably random inputs? What
> would the likely impact be on performance?

I think minimal parameter is enough rigidity. Random inputs would have
to be the closing price and daily trade volumes of all S&P 500
constituents on some day in the fall: no one can manipulate that
because it is in the future. The impact of random primes would be
pretty bad:
the best reduction algorithms take quadratic time in the number of digits.
>
> - Would selecting curves that are not in Weierstrass form materially slow
> down deployment?

I don't know the answer to this question.

Sincerely,
Watson Ladd
>
>
>
> Thanks for your considered inputs so far.
>
> Regards,
>
> Kenny (for the chairs)
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin