1-Resiliency of Bipermutive Cellular Automata Rules


It is known that CA rules which are both leftmost and rightmost permutive (bipermutive rules) are expansively and mixing chaotic. In this paper, we prove that bipermutive rules also satisfy the condition of 1-resiliency (that is, balancedness and first order correlation-immunity), which is an important property used in the design of pseudorandom number generators for cryptographic purposes. We thus derive an enumerative encoding for bipermutive rules based on a graph representation, and we use it to generate all the 256 bipermutive rules of radius 2. Among these rules we select the ones which satisfy additional cryptographic properties: high nonlinearity and 2-resiliency. Finally, we assess the quality of the pseudorandom sequences generated by these remaining rules with the ENT and NIST statistical test suites, taking the elementary rule 30 as a benchmark.

Cellular Automata and Discrete Complex Systems - 19th International Workshop, AUTOMATA 2013, Giessen, Germany, September 17-19, 2013. Proceedings

Note: this paper has been extended in this journal publication.