[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