<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div><blockquote type="cite"><div style="margin: 0px;"><font color="#000000"><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">On Fri, 5 Sep 2014 16:18 Jerry Leichter wrote:</span></font></div></blockquote></div><blockquote type="cite"></blockquote><div><blockquote type="cite"><font color="#000000"><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></font></blockquote></div><div><blockquote type="cite"><font color="#000000"><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">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.<br><br>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.</span></font></blockquote><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">Exactly.</span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span><blockquote type="cite"><font color="#000000"><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br>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.</span></font></blockquote><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">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.</span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">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</span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"> 2^n = n^k </span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">and solve for k. Taking log2 of both sides:</span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"> n = k log2(n)</span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"> k = n/log2(n)</span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">So if n=128,then k = 18.3.</span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">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. </span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">Arnold Reinhold</span></div><div style="-webkit-text-size-adjust: auto;"><br></div></div><br><span style="-webkit-text-size-adjust: auto;">Sent from my iPhone</span></body></html>