## Improving pseudorandom generator on cellular automata with bent functions

### Alla Levina, Daniyar Mukhamedjanov, Gleb Ryaskin, Dmitrij Kaplun

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 381–385 (2018)

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.

### References

- Stephen Wolfram “Random sequence generation by cellular automata”, Advances in Applied Mathematics, 1986
- Andrew Ilachinski “Cellular Automata: A Discrete Universe”, World Scientific, 2001.
- 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
- M. Tomassini, M. Perrenoud “Cryptography with cellular automata”, Appl. Soft Comput., 1(2):151 - 160, 2001
- Mads Haahr “True random number service” www.random.org, 1998
- 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.
- V. B.Kudryavtsev, A.S.Podkolzin, “Cellular automata”, Intellectual systems 1 - 4(10):657 - 692, 2006
- Ferguson, Niels; Schneier, Bruce; Kohno, Tadayoshi, “Chapter 9: Generating Randomness”, Cryptography Engineering: Design Principles and Practical Applications., Wiley Publishing, Inc. 2010
- Richard Brent “Uniform random number generators for supercomputers”, 1992
- 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
- M. Tomassini, “Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time”, Springer, 2005
- 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
- Moore, Edward F “Gedanken-experiments on Sequential Machines”, Automata Studies, Annals of Math. Studies. Princeton, N.J.: Princeton University Press, (34): 129 - 153, 1956
- Weisstein, Eric W. “von Neumann Neighborhood”, MathWorld–A Wolfram Web Resource, http://mathworld.wolfram.com/vonNeumannNeighborhood.html
- Weisstein, Eric W. “Moore Neighborhood” MathWorld–A Wolfram Web Resource, http://mathworld.wolfram.com/MooreNeighborhood.html
- Alberto Dennunzio, Enrico Formenti, Julien Provillard Non-uniform cellular automata:Classes, dynamics, and decidability Journal of Information and Computation, Elsevier, 2012
- Wolfram S. “Cellular Automat” Los Alamos Science 9: 2 - 21, 1983
- Dobbertin H., Leander G. , “A survey of some recent results on bent functions” Sequences and their applications. , SETA, 2004.
- N. N. Tokareva, “Bent functions and their generalizations”, Prikl. Diskr. Mat., 2009, supplement 2, 5 - 17
- 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).