Colloquium Archive

Luby and Rackoff showed how to construct pseudo-random permutations from pseudo-random functions; their paper formalized the concept of a secure block cipher. Their goal was to understand what makes the U.S. Data Encryption Standard (DES) secure. The technique is based on composing several Feistel permutations. The Feistel permutation, a fundamental building block of DES, involves applying a so-called round function to the right half of the input and taking the XOR with the left half of theinput. We consider the question of what happens when operations other than the XORare applied. In particular, we engage in a study of Luby-Rackoff ciphers when the operation in the underlying Feistel network is addition over an arbitrary finite algebraic structure. We obtain the following results: We construct a Luby-Rackoff cipher which can be easily broken when XOR is used, but is secure against adaptive chosen plaintextand ciphertext attacks when addition in finite groups of characteristic greater than 2 are considered. This cipher has better time/space complexity and uses fewer random bits than all previously considered Luby-Rackoff ciphers. We show that our construction is tight when operations are performed over a finite field, and a minor relaxation in one ofthe requirements results in it being insecure, though the attack here is non-obvious. We examine various other Luby-Rackoff ciphers known to be insecure under XOR. In some cases, we can break these ciphers over arbitrary Abelian groups --- though we have to employ new more complex techniques. In other cases, however, the security remains an open problem. This talk is based on joint work with Sarvar Patel and Ganesh Sundaram of Lucent Technologies/Bell Labs, and appeared in SAC 2002.