Efficient Symmetric-Key Ciphers Based on an NP-Complete Subproblem (DRAFT)


Published: Feb 27, 2000 Updated: Feb 27, 2000 Section: Network Security Library :: Cryptography Author: Company: Cambridge Protocols Workshop Printable Version Adjust font size: Rating: 1/5 - 1 Votes 1 2 3 4 5

We describe a simple, efficient, security primitive based on the Luby-Rackoff (Feistel) construction with small random functions. We show that recovering the internal state of the primitive is NP-Complete. We describe two simple symmetric-key cryptosystems based on the primitive. Turtle is a recursively-structured variable-length block cipher. Hare is a simple keystream generator. The ciphers are efficient on modern computers, and appear to resist various known attacks.

Click Here to download this article