[Cryptography] List of Proven Secure Ciphers / Hashes

[R. Hirschfeld]

> From: Jerry Leichter <leichter at lrw.com>
> Date: Mon, 15 Sep 2014 13:18:10 -0400

> 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).)

I think the decision problem you describe is actually in P, and is
just composites (or primes).  The decision problem for factoring is
usually something along the lines of: Does N have a (non-trivial)
factor less than m? (where 1 < m < N).  You can then do binary search
on m to extract the factors.

> 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.)

Here's an argument (I don't know whether you'll find it convincing):
There are many problems known to be NP-complete.  None of their
complements are known to be in NP.

Ray