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

[Dan Brown <[e-mail]>]

there's already been some answers on the list, but they haven’t resolved the issue fully to me, so I worked out that j = 256(a^2-3)^3/(a^2-4). For both j and a to be a (rational) integer, we must have a-2 and a+2 divide powers of two, which means a is 0,2,-2,6,-6.  I expect this is all worked out in some old publication.

so, for other j‎, I'd expect a mod p not too small. Not sure what happens for irrational j with CM over the rationals.

hence, so far, I only expect this one small a example‎. not yet sure how to infer something from this about unpublished weaknesses in ECDLP (assuming they exist, which is unlikely)

  Original Message
From: Steven Galbraith
Sent: Sunday, December 13, 2015 6:26 PM
To: Ben Laurie; Paterson, Kenny; Dan Brown; Grigory Marshalko; [e-mail]
Subject: Re: [Cfrg] Question about A=6 Montgomery over 2^89-1


Read Chapters 2 and 4 of Washington's book on Elliptic Curves. Section
4.6 comes close to discussing this sort of thing.

For a deeper knowledge you can look at Washington's chapter on Complex
Multiplication, or the book by Cox "Primes of the form x^2 + n*y^2", or
this great course by Drew Sutherland:
   http://math.mit.edu/classes/18.783/lectures.html

Steven


On 14/12/15 11:13, Ben Laurie wrote:
> 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]
> <mailto:[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] <mailto:[e-mail]>
>     on behalf of [e-mail] <mailto:[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] <mailto:[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 <http://www.tc26.ru>
>     >11 декабря 2015 г., 23:20, "Grigory Marshalko"
>     <[e-mail] <mailto:[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 <http://www.tc26.ru>
>     >> 11 декабря 2015 г., 00:22, "Dan Brown" <[e-mail]
>     <mailto:[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] <mailto:[e-mail]>
>     >>> https://www.irtf.org/mailman/listinfo/cfrg
>     >
>     >_______________________________________________
>     >Cfrg mailing list
>     >[e-mail] <mailto:[e-mail]>
>     >https://www.irtf.org/mailman/listinfo/cfrg
>
>     _______________________________________________
>     Cfrg mailing list
>     [e-mail] <mailto:[e-mail]>
>     https://www.irtf.org/mailman/listinfo/cfrg
>