[Cryptography] List of Proven Secure Ciphers / Hashes

[R. Hirschfeld]

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