Designing Conflict Free Cellular Automata-Based PRNG
Miroslaw Szaban and Franciszek Seredynski
In this paper, we consider a problem of an appropriate selection of rules for one-dimensional (1D) cellular automata (CA), which is used for generation of high-quality pseudorandom sequences useful in cryptography. The quality of pseudorandom bit sequences generated by CAbased pseudorandom number generator (PRNG) depends on a collective behavior of rules assigned to CA cells. We present a new method of selection of CA rules, based on a cryptographic criterion known as a balance. The proposed method selects a maximal size set of available CA rules for a given neighbourhood radius and suitable for PRNG, guarantees avoiding conflicting assignments of rules resulting in the creation of unwanted stable bit sequences, and provides a high quality of pseudorandom sequences. We use the method to verify already known from the literature CA rules used for 1D CA-based PRNG, and also present a new set of CA rules with neighbourhood radius r = 2, which can be used in CA-based PRNG and provide cryptographically strong bit sequences and huge key space.
Keywords: Cellular automata, pseudorandom number generator, balance, boolean function, cryptography.