[OPTICAL REVIEW Vol. 5, No. 3 (1998) 143-151]

Two-Dimensional Cellular Automata for Pseudo-Random Pattern Generators and for Highly Secure Stream Ciphers

Maria MADJAROVA, Mitsugu KAKUTA, Takashi OBI, Masahiro YAMAGUCHI and Nagaaki OHYAMA*

Imaging Science and Engineering Laboratory, Tokyo Institute of Technology, 4259, Nagatsuta, Midori-ku, Yokohama, 226-8503 Japan

(Received December 8, 1997; Accepted March 24, 1998)

Pseudo-random properties of a class of two-dimensional (2-D) 5-neighborhood cellular automata (CA), built around nonlinear (OR, AND) and linear (XOR) Boolean functions are studied. The site values at each step of the 2-D CA evolution are taken in parallel and form pseudo-random sequences, which satisfy the criteria established for pseudo random number generator (PRNG): long period, excellent random qualities, single bit error propagation (avalanche criteria), easy and fast generation of the random bits. A block-scheme for secure Stream Cipher based on 2-D CA is proposed. The 2-D CA based PRNG algorithm has simple structure, use space-invariant and local interconnections and can be easily realized in very large scale integration or parallel optoelectronic architectures.

Key words : data encryption, stream cipher, pseudo-random number generation, two-dimensional cellular automata, parallel algorithms, parallel opto-electronic architectures

* yama@isl.titech.ac.jp