[Cryptography] List of Proven Secure Ciphers / Hashes

Arnold Reinhold agr at me.com
Sun Sep 7 17:06:39 EDT 2014


> On Fri, 5 Sep 2014 16:18 Jerry Leichter wrote:
> 

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

Exactly.

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

An interesting point, but it is worth plugging in some numbers. Say you are using a 128-bit key with your n^50 algorithm family and want to know the improvement adding one key bit brings. (129/128)^50 = 1.47566…, a little more than the square root of two. So you will need to add two bits to double the strength, compared to one bit for a 2^n strength algorithm, not a big problem. For an n^20 algorithm, you’ll need to add 5 bits to a 128-bit key to double strength, again not so unreasonable.

It is also worth computing the break-even point between a family of polynomial-time algorithms whose strength grows as n^k vs a 2^n exponential-time algorithm family, assuming the same constant multiplier, say one. So do so, set

    2^n = n^k 

and solve for k. Taking log2 of both sides:

   n = k log2(n)
   k = n/log2(n)

So if n=128,then  k = 18.3.

In other words, an algorithm family whose difficulty grows as n^19  will be stronger than one that grows as 2^n when n<=128, again assuming the same constant multipliers. So the notion that P algorithms are necessarily tractable while exponential ones are not really falls apart at values relevant to cryptography. 


Arnold Reinhold


Sent from my iPhone
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140907/58d55084/attachment.html>


More information about the cryptography mailing list