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