Paper Info
Title
Cellular Automata Pseudo-Random Number Generators and Their Resistance to Asynchrony.
Abstract
Cellular Automata (CA) have a long history being employed as pseudo-random number generators (PRNG), especially for cryptographic applications such as keystream generation in stream ciphers. Initially starting from the study of rule 30 of elementary CA, multiple rules where the objects of investigation and were shown to be able to pass most of the rigorous statistical tests used to assess the quality of PRNG. In all cases, the CA employed where of the classical, synchronous kind. This assumes a global clock regulating all CA updates which can be a weakness if an attacker is able to tamper it. Here we study how much asynchrony is necessary to make a CA-based PRNG ineffective. We have found that elementary CA are subdivided into three class: (1) there is a “state transition” where, after a certain level of asynchrony, the CA loses the ability to generate strong random sequences, (2) the randomness of the sequences increases with a limited level of asynchrony, or (3) CA normally unable to be used as PRNG exhibit a much stronger ability to generate random sequences when asynchrony is introduced.
Year
Venue
Field
2018
ACRI
Keystream,Cellular automaton,Cryptography,Computer science,Theoretical computer science,Stream cipher,Rule 30,Statistical hypothesis testing,Randomness,Pseudorandom number generator
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
13
2
Name
Order
Citations
PageRank
Luca Manzoni148855.19
Luca Mariot24711.35