[Cryptography] Why is ECC secure?

[Tony Arcieri]

On Fri, May 29, 2015 at 12:26 PM, Bill Cox <waywardgeek at gmail.com> wrote:

> Why do we believe this is secure, other than the fact that in EEC's short
> life, no one has cracked it?  Compared to DLP and integer factorization, I
> doubt many people have tried.
>

For what it's worth, you can say the same thing about factorization. The
only reason RSA is secure is because factoring large numbers is generally
considered a hard problem.

Index calculus attacks aside, integer factorization and DLP have some
interesting "isomorphisms" (for lack of a better term). For example,
Pollard's rho is the best algorithm (in different forms) for solving both
problems:

https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms

My understanding is that both problems can be reduced to the Hidden
Subgroup Problem:

https://en.wikipedia.org/wiki/Hidden_subgroup_problem

There's been a decent amount of research into solving DLP. Certainly it's a
problem that humanity has spent less time working on than factorization,
but so far there hasn't been any particularly interesting breakthroughs.

-- 
Tony Arcieri
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150529/09438fb6/attachment.html>