NP complete problems related to permutations of binary vectors or block ciphers

Question

Recently, T.Gowers wrote a blog entry called "How not to prove that P is not equal to NP" about the Razborov/Rudich Natural Proofs paper. He has a construction where he talks about compositions of 3-bit scramblers along with a paper on the subject. Boaz Barak replied to that post with the following comment:

Some other intuition that these scramblers might be hard to distinguish from random is that they seem somewhat related to the designs of block ciphers, and these are actually conjectured by cryptographers to be indistinguishable from random. (And cryptanalysts spend significant time trying to attack these conjectures.)

I'm wondering:

Are there any NP complete problems related to permuting bit vectors or block cipher constructions?

Answer 1

In a strict sense, no. NP is about worst-case hardness. Cryptography requires average-case hardness. $P \ne NP$ implies the existence of problems that are hard in the worst-case (the worst-case running time is super-polynomial) but says nothing about average-case hardness.

For block ciphers, we need average-case hardness. Therefore, there are good reasons to expect that $P\ne NP$ won't be enough.

(There are other reasons to think that $P\ne NP$ is not enough -- see, e.g., Impagliazzo's many worlds of cryptography -- but I'm trying to keep it simple for you.)

In a loose sense, you might be able to find some loose relationship, e.g., where someone builds a block cipher whose security they claim is "based" upon the NP-completeness of some problem. But that kind of claim is on very shaky ground. It's very unlikely they will have proven a theorem that says "if $P\ne NP$, then my block cipher is secure". Instead, they will have some handwavy argument about how the problem is "related", and it'll all be just a bit sketchy.

---

The blog post you mention actually describes a relationship that goes in the opposite way: if secure ciphers exist, then a large class of natural ways of trying to prove $P\ne NP$ are doomed to fail. That's a pretty nifty result.