Jerry Leichter wrote:
On Apr 21, 2010, at 7:29 PM, Samuel Neves wrote:
EC definitely has practical merit. Unfortunately the patent issues
around
protocols using EC public keys are murky.
Neither RSA nor EC come with complexity proofs.
While EC (by that I assume you mean ECDSA) does not have a formal
security proof, i.e., it is as hard as the EC discrete log, it it much
closer to one than RSA is to factoring. In particular, Pointcheval and
Stern, and later Brown come close to a formal proof for ECDSA [1]....
It's perhaps worth pointing out again how little formal complexity
proves tell you about security.
Suppose we could show that RSA was as hard as factoring. So? Nothing
is really known about how hard factoring is. At worst, it's NP-complete
(though that's actually considered unlikely). But suppose *that* was in
fact known to be the case. What would it tell us about the difficulty
of factoring any particular product of two primes? Absolutely nothing.
NP-completeness is a worst-case result. In principle, it could be the
case that factoring is "easy" for numbers less than a billion bits long
- it just becomes much harder "eventually". (I put "easy" in quotes
because it's usually taken to mean "there's a poly-time algorithm", and
that's a meaningless statement for a finite set of problems. *Every*
finite set of problems has a O(1) time solution - just make a lookup
table.)
There are some concrete complexity results - the kind of stuff Rogoway
does, for example - but the ones I've seen tend to be in the block
cipher/cryptographic hash function spaces. Does anyone one know of
similar kinds of results for systems like RSA?
-- Jerry
E.g. Koblitz, Neal; Menezes, Alfred, "Another Look at ``Provable
Security''", Cryptology ePrint Archive: Report 2004/152, available at
http://eprint.iacr.org/2004/152.pdf.
- Thierry Moreau
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com