[145253] in cryptography@c2.net mail archive
Re: What's the state of the art in factorization?
daemon@ATHENA.MIT.EDU (Thierry Moreau)
Thu Apr 22 13:52:47 2010
Date: Thu, 22 Apr 2010 11:55:02 -0400
From: Thierry Moreau <thierry.moreau@connotech.com>
To: Jerry Leichter <leichter@lrw.com>
CC: Samuel Neves <sneves@dei.uc.pt>, cryptography@metzdowd.com
In-Reply-To: <95296893-A930-4A81-9689-372FD6D68435@lrw.com>
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 majordomo@metzdowd.com
