What's the state of the art in factorization?

[Jerry Leichter]

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