[Cryptography] List of Proven Secure Ciphers / Hashes
R. Hirschfeld
ray at unipay.nl
Mon Sep 8 16:13:56 EDT 2014
> Date: Mon, 08 Sep 2014 10:03:03 -0700
> From: John Denker <jsd at av8n.com>
>
> On 09/07/2014 07:56 PM, R. Hirschfeld wrote:
> > Even though they are defined in terms of worst-case rather than
> > average-case complexity, I wouldn't say that P and NP are irrelevant.
> > If P = NP then there are no one-way functions, and no hard on average
> > problems (in NP).
> I've seen any number of hand-wavy arguments that "P = NP" would
> spell the end of public-key crypto, or worse.
I didn't say that, just the statement above. I don't disagree with
anything you wrote, but I don't think it contradicts my statement.
Both one-way functions and hard on average problems have very specific
technical definitions. They are widely believed to be important
(although perhaps not critical) for public-key crypto. The existence
of either implies P != NP.
> By way of background: P and NP are highly specific technical terms.
> Unless there is a compelling reason to redefine them, please let's
> stick to the established meanings.
I certainly can't think of a compelling reason to redefine them! The
usual practice when a complexity class doesn't capture what you're
after is to define a new one, and there's a whole zoo full of them.
BTW, avgP and distNP are average-case analogues of P and NP.
> Please do not say NP when you mean NP_HARD.
> Please do not say NP when you mean NP_COMPLETE.
I wouldn't dream of it!
Perhaps you object to my parenthetical "(in NP)"? I added that only
to make it clear that I was excluding even harder problems (e.g. in
EXPTIME), although this might be implicit from the definition of hard
on average. I did not mean NP-hard or NP-complete.
> ++ Some things are just plain undecidable, such as the infamous
> halting problem.
And above that there is the arithmetic hierarchy, of which the
polynomial-time hierarchy is an analogue (with P analogous to
recursive and NP analogous to r.e., etc.). And above that...
More information about the cryptography
mailing list