[Cryptography] Why is ECC secure?

[Bill Cox]

On Wed, Sep 30, 2015 at 8:40 AM, Viktor Dukhovni <cryptography at dukhovni.org>
wrote:

> On Tue, Sep 29, 2015 at 09:47:01PM -0700, Bill Cox wrote:
>
> > A few weeks ago, I managed to prove what I'm sure is already well known:
> > that for Edwards curves, Finv(a) is just sn(a, k), where sn is the Jacobi
> > Elliptic sine function.  The whole Edwards curve addition rule, at least
> in
> > one quadrant, can be restated (in Wolfram Alpha language) as:
> >
> >     x3 = JacobiSN[EllipticF[ArcSin[x1], d] + EllipticF[ArcSin[x2], d], d]
> >
> > or more simply in regular notation:
> >
> >     x3 = sn(F(arcsin(x1), d) + sn(F(arcsin(x2), d), d)
>
> The existence of the "exponential map" for compact one-dimensional
> Lie-groups (such as Edwards curves, at least for d < 0) is not at
> all surprising.  The "exponential map" exists for *all* Lie-groups,
> and yields a group homorphism from the tangent vector space at the
> identity under addition into the group.
>

Do you know if this particular map is already known?  As per my experience
in crypto so far, I assume the answer is "yes".  At least this time, I'm
not _also_ wrong :)


> In the special case of compact one-dimensional Lie-groups the
> exponential map is necessarily a group isomorphism with the real
> circle (the exponential map is periodic with some period T).
>
> It is likely feasible to compute a local inverse of the exponential
> map (near the identity element) with enough precision to make
> discrete logarithms practical on Edwards curves over the real
> numbers (find $n$ given $nP$ for some base point $P$).
>

Yeah, I figured that out.


> But this applies only to curves over the reals, which are not
> terribly relevant to cryptography.  It does not carry over to curves
> over prime fields (or Galois extensions).
>
> It still seems like you're ignoring the lack of a generic correspondence
> between the continuous and discrete cases.  Yes *some* things work
> the same way, but important distinctions remain.
>
> --
>         Viktor.
>

I'm not ignoring it, I'm just using the geometric correspondence to help me
understand these curves.  There's no point wasting all thatd GPU hardware
in my brain :)

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151001/a06e99d5/attachment.html>