[Cryptography] Why is ECC secure?

Viktor Dukhovni cryptography at dukhovni.org
Fri Aug 14 00:11:06 EDT 2015


On Thu, Aug 13, 2015 at 11:26:23PM +0000, Viktor Dukhovni wrote:

> On Wed, Aug 12, 2015 at 06:12:13PM -0700, Bill Cox wrote:
> 
> > I used Wolfram to evaluate the path integral for several multiples of the
> > generator point, and indeed, they are clearly multiples of a constant.
> 
> An Edwards curve over the reals is a compact subset of R^2 bounded
> away from (0,0).  Therefore, your scaled metric gives the image of
> the curve on S^2 a finite diameter, but there are points of infinite
> order on the curve when the generator "G" is not a torsion element.
> 
> Therefore, any proportionality between "n" and the "distance" of
> "nG" from some reference point (pick any continuous metric), fails
> for large enough "n".  Thus, before we even consider whether any
> of this applies to the discrete case, it seems clear that this must
> fail in the continuous case.

Note that, in essence, what you're trying to do is contruct a group
homomorphism from the real Edwards curve to the circle.  If "d" is
not a real square (i.e. d is negative), then the Edwards group law
is a differtiable function of its arguments, and the Edwards curve
is a compact one dimensional "Lie group".

Such a group is necessarily diffeomorphic to the unit circle, via
the "exponential map" (for which you've stumbled into a closed form
via Elliptic functions).  

More precisely, if e() is the exponential map on the Edwards curve
mapping real numbers t to group elements e(t), and T > 0 is the
smallest number with e(T) = identity, then we get a group isomorphism
to the unit circle:

	e(t) <-> exp(2*i*pi*t/T)

where e() is the exponential map (from theory of Lie groups) on
the Edwards curve, and exp() is the exponential map on the unit
circle which (not coincidentally) maps t -> e^{it}.

If G is not a torsion element, and you know a bound for "nG" and
a bound for "n", then sufficiently precise preimages for the
exponential map, log(G) and log(nG) (both known only modulo T) are
in principle sufficient to find "n".

This does not carry over to the discrete case.  A discrete Edwards
curve is not a Lie group, and the functions you're looking for are
the logarithms, which if you had at hand, would trivially identify
any cyclic subgroup of the curve abelian group with Z/nZ (discrete
circle).  These functions of course exist, but that does not make
them computable in practice.

-- 
	Viktor.


More information about the cryptography mailing list