On Thu, Apr 22, 2010 at 12:40 PM, Jonathan Katz <jk...@cs.umd.edu> wrote: > On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote: > >> Unless I misunderstand, if you read someone's plaintext without having >> the private key then you have proven that P=NP! … > 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.
I see. I did misunderstand. So although cracking the Lyubashevsky, Palacio, Segev encryption scheme [1] doesn't mean that you've proven P=NP, because NP is about worst-case rather than average-case, it *does* mean that you've solved the subset sum problem for a random instance. If you can do that for all keys that people use in real life then you can solve the subset sum problem for almost all random instances, which seems like it would still be a breakthrough in complexity theory. If you can do it for only a few keys then this means that the Lyubashevsky, Palacio, Segev scheme is susceptible to "weak keys". Is that right? Anyway, although this is not one, there do exist proposals for public key crypto schemes where breaking the scheme implies solving a worst case instance of a supposedly hard problem, right? Here is a recent paper which surveys several of them (all lattice-based) and estimates secure key sizes: [2]. None of the signature schemes mentioned therein appear to have the sort of efficiency that we are used to. For example the "ecdonaldp" (ECDSA) signature schemes measured on http://bench.cr.yp.to/results-sign.html have key sizes on the order of tens of bytes, where the most efficient digital signature algorithm described in [2] has key sizes on the order of thousands of bytes. (And that one is a one-time signature scheme!) Okay, so I'm still searching for a signature algorithm which has the following properties (or as many of them as I can get): 1. efficient (signing time, verification time, key generation time, key size, signature size) 2. some kind of strong argument that it really is secure (the gold standard would be reduction to a worst-case instance of an NP-complete problem) or, if we can't have (2) then at least we want (3) and (4): 3. rather different from ECDSA, so that a breakthrough is unlikely to invalidate both ECDSA and this other scheme at once and 4. not known to be vulnerable to quantum computers and finally but importantly: 4. easy to understand and to implement Suggestions welcome! Regards, Zooko Wilcox-O'Hearn [1] http://eprint.iacr.org/2009/576 [2] http://eprint.iacr.org/2010/137 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com