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.)
Are there any NP complete problems related to permuting bit vectors or block cipher constructions?