[145247] in cryptography@c2.net mail archive
Re: What's the state of the art in factorization?
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Thu Apr 22 10:53:16 2010
Cc: cryptography@metzdowd.com
From: Jerry Leichter <leichter@lrw.com>
To: Samuel Neves <sneves@dei.uc.pt>
In-Reply-To: <4BCF8A5D.7030806@dei.uc.pt>
Date: Wed, 21 Apr 2010 22:49:50 -0400
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
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
