Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 15

Proceedings of the 2018 Federated Conference on Computer Science and Information Systems

Improving pseudorandom generator on cellular automata with bent functions

, , ,

DOI: http://dx.doi.org/10.15439/2018F234

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 381385 ()

Full text

Abstract. Nowadays the practice of researching pseudorandom number generators (PRNG) becomes more scalable because of its spreading in many spheres of computer science and, especially, cybersecurity. The problem is that existing generators are still have many disadvantages in terms of velocity, complexity or flexibility. Thus, the area of researching new algorithms of generating pseudorandom sequences is more than just applicable method, but the target for multiplying cybersecurity from the hardware to application level. This leads to make the set of available and useful PRNG larger and better by their features, like velocity, performance, simplicity in realization. These features match PRNG, based on cellular automata (CA), but not all rules, used in CA are appropriate for their transition functions. Bent functions are perfectly complement statistical weakness of some rules because of their non-linearity without loss of other features.


  1. Stephen Wolfram “Random sequence generation by cellular automata”, Advances in Applied Mathematics, 1986
  2. Andrew Ilachinski “Cellular Automata: A Discrete Universe”, World Scientific, 2001.
  3. M. Tomassini, M. Sipper, and M. Perrenoud “On the generation of high-quality random numbers by two-dimensional cellular automata” IEEE Transactions on Computers, 49(10):1146 - 1151, Oct 2000
  4. M. Tomassini, M. Perrenoud “Cryptography with cellular automata”, Appl. Soft Comput., 1(2):151 - 160, 2001
  5. Mads Haahr “True random number service” www.random.org, 1998
  6. M. Tomassini, M. Sipper, M. Zolla, M. Perrenoud, “Generating high-quality random numbers in parallel by cellular automata”, Future Gener.Comput. Syst., 16(2 - 3):291 - 305, December 1999.
  7. V. B.Kudryavtsev, A.S.Podkolzin, “Cellular automata”, Intellectual systems 1 - 4(10):657 - 692, 2006
  8. Ferguson, Niels; Schneier, Bruce; Kohno, Tadayoshi, “Chapter 9: Generating Randomness”, Cryptography Engineering: Design Principles and Practical Applications., Wiley Publishing, Inc. 2010
  9. Richard Brent “Uniform random number generators for supercomputers”, 1992
  10. A. L. Rukhin, “A statistical test suite for random and pseudorandom number generators for cryptographic applications”, U.S. Dept. of Commerce, Technology Administration, National Institute of Standards and Technology, rev. edition, 2010
  11. M. Tomassini, “Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time”, Springer, 2005
  12. Toru Sasaki, Hiroyuki Togo, Jun Tanidaa and Yoshiki Ichiokab “Stream cipher based on pseudo-random number generation using optical affine transformation”, Applied Optics, 39(14):2340 - 6 Âů June 2000
  13. Moore, Edward F “Gedanken-experiments on Sequential Machines”, Automata Studies, Annals of Math. Studies. Princeton, N.J.: Princeton University Press, (34): 129 - 153, 1956
  14. Weisstein, Eric W. “von Neumann Neighborhood”, MathWorld–A Wolfram Web Resource, http://mathworld.wolfram.com/vonNeumannNeighborhood.html
  15. Weisstein, Eric W. “Moore Neighborhood” MathWorld–A Wolfram Web Resource, http://mathworld.wolfram.com/MooreNeighborhood.html
  16. Alberto Dennunzio, Enrico Formenti, Julien Provillard Non-uniform cellular automata:Classes, dynamics, and decidability Journal of Information and Computation, Elsevier, 2012
  17. Wolfram S. “Cellular Automat” Los Alamos Science 9: 2 - 21, 1983
  18. Dobbertin H., Leander G. , “A survey of some recent results on bent functions” Sequences and their applications. , SETA, 2004.
  19. N. N. Tokareva, “Bent functions and their generalizations”, Prikl. Diskr. Mat., 2009, supplement 2, 5 - 17
  20. Carlet C., “On the higher order nonlinearities of Boolean functions and S-boxes, and their generalizations “ The Fifth Int. Conf. on Sequences and Their Applications , SETA, 2008 P. 345 - 367 (Lecture Notes in Comput. Sci. V. 5203).