2024/04/15 by Alexander Russell, Qiang Tang, Russell, Alexander +3
Computer Science · #Coding theory and cryptography #Cryptographic Implementations and Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Physical Unclonable Functions (PUFs) and Hardware Security
paper · pdf · doi:10.48550/arxiv.2404.09450
openalex publication_date 2024/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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/ε) rounds can transform a subverted random function -- which disagrees with the original one at a small fraction (denoted by ε) of inputs -- into an object that is 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/ε) rounds to achieve crooked-indifferentiable security.