[Cryptography] State of sin (was Re: What to put in a new cryptography course)

[John Denker]

On 07/12/2016 09:05 AM, Ron Garret wrote:

> The reason P?=NP matters is not because we want crypto algorithms that are in NP.

That's wrong on multiple levels.

First of all, NP is a statement of how /easy/ a problem is.
If you mean NP-hard, please say NP-hard.

More importantly, as Arnold Reinhold explained with commendable clarity
on 07/12/2016 04:37 AM, we do not need breakage to be NP-hard.  All we 
need is hard.

This has been understood since Day One of public key cryptography (1974).
Merkle Puzzles are only polynomial hard.  In fact they are quadratic,
which is a remarkably wimpy polynomial.  However, depending on the
prefactor, and depending on how fast your machine is, this is good
enough for some applications.