[Cryptography] List of Proven Secure Ciphers / Hashes

[Jerry Leichter]

On Sep 5, 2014, at 3:16 PM, Bear <bear at sonic.net> wrote:
> NP problems are those for which we do not know whether any
> polynomial-time solution exists.  In practice all successful 
> modern ciphers are based on NP problems.
That's not a good way to say it; and, again, if we want to discuss a technical subject on a technical level, details matter.

P: There are problems we know have a poly-time algorithm.
not-P: There are problems we know do *not* have a poly-time algorithm.
Unknown: And, of course, there are problems where we don't know whether there's a poly-time algorithm.

Among problems in Unknown, there is a subset that we know *can* be solved in "non-deterministic polynomial time", something that has a number of equivalent formulations, but is perhaps easiest to visualize as "given a proposed solution, you can check whether it really is one in polynomial time (in the size of the original problem)."  If P=NP, then in fact all of those problems actually are in P.  If P!=NP, at least one of them is not. 

Since NP is a subclass of problems about which we lack some knowledge, it's inherently a "no harder than" descriptions.  There may well be problems that we currently put in NP (because we haven't found a poly-time algorithm for them) which we later determine to be in P.  Linear programming was long in NP - the best algorithm was actually exponential time in the worst case.  Then Karmarker showed that it was actually in P.

Among all the problems in NP, there is a further subclass of the NP-complete problems, which are the "hardest" problems in NP, in the following sense:  If you can find a poly-time algorithm for any NP-complete problem, it will implicitly give you a poly-time algorithm for all problems in NP.

BTW, factoring is in NP, but is not known to be NP-complete.  In fact, there is good reason to believe it is *not* NP-complete.

> For cryptography we want problems that are hard;  but it doesn't 
> really matter whether they are hard in a way that is proportional 
> to an exponential (non-polynomial)function or hard in a way that 
> is proportional to some polynomial of very high degree. It only 
> matters that they are too hard for solving them to be likely or
> practical.
> 
> For example, if there is some problem whose difficulty is O(N^50)
> for N-bit keys of at least some minimum size, then it isn't NP, 
> but it could be suitable for cryptography anyway. 
Actually that's not a good example.

The "hardness" in P and in NP are (a) asymptotic - an NP, or even an NP-complete, problem could be very easy for n up to 10^1000, but *eventually* turn into something for which we know of no poly-time algorithm; (b) about *worst case* time:  If, for every n, there is a one problem of size n such that the difficulty of solving those single, special problems grows faster than any polynomial, then the problem as a whole is not in P, even if "almost all" cases are easy.

Since we do cryptography with a fixed size parameter, and we want "almost all" - probably "all" - of our particular uses of it to be hard, the P and NP classes are simply irrelevant.

On the other hand, the question of asymptotic complexity *does* tell you something about the scaling behavior of your algorithm.  If your algorithm asymptotically takes time 2^n, adding 1 to n doubles the difficulty.  If you algorithm grows as n^50, adding 1 to n grows the difficulty by (n+1/n)^50, which grows pretty slowly even for reasonably small n.  So if you find you chose a security parameter that's too small, recovery for the exponential case may be easy, while recovery for the polynomial case - even with a polynomial of degree 50 - may be difficult.

But just what security parameter *do* you need?  It really depends on the constant terms.  If the "concrete complexity" (something that's usually very difficult to compute:  Real numbers, not just growth rates) of your exponential algorithm is 10^-100*2^n, it's not a reasonable choice unless n is absurdly large; with if you polynomial algorithm has complexity 10^100*n^50, even very small n give you a high degree of security.

Different measures of complexity are good for different things.  Use the wrong measure and your results are meaningless.
                                                        -- Jerry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140905/6278e336/attachment.bin>