Generating High-Quality Random Numbers by Next Nearest-Neighbor Cellular Automata

Abstract:

Cellular automaton (CA) has been widely investigated as random number generators (RNGs). However, the CA rule and the number of neighbors must be chosen carefully for good randomness. In Ref. [11], non-uniform CA with next nearest neighborhood was applied to generate a pseudo-random sequence. Considering that non-uniform CA has more complex implementation in hardware and needs lager memory to store different rules than uniform CA. In this paper, we propose new RNGs based on uniform CA with next nearest neighborhood. Time spacing technique and NIST statistical test suite are used to find optimal rules for uniform CA. Experiment results show that the sequences generated by uniform CA with optimal rules successfully passed all tests in the NIST suite.

• Periodical: Advanced Materials Research (Volumes 765-767)
• Pages: 1200-1204
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.765-767.1200
• Online since: September 2013
• Authors: Ping Ping, Feng Xu, Zhi Jian Wang
• Keywords: Cellular Automata (CA), Cryptography, NIST Statistical Test Suite, Random Number Generator

References

[1] P. D. Hortensius, R. D. McLeod, W. Pries, D. M. Miller and H. C. Card, Cellular automata-based pseudorandom number generators for Built-In Self-Test, IEEE Trans. Comput. Aid. D 8 (1989) 842-859.

DOI: 10.1109/43.31545

[2] S. U. Guan, S. Zhang, An evolutionary approach to the design of controllable cellular automata structure for random number generation, IEEE Trans. Evolut. Comput. 7 (2003) 23-36.

DOI: 10.1109/tevc.2002.806856

[3] S. U. Guan, S. K. Tan, Pseudorandom number generation with self-programmable cellular automata, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 23 (2004) 1095–1101.

DOI: 10.1109/tcad.2004.829808

[4] B. H. Kang, D. H. Lee, C. P. Hong, High performance pseudorandom number generator using two-dimensional cellular automata, In: 4th IEEE International Symposium on Electronic Design, Test & Application, Enero, 2008, pp.597-602.

DOI: 10.1109/delta.2008.46

[5] S. Wolfram, Random sequence generation by cellular automata, Advances in applied mathematics 7 (1986) 123-169.

DOI: 10.1016/0196-8858(86)90028-x

[6] W. Meier, O. Staffelbach, Analysis of pseudo random sequences generated by cellular automata, Advances in Cryptology: Proceedings of EUROCRYPT, 1991, pp.186-199.

DOI: 10.1007/3-540-46416-6_17

[7] M. Tomassini, M. Sipper, and M. Perrenoud, On the generation of high-quality random numbers by two-dimensional cellular automata, IEEE Trans. Comput. 49 (2000) 1146-1151.

DOI: 10.1109/12.888056

[8] R. Dogaru, Hybrid cellular automata as pseudo-random number generators with binary synchronization property, International Symposium on Signals, Circuits and Systems, 2009, pp.1-4.

DOI: 10.1109/isscs.2009.5206126

[9] K. Chakraborty, D. Chowdhury, CSHR: Selection of Cryptographically Suitable Hybrid Cellular Automata Rule, In: 10th International Conference on Cellular Automata for Research and Industry, ACRI 2012, pp.591-600.

DOI: 10.1007/978-3-642-33350-7_61

[10] F. Seredynski, P. Bouvry, A. Zomaya, Cellular automata computation and secret key cryptography, Parallel Computation 30 (2004) 753-766.

DOI: 10.1016/j.parco.2003.12.014

[11] M. Szaban, F. Seredynski, P. Bouvry, Collective behavior of rules for cellular automata-based stream ciphers, In: IEEE Congress in Evolutionary Computation, 2006, pp.179-183.

DOI: 10.1109/cec.2006.1688306

[12] Rukhin A et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication 800-22 (with revisions dated April, 2010).

[13] M. Tomassini, M. Sipper, M. Zolla, M. Perrenoud, Generating high-quality random numbers in parallel by cellular automata, Future Generation Computer System 16 (1999) 291-305.

DOI: 10.1016/s0167-739x(99)00053-9