Re: [Cfrg] Mishandling twist attacks

1. Very much agreed on 3 mod 4 primes; they are much more pleasant to work
with.

The most rigid solution is then to require, as Samuel proposes, the curve
and its twist to have equal cofactors.

----

2. The NUMS paper's approach to selecting curves was technically superior;
it is elegant and rigid.

(Provided that the complete Edwards curve with parameter d0 is used, of
course.)

----

However. Curve25519 is widely deployed. The benefits of changing curve
parameters is negligible. No new curves over 2^255-19, please. We have a
perfectly good one.

The likelihood of my adopting a new curve is not increased by CFRG's
meddling with good crypto.

--

(I have no opinions about Curve1174.)

David Leon Gil
Yahoo

(PS From a hot tub, on Thanksgiving vacation.)
On Fri, Nov 28, 2014 at 5:20 PM Samuel Neves <sneves@dei.uc.pt> wrote:

> On 28-11-2014 17:22, Watson Ladd wrote:
> > What exactly is wrong with telling everyone to multiply by 8, not 4,
> > even if the cofactor is 4?
>
> If your protocol is tightly coupled with an elliptic curve, nothing wrong
> with that, I suppose. But schemes and
> protocols are often specified in terms of generic groups, where order and
> cofactor always exist, but the notion of twist
> security may not.
>
> > So if we add this requirement to have the curve have larger cofactor
> > then the twist, then we still get E-521, and we will get Curve25519 at
> > the low end. It seems to me like we should make this change to the
> > generation method, and run it on 2^389-21 to get the intermediate size
> > curve.
>
> All this bickering further convinces me that complete Edwards curves over
> 3 (mod 4) primes are the way to go:
>
>  - Square root computations are the simplest. 1 (mod 4) is too lenient, by
> the way: I don't think anybody is interested
> in computing square roots over 1 (mod 8) primes.
>
>  - Edwards curves over 3 (mod 4) primes can have both order and twist with
> cofactor 4.
>
>  - For users obsessed with speed, Mike Hamburg has described how to use an
> isogeny to get twisted Edwards-speed out of
> these curves [1].
>
> We already have an excellent candidate in this space, namely Curve1174
> over 2^251-9. E-521 is also such a curve. Since
> 2^389-21---which appears to be one of the nicest primes in that range (the
> other one being 2^379-19)---is also congruent
> to 3 (mod 4), it seems logical to keep things consistent and choose 3 (mod
> 4) primes for every work factor.
>
> [1] https://eprint.iacr.org/2014/027
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>