What's the state of the art in factorization?

[Jonathan Katz]

On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote:

> There is some interesting work in public key cryptosystems that reduce
> to a *random* instance of a specific problem.
>
> Here is a very cool one:
>
> http://eprint.iacr.org/2009/576
>
...
>
> Unless I misunderstand, if you read someone's plaintext without having
> the private key then you have proven that P=NP!

It is not known, and considered extremely unlikely, that P \neq NP implies 
symmetric-key cryptography, much less public-key cryptography.

The paper you cite reduces security to a hard-on-average problem, whereas 
all that P \neq NP guarantees is hardness in the worst case.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com