Cryptographic Properties of Bipermutive Cellular Automata Rules


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.

J. Cellular Automata

Note: this publication is an extended version of this conference paper.