What's the state of the art in factorization?

[Thierry Moreau]

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 at metzdowd.com