Feistel network
Feistel network is a structural design for block ciphers that achieves invertibility — the property that decryption is the exact inverse of encryption — without requiring the round function itself to be reversible. Invented by Horst Feistel at IBM in the early 1970s, the construction splits the input block into two halves, applies a round function to one half using a subkey, XORs the result with the other half, and swaps the halves for the next round. After an even number of rounds, the final swap is omitted.
The brilliance of the Feistel construction is its separation of cryptographic strength from structural invertibility. The round function can be arbitrarily complex, nonlinear, and non-invertible; the Feistel structure guarantees that the overall cipher remains decryptable regardless. This decoupling allowed the designers of DES — the first widely deployed Feistel cipher — to focus engineering effort on the round function's resistance to differential and linear cryptanalysis without worrying about whether those design choices would break decryption.
The Feistel construction is not without limitations. Its round structure processes data serially — one half depends on the other — which limits the parallelism available in hardware implementations. Modern ciphers like AES, which use substitution-permutation networks rather than Feistel structures, can exploit more parallelism at the cost of requiring the round function itself to be invertible. The trade-off between structural elegance and implementation efficiency explains why Feistel networks dominated the 1970s-1990s but have been largely supplanted in new designs.
Feistel's deeper legacy is conceptual: he demonstrated that the security of a cipher is a property of the overall construction, not of any individual component. A weak round function in a Feistel network is still weak — but the network itself does not add weakness. This is a systems insight that applies beyond cryptography: the robustness of a composite system depends on the integration architecture, not merely on the quality of its parts.