[Cryptography] List of Proven Secure Ciphers / Hashes

[Dennis E. Hamilton]

<orcnote> below.

-----Original Message-----
From: cryptography [mailto:cryptography-bounces+dennis.hamilton=acm.org at metzdowd.com] On Behalf Of Jerry Leichter
Sent: Monday, September 15, 2014 10:18
To: Miroslav Kratochvil
Cc: Cryptography Mailing List; grarpamp
Subject: Re: [Cryptography] List of Proven Secure Ciphers / Hashes

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

<orcnote>
This is in Chapter 11, Additional Classes of Problems.  They are more circumspect.  In the second paragraph of Chapter 11, "However, it is likely that co-NP is different from both [of] these classes [P and NP], and in fact *likely* that no NP-complete problem is in co-NP." (emphasis on *likely* mine).

They go on, in their sketch of the chapter, to observe that "We shall see that testing primes is both in NP and co-NP, and therefore it is *unlikely* that we can prove primality testing to be NP-complete."  And so it goes.