On Wed, Apr 21, 2010 at 8:49 PM, Jerry Leichter <leich...@lrw.com> wrote:
> There are some concrete complexity results - the kind of stuff Rogoway does, > for example - but the ones I've seen tend to be in the block > cipher/cryptographic hash function spaces. Does anyone one know of similar > kinds of results for systems like RSA? 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 """ Public-Key Cryptographic Primitives Provably as Secure as Subset Sum Vadim Lyubashevsky and Adriana Palacio and Gil Segev Abstract: We propose a semantically-secure public-key encryption scheme whose security is polynomial-time equivalent to the hardness of solving random instances of the subset sum problem. The subset sum assumption required for the security of our scheme is weaker than that of existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC '97), Regev (STOC '03, STOC '05), and Peikert (STOC '09). Additionally, our proof of security is simple and direct. We also present a natural variant of our scheme that is secure against key-leakage attacks, as well as an oblivious transfer protocol that is secure against semi-honest adversaries. """ Unless I misunderstand, if you read someone's plaintext without having the private key then you have proven that P=NP! Nice. :-) Regards, Zooko --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com