[Cryptography] List of Proven Secure Ciphers / Hashes

[Jerry Leichter]

On Sep 15, 2014, at 6:17 AM, Miroslav Kratochvil <exa.exa at gmail.com> wrote:
> Anyway, for the other folks here - I always wanted to ask - can RSA be reduced to some at-least-pretty-hard complexity class?
No.  RSA is no harder than factoring (we still have no proof that it's *as hard as factoring*).  Factoring is in the intersection of NP and co-NP, the class of decision problems whose complement is in NP.  (The "decision problem for factoring is":  Does N have a factor other than itself or 1?  This is obviously in NP because if I give you a proposed factor m, you can quickly compute the GCD and check.  Membership in co-NP is checked by a deterministic version of primality testing (AKS algorithm).)

If there were an NP-complete problem in that intersection, then NP and co-NP would be the same - which is "thought to be false".  However I haven't been able to find any argument for *why* this is thought to be false - every reference I could find simply states this.  (http://en.wikipedia.org/wiki/Co-NP refers this statement to the 2nd edition of Hopcraft's "Introduction to Automata Theory..." but I don't have a copy handy to check right now.)
                                                        -- Jerry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140915/b95f86d4/attachment.bin>