Paper about a new encryption method that also prove that P != NP
eprint.iacr.org
eprint.iacr.org
This is a stream cipher with a large internal state. The author argues that it is logically impossible to deduce the internal state by any means faster than a slow algebraic method (exponential time in ... some variable, I'm not sure).
The most questionable thing I noticed right away is that the author says that there can't be statistical biases or regularities in the stream cipher output because certain parameters are XORed with the output byte position mod 256, which supposedly gets rid of any possible statistical regularities.
> The L and K values are also XORed with n mod 256. This is done because some key combinations may cause regularities in the g(m) values, and XORing with n mod 256 ensures that all L and K values contain all values between 0 and 255. For example, if we didn't XOR the K and L values with n mod 256, and all key values in table A were 2, and all other key values in the other tables were 0, then K and L would always be 2. This means that we would be XORing even table key values with an even number, and all other bits would always be 0, so all fm values would be 2. Even though the attacker knows the value of n (and therefore n mod 256), the use of L and K ensures that the attacker does not gain any advantage from this knowledge. [...] XORing the L and K values with n mod 256 ensures that the Zn values are statistically evenly distributed for all possible key combinations.
I'm super-skeptical of this claim. Your stream cipher might have statistical bias, so you introduce the current output byte position (also admittedly known to the attacker) as part of the internal state, and now you're sure that there can no longer be any statistical bias?
The paper then argues that there's no analytic solution to find the internal state faster than this exponentially hard brute-force-esque solution (or maybe that it's very statistically unlikely that the attacker could get an advantage in trying to find the internal state more quickly). I think this explicitly refers back to the idea that there are no statistical regularities in the output and some kind of argument that any bit value is in some sense possible in any position (?). OK, but any bit value possible in any position isn't enough to show that there couldn't be an analytic solution that uses successive bytes to efficiently eliminate large numbers of possibilities about the internal state... and I still feel like the statistical regularity thing is pretty much being asserted without proof.
> Since there is at least one algorithm (WESP) that is NP (verifiable in polynomial time) but not P (solvable in polynomial time), P cannot be the same set as NP.