[Cryptography] Why is ECC secure?

[Bill Cox]

On Tue, Jun 30, 2015 at 7:56 AM, Viktor Dukhovni <cryptography at dukhovni.org>
wrote:

> > > 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 said, with a bit more thought (and a hint from Watson Ladd I
> should not have needed), there is a useful homomorphism if we're
> willing to abandon the rational circle for multiplication in a
> finite field.
>
> If p == 3 mod 4, choose $i^2 = -1$ in a quadratic extension $F_{p^2}$.
> If p == 1 mod 4, choose $i^2 = -1$ in the base field $F_p$.
>
> In either case the mapping (x,y) -> (x+iy) is an injective homomorphism
> (monic) from the circle group into the multiplication group of the
> corresponding finite field.  In fact for the 1 mod 4 case the
> mapping is an isomorphism.
>
> So DLP in the 1 mod 4 circle group is identical to DLP in F_p (plus
> the cost of finding a square root of p-1).
>
> DLP in the 3 mod 4 circle group is a sub-problem of DLP in F_{p^2},
> which is subject to essentially the same index calculus attacks as
> F_p, but now the smooth factor base uses gaussian integers.
>

Thanks for this info.  That's very cool.

Given that the circle group seems roughy equivalent to regular DLP in
difficulty, is it safe to say that finding a compactly representable point
on the unit circle that maps to (x, y) mod p is equivalent in difficult to
DLP?  This would explain why I am finding it difficult to do :-)

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