Crooked indifferentiability of the Feistel Construction

The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks – that is, adversarial subversion – of the component round functions. Specifically, we establish that a Feistel-based construction with more than $2000n\mathrm{/}\log (1\mathrm{/}\epsilon )$ rounds can transform a subverted random function – which disagrees with the original one at a small fraction (denoted by $\epsilon$) of inputs – into an object that is \emph{crooked-indifferentiable} from a random permutation, even if the adversary is aware of all the randomness used in the transformation. We also provide a lower bound showing that the construction cannot use fewer than $2n\mathrm{/}\log (1\mathrm{/}\epsilon )$ rounds to achieve crooked-indifferentiable security.