Crooked indifferentiability of the Feistel Construction
<|reference_start|>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/\log(1/\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/\log(1/\epsilon)$ rounds to achieve crooked-indifferentiable security.<|reference_end|>
@article{russell2024crooked,
    title={Crooked indifferentiability of the Feistel Construction},
    author={Alexander Russell, Qiang Tang, Jiadong Zhu},
    journal={arXiv preprint arXiv:2404.09450},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.09450},
    primaryClass={cs.CR}
}