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

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" <cfrg-bounces@irtf.org
on behalf of dbrown@certicom.com> 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; cfrg@ietf.org
>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" <marshalko_gb@tc26.ru>
>написал:
>
>> 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" <dbrown@certicom.com> написал:
>>
>>> 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
>>> Cfrg@irtf.org
>>> https://www.irtf.org/mailman/listinfo/cfrg
>
>_______________________________________________
>Cfrg mailing list
>Cfrg@irtf.org
>https://www.irtf.org/mailman/listinfo/cfrg