SpringerLink
Log in

Asynchronous Cellular Automata as Randomness Enhancer

  • Conference paper
  • First Online:
Proceedings of First Asian Symposium on Cellular Automata Technology (ASCAT 2022)

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 1425))

Included in the following conference series:

  • 117 Accesses

Abstract

This work explores randomness enhancing capability of asynchronous cellular automata. This paper first reports theoretical results to identify elementary cellular automata under fully asynchronous updating scheme with large cycle of length \(2^n\) or \(2^n - 1\). To predict the pseudo-random number generation capability, we classify these large cycle asynchronous cellular automata into fully and partially exposed systems. Finally, it is observed that asynchronous cellular automata are able to improve randomness quality of a ‘poor’ random number generator.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 149.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 199.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Wolfram, S.: A New Kind of Science. Wolfram-Media Inc., Champaign, Ilinois, United States (2002)

    MATH  Google Scholar 

  2. von Neumann, J.: The Theory of Self-reproducing Automata, A. W. Burks ed. Univ. of Illinois Press, Urbana and London (1966)

    Google Scholar 

  3. Chaudhuri, P.P., Chowdhury, D.R., Nandi, S., Chatterjee, S.: Additive cellular automata—theory and applications. IEEE Comput. Soc. Press USA 1 ISBN 0-8186-7717-1 (1997)

    Google Scholar 

  4. Bhattacharjee, K., Naskar, N., Roy, S., Das, S.: A survey of cellular automata: types, dynamics, non-uniformity and applications. Natural Comput. 19, 433–461 (2020)

    Article  MathSciNet  Google Scholar 

  5. Wolfram, S.: Cryptography with cellular automata. In: Williams, H.C. (Ed.) Advances in Cryptology—CRYPTO ’85 Proceedings, pp. 429–432. Springer, Berlin, Heidelberg (1986)

    Google Scholar 

  6. Damgård, I.B.: A design principle for hash functions. In: Brassard, G. (Ed.) Advances in Cryptology—CRYPTO’ 89 Proceedings, pp. 416–427. Springer, New York (1990)

    Google Scholar 

  7. Kurka, P.: Languages, equicontinuity and attractors in cellular automata. Ergodic Theory Dyn. Syst. 17, 417–433 (1997)

    Article  MathSciNet  Google Scholar 

  8. Meier, W., Staffelbach, O.: Analysis of pseudo random sequence generated by cellular automata. In: Advances in Cryptology—EUROCRYPT ’91, Workshop on the Theory and Application of of Cryptographic Techniques, Brighton, UK, April 8–11,: Proceedings, ser. Lecture Notes in Computer Science, vol. 547. Springer 1991, 186–199 (1991)

    Google Scholar 

  9. Hortensius, P.D., McLeod, R.D., Card, H.C.: Parallel random number generation for vlsi systems using cellular automata. IEEE Trans. Comput. 38(10), 1466–1473 (1989)

    Article  Google Scholar 

  10. Adak, S., Bhattacharjee, K., Das, S.: Maximal length cellular automata in \(gf\)(q) and pseudo-random number generation. Int. J. Modern Phys. C 31(03), 2050037 (2020)

    Article  MathSciNet  Google Scholar 

  11. Cori, R., Metivier, Y., Zielonka, W.: Asynchronous map**s and asynchronous cellular automata. Inform. Comput. 106(2), 159–202 (1993)

    Article  MathSciNet  Google Scholar 

  12. Droste, M., Gastin, P., Kuske, D.: Asynchronous cellular automata for pomsets. Theoret. Comput. Sci. 247(1–2), 1–38 (2000)

    Article  MathSciNet  Google Scholar 

  13. Sethi, B., Roy, S., Das, S.: Asynchronous cellular automata and pattern classification. Complexity 21(S1), 370–386 (2016)

    Article  MathSciNet  Google Scholar 

  14. Sethi, B., Das, S.: On the use of asynchronous cellular automata in symmetric-key cryptography. In: Mueller, P., Thampi, S.M., Alam Bhuiyan, M.Z., Ko, R., Doss, R., Alcaraz Calero, J.M. (Eds.) Security in Computing and Communications, pp. 30–41. Springer, Singapore (2016)

    Google Scholar 

  15. Manzoni, L., Mariot, L.: Cellular automata pseudo-random number generators and their resistance to asynchrony. In: Mauri, G., El Yacoubi, S., Dennunzio, A., Nishinari, K., Manzoni, L. (eds.) Cellular Automata, pp. 428–437. Springer International Publishing, Cham (2018)

    Google Scholar 

  16. Marsaglia, G.: DIEHARD: A battery of tests of randomness. http://stat.fsu.edu/geo/diehard.html (1996)

  17. Li, W., Packard, N.: The structure of the elementary cellular automata rule space. Complex Syst. 4, 281–297 (1990)

    MathSciNet  MATH  Google Scholar 

  18. Roy, S., Das, S.: Asynchronous cellular automata that hide some of the configurations during evolution. Int. J. Modern Phys. C 32(04), 2150054 (2021)

    Article  MathSciNet  Google Scholar 

  19. Fatès, N., Thierry, E., Morvan, M., Schabanel, N.: Fully asynchronous behavior of double-quiescent elementary cellular automata. Theoret. Comput. Sci. 362(1), 1–16 (2006)

    Article  MathSciNet  Google Scholar 

  20. Sarkar, A., Mukherjee, A., Das, S.: Reversibility in asynchronous cellular automata. Complex Syst. 21, 71–84 (2012)

    Google Scholar 

  21. Sethi, B., Fatès, N., Das, S.: Reversibility of elementary cellular automata under fully asynchronous update. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) Theory and Applications of Models of Computation, pp. 39–49. Springer International Publishing, Cham (2014)

    Chapter  Google Scholar 

  22. Fatès, N., Sethi, B., Das, S.: On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View, pp. 313–332. Springer International Publishing, Cham (2018)

    MATH  Google Scholar 

  23. Knuth, D.E.: The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd ed. Boston: Addison-Wesley (1997)

    Google Scholar 

  24. Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., Vo, S.: Statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST special publication. revision 1a. National Institute of Standards and Technology, Technology Administration, U.S. Department of Commerce, vol. 800-22 (2010)

    Google Scholar 

  25. L’Ecuyer, P., Simard, R.: TestU01: a c library for empirical testing of random number generators. ACM Trans. Math. Softw. 33(4), 22:1–22:40 (2007)

    Google Scholar 

  26. McGrath, R. et al.: GNU C Library. https://www.gnu.org/software/libc/manual/html_node/Pseudo_002dRandom-Numbers.html#index-pseudo_002drandom-numbers

  27. Bhattacharjee, K., Maity, K., Das, S.: A search for good pseudo-random number generators : survey and empirical studies. CoRR vol. abs/1811.04035, 2018. [Online]. http://arxiv.org/abs/1811.04035

Download references

Acknowledgements

The authors are grateful to Prof. Sukanta Das and Dr. Kamalika Bhattacharjee for enlightening discussions on this topic. The authors acknowledge the anonymous reviewers for their comments and suggestions, which have helped to improve the quality and readability of the paper.

Author information

Authors and Affiliations

  1. Department of Information Technology, Indian Institute of Engineering Science and Technology, Shibpur Howrah, 711103, West Bengal, India

    Souvik Roy & Sumit Adak

Authors
  1. Souvik Roy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sumit Adak
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Information Technology, Indian Institute of Engineering Science and Technology, Shibpur, Howrah, West Bengal, India

    Sukanta Das

  2. National Polytechnic Institute, Mexico City, Mexico

    Genaro J. Martinez

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Roy, S., Adak, S. (2022). Asynchronous Cellular Automata as Randomness Enhancer. In: Das, S., Martinez, G.J. (eds) Proceedings of First Asian Symposium on Cellular Automata Technology. ASCAT 2022. Advances in Intelligent Systems and Computing, vol 1425. Springer, Singapore. https://doi.org/10.1007/978-981-19-0542-1_11

Download citation

Publish with us

Policies and ethics

Search

Navigation