[Cryptography] Why is ECC secure?

[Viktor Dukhovni]

On Mon, Jun 15, 2015 at 02:05:51PM -0700, Bill Cox wrote:

> > Since there are only finitely mod p points, each point has a finite
> > order, i.e. (x,y)^n = 1 for for some n.  The same would have to be
> > true for any image of (x,y) under a homomorphism into the rational
> > circle.  However, there are only four rational points on the circle
> > with finite order:
> >
> >         1, -1, i, -i
> >
> > all other rational (p, q) with p^2 + q^2 = 1 have infinite order.
> > Otherwise, there'd be a primitive n^th root of unity for n > 2,
> > with rational real and imaginary parts, but all such numbers
> > have degree 2 over the rationals.
> >
> > So the only viable homorphisms are into Z_4, and cannot be injective
> > for all but the smallest primes.
> >
> > So this approach is a dead-end even for the circle, which is much
> > simpler than an actual Edwards curve with a non-zero "d"
> >
> 
> That's the shortest proof I've seen for why all but a few rational points
> generate infinite groups on the unit circle.  I Googled that the other day,
> and maybe this is a standard proof, but I failed to find such a succinct
> proof.  Nice!

Note, that I glossed over the details for the "n=3" and "n=4" cases.

For prime p, the p^th roots of unity lie in an extension of degree
p-1, not p.  

Thus cube roots of unity have degree 2, but these are well known
to have coordinates (-1/2, +/- sqrt(3)/2) which are not both
rational.

Similarly, we have to handle n=4 (which gives the +/- i  points).
After that we either have larger odd factors or higher powers of
two which give a degree of at least 4.

I don't know whether the proof outline is "standard" or not, the
result is surely well known.  It just seemed like the simplest way
to rule out additional rational points of finite order on the
unit circle.

If you abandon the requirement of a homomorphism, yes in principle
you could map each n*G in the mod p circle to its smallest non-negative
integer discrete logarithm.  No need for the unit circle at all.
At which point you get to read off the logarithm.

The problem is doing this *effectively* in practice.  If we posit
a log-table oracle, then we solve DLP.

It seems that your idea of mapping to the unit circle where discrete
logs may be viable for geometrical reasons boils down to proposing
an oracle.

Without claiming that DLP on the mod p circle group is secure (it
likely is not), I am willing to guess that any attacks are not
based on a concrete correspondence with the characteristic 0 circle.

A quick Google search, shows that the group has order p-1 if p is
1 mod 4, and p+1 if p is 3 mod 4.  The order of the group is always
divisible by 4.  (Not surprising given the subgroup corresponding
to the 4 rational points on the unit circle).

    https://books.google.com/books?id=ZXjHKPS1LEAC&pg=PA258&lpg=PA258&dq=%22circle+group%22+carl+pomerance&source=bl&ots=m9UpczU4Za&sig=RINCrY6soblJJqNoP8muuVvtmDY&hl=en&sa=X&ved=0CCAQ6AEwAWoVChMIvpWIw4uTxgIVh0SMCh1v1AQK#v=onepage&q&f=false

Perhaps someone else on the list knows more about these (C_p)
groups.

-- 
	Viktor.