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:



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 majord...@metzdowd.com

Reply via email to