On the Pseudorandomness of Top-Level Schemes of Block Ciphers

Block ciphers are usually basedon one top-level scheme into which we plug “roundf unctions”. To analyze security, it is important to study the intrinsic security provided by the top-level scheme from the viewpoint of randomness: given a block cipher in which we replaced the lower-level schemes by idealized oracles, we measure the security (in terms of best advantage for a distinguisher) depending on the number of rounds and the number of chosen plaintexts. We then extrapolate a sufficient number of secure rounds given the regular bounds provided by decorrelation theory.This approach allows the comparison of several generalizations of the Feistel schemes andot hers. In particular, we compare the randomness provided by the schemes used by the AES candidates.In addition we provide a general paradigm for analyzing the security provided by the interaction between the different levels of the block cipher structure.