<div dir="ltr"><p dir="ltr">ITT: Lodewijk trolls (fellow?) cryptonerds by mentioning P=NP. Sorry about glossing over so much that it seems legit but is actually false in many ways of looking at the situation.</p>
<p dir="ltr">The constant time argument is cheating; a large enough constant always exceeds there result of a function ( when working in |R ). Although I definitely agree that one needn't something NP hard to work as crypto. Mixing functions like AES or hashes are quite different from asymetric crypto, asymetric crypto has sterner demands on key shortness and computational time. (Someone glossed over the fact that larger keys are much much slower to compute, which (atm) really does become a problem exponentially fast ;) )</p><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-family:arial,sans-serif;font-size:13px">Assumption 1: We are talking about asymptotic security (as a function of key length), not concrete security. Why? Because if you care about concrete security, then P and NP are irrelevant since, as a previous person noted, any scheme with some fixed key length k can be broken in *constant* time 2^k.</span></blockquote><div><br></div><div>The last part depends on how the break works. By crawling 2^k you've found all possible inputs, not the one you actually meant. Especially when stacking algorithms that makes a huge difference. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-family:arial,sans-serif;font-size:13px">Let's let n -- a parameter! -- denote the length of the key.</span></blockquote><div>Now N correlates with both "security factor" and computational time</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-family:arial,sans-serif;font-size:13px">Assumption 2: Encryption runs in time polynomial in n.<br></span><span style="font-family:arial,sans-serif;font-size:13px">You can question this assumption, and in fact it might be meaningful to allow encryption to run in time  n^{log n}. But this is the assumption I am making.</span></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">Assumption 3: You want security to hold against all polynomial-time adversaries.<br></span><span style="font-family:arial,sans-serif;font-size:13px">You can question this assumption, and in fact it might be meaningful to only require security for adversaries running in time n^10 (but not those running in time n^11). But this is the assumption I am making.</span></blockquote><div><br></div><div>Well said. Adversaries are usually not theoretical. But we're usually looking for multiple orders of excess safety, against attackers 1000-10,000 times faster (than current known best) over long periods of time. It's still also cheating, of course, because polynomials can grow pretty fast too.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-family:arial,sans-serif;font-size:13px">We must also fix a notion of security. For concreteness, let's use the notion of CPA-security (i.e., security against chosen-plaintext attacks); see the Katz-Lindell textbook for formal definitions. CPA-security, as defined there, already incorporates Assumptions 1, 2, and 3.</span><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">Now, what I claim is:<br></span><span style="font-family:arial,sans-serif;font-size:13px">If P=NP, then no public-key or symmetric-key encryption scheme is CPA-secure.</span></blockquote><div><br></div><div>I think that the assumptions (esp 3) are too strong for grarpamp purposes. I'll look at the CPA-secure definition later, but I suspect it is also too strong. Then again, what secure meant was not really specified anyway.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-family:arial,sans-serif;font-size:13px">NP just isn't the hardest class of problems out there.</span></blockquote><div> </div><div>I think I was confusing NP with NP-hard, but this is probably the strongest counter argument out there! Haven't heard of crypto with decryption in NP-hard but not in NP (would love to be pointed at it, if it's out there!).</div><div><br></div><div>Getting back to grarpamp:</div><div><span style="font-family:arial,sans-serif;font-size:13px">formally proofed secure crypto besides the </span><span style="font-family:arial,sans-serif;font-size:13px">one time XOR?<br></span><br>There's proofs with the right assertions, which is all proofs usually are. OTP still assumes a good source of randomness (which can be impossible). Most others a hard problem (notable discrete log, prime factorization, such things). Some (symmetric crypto) merely attempt to mix data such that it doesn't turn homogenous (remains high in entropy/uses the output space optimally) but also mixes thoroughly (all input (bits) is (are) represented in all the output (bits)) without there being any determinable relationship between in and output. We've gotten quite good at symetric, given that AES looks a lot like DES but still nobody really found a problem with it (biclique isn't that big a deal). AES is also ridiculously fast for how good the encryption is. Asymmetric is still quite hard, given basically everyone is worried basically everything out there. We all stick our heads in the sand when someone mentions quantum computing.</div><div><br></div><div>What would proving AES even mean? Did anyone ever prove a cipher to be secure? I guess you could construct a symetric cipher from asymetric crypto, copypaste proof that asserts the security of the underlying problem (and probably P!=NP) and call it a day.</div><div><br></div><div>Thanks for participating guys, you actually make me feel guilty not studying this stuff harder and more formally correctly.</div>
</div>