[ Changed 25th January 1997 ]
A useful principle in cipher design is to reduce or at least relate closely the cryptanalysis of the cipher to some long-studied problem that is believed to be difficult. Most public-key ciphers follow this principle fairly closely (e.g., RSA is at least similar to factoring). Modern symmetric-key ciphers, on the other hand, can rarely be reduced in this way and so are frequently designed specifically to resist the various known cryptanalytic attacks. In this informal talk, we examine a simple cipher primitive, based on Feistel networks, for which recovery of its internal state given its inputs and outputs is NP-complete. We outline simple and efficient block- and stream- cipher constructions based on this primitive.