[Cryptography] List of Proven Secure Ciphers / Hashes
R. Hirschfeld
ray at unipay.nl
Tue Sep 16 21:15:50 EDT 2014
> 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
More information about the cryptography
mailing list