For many cryptographic primitives, e.g., hashing and pseudorandom functions & generators, doubling the output length is useful
even if the doubling transformation is not reversible. For these cases, we present a non-reversible construction based on
a Benes network, as an alternative to the traditional Feistel construction (which is the basis of DES).
Assuming that a given primitive behaves like an n-bit to n-bit random function, we present a length-doubling scheme that yields a 2n-bit to 2n-bit function that provably requires Ω(2n) queries to distinguish with Θ(1) probability from a truly random function of that length. This is true even if the adversary is of unlimited computing
power and is allowed to query the function adaptively. Our construction is minimal in the sense that omitting any operation
makes the resulting network susceptible to birthday attacks using O(2
n/2) queries.
Feistel networks also use truly random n-bit functions to achieve 2n-bit functions. Luby and Rackoff [16] showed that 3 and 4 round Feistel networks require Ω(2
n/2) queries to distinguish with Θ(1) probability from truly random. We show that these bounds are tight by showing that these networks are susceptible various
types of birthday attacks using O(2
n/2) queries.