Keywords: discrete dynamical system, chaos theory, ergodicity, information security..

Asynchronous delay iterations from discrete mathematics have long been used to accelerate convergence in high-performance computing. They have the particularity of being defined on an infinite (discrete) set that can be seen as a Cartesian product: at each iteration, a vector of fixed-size bits is updated from a function whose return also depends on a parameter, itself obtained from the first term of a sequence that is iterated at each iteration. The resulting product space is infinite but only handles bounded integers. In addition, only the bit vector must be stored in the finite state machine, a new term of the infinite sequence can be read at each iteration. In doing so, we obtain a discrete dynamic system that can be implemented as is on our computers, but which, from the moment they receive new data at each clock stroke, iterates over an infinite set. Any algorithm performing the function mentioned above, and iterating in order to update the memory, can thus be studied for its chaotic properties, and when such properties are proven for the dynamical system, the associated computer program is still chaotic in the most rigorous acceptation of this term, while implemented in finite state machines.

Many advances in the theoretical study of the randomness of such asynchronous iterations have been achieved in the past decade, and these results have been successfully applied in various areas of IT security. The objective of this article is to review these various advances in the study of the disorder of asynchronous iterations, both theoretically and practically, and to present new avenues of research and the latest results on ergodicity cases. In detail, we will present the link between asynchronous iterations and a certain category of connected graphs, and we will deduce a characterization of the chaos of such iterations, asmathematically defined by Devaney, Knudsen, in the sense of topological and metric entropies, and for Lyapounov’s exponent. New results from measurement theory, including the ergodicity of these iterations, will then be introduced, and we will then provide an overview of the applications of these results in computer security, focusing in particular on cryptographically secure pseudorandom generation and symmetric encryption.

purchase the full-text of this paper (price £22)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £25 +P&P)