Cryptographic Properties of Bipermutive Cellular Automata Rules
Alberto Leporati and Luca Mariot
Bipermutive rules are known to induce both expansive and mixing chaotic cellular automata. In this paper, we study some cryptographic properties of bipermutive rules, initially proving that they also satisfy 1-resiliency, which combines balancedness and first order correlation immunity. We thus carry out an exhaustive exploration of the 256 bipermutive rules of radius 2, in order to select those rules satisfying additional cryptographic criteria (2-resiliency and high nonlinearity), and we test them through the ENT and NIST statistical test suites. We then complete the theoretical analysis of bipermutive rules by showing how several other properties (algebraic degree, nonlinearity, k-resiliency, number of linear structures) can be deduced by the properties of their generating functions. Finally, we explore the set of bipermutive rules having radius 3, always selecting the ones which satisfy the best tradeoffs among the considered properties, and we test them as well with the ENT and NIST suites.
Keywords: Cellular automata, boolean functions, pseudorandom number generators, stream ciphers, block ciphers, permutivity, resiliency, nonlinearity, strict avalanche criterion, Walsh transform, ENT test suite, NIST test suite.