Re: [Cfrg] Question about A=6 Montgomery over 2^89-1

[Ben Laurie <[e-mail]>]

OK, now I want the shortest possible reading course that lets me figure out
what you just said.

Actually a serious request.

On Sat, 12 Dec 2015 at 18:29 Paterson, Kenny <[e-mail]>
wrote:

> Hi Dan,
>
> I asked Steven Galbraith about this. Here's what he said:
>
> "Some thoughts on the elliptic curve:  E : y^2 = x^3 + 6x^2 + x
> It is a global CM curve with j(E) = 66^3, so it has complex
> multiplication of discriminant -16.
> Due to congruence conditions it is therefore supersingular.
> To flip the question around:  For a given prime p, there is usually a CM
> elliptic curve over Q which is supersingular modulo p.  And since that
> curve is from a finite list it usually has small coefficients. So it is
> not at all surprising that one can find a curve with small coefficients
> that is supersingular. And if the prime p is such that p+1 is smooth
> then this is weak for Pohlig-Hellman.
> There is no reason to think there would be another other such example,
> so I guess there is nothing to worry about."
>
> Steven no longer subscribes to this list, so include him in cc if you want
> him to see any responses.
>
> Cheers
>
> Kenny
>
>
>
> On 12/12/2015 15:23, "Cfrg on behalf of Dan Brown" <[e-mail]
> on behalf of [e-mail]> wrote:
>
> >So 66^3 is one of the few (13???) integral j-invariants with CM over the
> >rationals (the Baker-Stark-Heegner theorem?). And yes Elkies shows that
> >half the primes will give a supersingular. I'll look at how j=66^3
> >corresponds to A=6 in 2016, and eventually try to sort out whether
> >there's much to say about small |A|.
> >
> >  Original Message
> >From: Grigory Marshalko
> >Sent: Friday, December 11, 2015 4:09 PM
> >To: Dan Brown; [e-mail]
> >Subject: Re: [MASSMAIL][Cfrg] Question about A=6 Montgomery over 2^89-1
> >
> >
> >This seems to be a better answer
> >
> >http://alexricemath.com/wp-content/uploads/2013/07/EC2.pdf
> >
> >Regards,
> >Grigory Marshalko,
> >expert,
> >Technical committee for standardisation "Cryptography and security
> >mechanisms" (ТC 26)
> >www.tc26.ru
> >11 декабря 2015 г., 23:20, "Grigory Marshalko" <[e-mail]>
> >написал:
> >
> >> Hi,
> >>
> >> May be this is the case:
> >> from wiki:
> >> If an elliptic curve over the rationals has complex multiplication then
> >>the set of primes for which
> >> it is supersingular has density 1/2. If it does not have complex
> >>multiplication then Serre showed
> >> that the set of primes for which it is supersingular has density zero.
> >>Elkies (1987) showed that
> >> any elliptic curve defined over the rationals is supersingular for an
> >>infinite number of primes.
> >>
> >> and this is also may be useful
> >>http://pages.cs.wisc.edu/~cdx/ComplexMult.pdf
> >>
> >> Regards,
> >> Grigory Marshalko,
> >> expert,
> >> Technical committee for standardisation "Cryptography and security
> >>mechanisms" (ТC 26)
> >> www.tc26.ru
> >> 11 декабря 2015 г., 00:22, "Dan Brown" <[e-mail]> написал:
> >>
> >>> Hi,
> >>>
> >>> I stumbled upon something surprising (to me), using Sage (while
> >>>searching
> >>> for something else).
> >>>
> >>> The Montgomery curve y^2 = x^3 + 6x^2 + x over the field of size
> >>>2^89-1, has
> >>> order 2^89, so it is maximally vulnerable to Pohlig-Hellman. (Other
> >>> details: it has order p+1, so is also vulnerable to MOV. I haven't
> >>>checked
> >>> yet, but I'd _bet_ it's supersingular. It has j-invariant 66^3.)
> >>>
> >>> As is well-known, the supersingular curve y^2 = x^3 + x also has order
> >>>2^89
> >>> (it has j-invariant 1728=12^3). But I recall a result of Koblitz saying
> >>> that curves over F_p with order p+1 are very rare (among isomorphism
> >>> classes). Naively, I would think that finding two such curves so close
> >>> together (A=0 and A= 6) has negligible chance, unless these weak
> >>>curves are
> >>> distributed towards small |A|.
> >>>
> >>> Nonetheless, I still hope that this does _not_ indicate some general
> >>>_weak_
> >>> correlation between Montgomery curves with a small coefficient and
> >>>known
> >>> attacks.
> >>>
> >>> To that end, I'd be curious if somebody here could explain the theory
> >>>behind
> >>> this example curve. For example, it would be re-assuring to explain
> >>>this as
> >>> a mere one-time coincidence, rather than a higher chance of a known
> >>>attack
> >>> (e.g. MOV or PH) on smaller-coefficient curves. (Purely speculating:
> >>>maybe
> >>> there's a good theory of supersingular j-invariants for each prime p,
> >>>then a
> >>> way to deduce A from j, such that p=2^89-1 and j=66^3 formed a
> >>>superstorm to
> >>> arrive at a small A=6.)
> >>>
> >>> Absent such an explanation, the worry is that if known attacks more
> >>> generally exhibit this kind of correlation with coefficient size, then
> >>>how
> >>> wise is it to suggest small-coefficient curve as a remedy against
> >>>secret
> >>> attacks?
> >>>
> >>> I am aware that there are other worries of a different nature
> >>> ("manipulation") involved with methods that generate larger
> >>>coefficients,
> >>> but maybe there's a good way to balance both concerns.
> >>>
> >>> Best regards,
> >>>
> >>> Daniel Brown
> >>>
> >>> _______________________________________________
> >>> Cfrg mailing list
> >>> [e-mail]
> >>> https://www.irtf.org/mailman/listinfo/cfrg
> >
> >_______________________________________________
> >Cfrg mailing list
> >[e-mail]
> >https://www.irtf.org/mailman/listinfo/cfrg
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>