[Cryptography] List of Proven Secure Ciphers / Hashes

John Denker jsd at av8n.com
Mon Sep 8 13:03:03 EDT 2014


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 wouldn't have said that.

I've seen any number of hand-wavy arguments that 
"P = NP" would spell the end of public-key crypto, 
or worse.  However, all of these arguments seem 
seriously flawed to me.  I reckon that even if it 
turns out that P=NP, we can still do crypto, including 
public-key crypto.  This is true twice over, both 
at the low end and the high end.

At the low end:  Consider the first known asymmetric 
crypto algorithm, Merkle's puzzles
  http://merkle.com/1974/
The work factor is only polynomial (indeed quadratic, 
which is not a particularly fancy polynomial) in the 
sense that the bad-guy work is only the square of the 
good-guy work.  If you square a sufficiently large 
number, you win.  Higher-order polynomials work even 
better.

To say the same thing another way:  We need breakage
to be hard.  It doesn't need to be infinitely hard,
or even exponentially hard.

At the high end:  If P=NP, you can always choose 
something that is not in NP, i.e. harder than NP.
I haven't seen much work done in this direction, 
which is understandable given that most people are 
betting that P ≠ NP, but it remains a possibility 
in principle.

=======================

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.

 *) P is a category of easiness.

 *) NP is also a category of easiness.  It means if
  you have a guess as to the answer, you can check
  it in polynomial time.  This implies that if you
  are given unlimited hardware running in parallel,
  you can /find/ the answer in polynomial time,
  because you can just check all possibilities.

  Obviously P is contained within NP.

 *) P_HARD is a category of hardness.  It means a 
  problem is at least as hard as the hardest thing
  in P.

 *) NP_HARD is a category of hardness.  It means a
  problem is at least as hard as the hardest thing
  in NP.

 *) NP_COMPLETE means a problem is both NP_HARD
  and NP.  In other words, it is exactly as hard
  as the hardest thing in NP (within a polynomial
  scale factor).

  Please do not say NP when you mean NP_HARD.
  Please do not say NP when you mean NP_COMPLETE.

 *) There are lots of things that are not in NP,
  meaning they are harder than NP, and therefore
  harder than NP_COMPLETE.

  ++ Some things take exponential time -- worse 
   than any polynomial -- even if you have unlimited
   hardware.

  ++ Some things take combinatorial time -- worse
   even than exponential.

  ++ Some things are just plain undecidable, such
   as the infamous halting problem.

A decent discussion with inclusion diagrams and examples 
of harder-than-NP problems can be found at
  http://en.wikipedia.org/wiki/EXPTIME



More information about the cryptography mailing list