[145267] in cryptography@c2.net mail archive
Re: What's the state of the art in factorization?
daemon@ATHENA.MIT.EDU (Jonathan Katz)
Fri Jul 9 12:27:40 2010
Date: Thu, 22 Apr 2010 14:40:07 -0400 (EDT)
From: Jonathan Katz <jkatz@cs.umd.edu>
To: "Zooko O'Whielacronx" <zookog@gmail.com>
cc: cryptography@metzdowd.com
In-Reply-To: <t2ncd6401a1004221008o591f281ama934ad3cf8479aee@mail.gmail.com>
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@metzdowd.com
