What's the state of the art in factorization?

Jonathan Katz jkatz at cs.umd.edu
Thu Apr 22 14:40:07 EDT 2010

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

More information about the cryptography mailing list