1 The exploitation of chaotic systems to generate pseudorandom sequences is
2 an hot topic~\cite{915396,915385,5376454}. Such systems are fundamentally
3 chosen due to their unpredictable character and their sensitiveness to initial conditions.
4 In most cases, these generators simply consist in iterating a chaotic function like
5 the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots
6 It thus remains to find optimal parameters in such functions so that attractors are
7 avoided, hoping by doing so that the generated numbers follow a uniform distribution.
8 In order to check the quality of the produced outputs, it is usual to test the
9 PRNGs (Pseudo-Random Number Generators) with statistical batteries like
10 the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07} ones.
12 In its general understanding, chaos notion is often reduced to the strong
13 sensitiveness to the initial conditions (the well known ``butterfly effect''):
14 a continuous function $k$ defined on a metrical space is said
15 \emph{strongly sensitive to the initial conditions} if for each point
16 $x$ and each positive value $\epsilon$, it is possible to find another
17 point $y$ as close as possible to $x$, and an integer $t$ such that the distance
18 between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$,
19 are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney}
20 imposes to the chaotic function two other properties called
21 \emph{transitivity} and \emph{regularity}. Functions evoked above have
22 been studied according to these properties, and they have been proven as chaotic on $\R$.
23 But nothing guarantees that such properties are preserved when iterating the functions
24 on floating point numbers, which is the domain of interpretation of real numbers $\R$ on
27 To avoid this lack of chaos, we have previously presented some PRNGs that iterate
28 continuous functions $G_f$ on a discrete domain $\{ 1, \ldots, n \}^{\Nats}
29 \times \{0,1\}^n$, where $f$ is a Boolean function (\textit{i.e.}, $f :
30 \{0,1\}^n \rightarrow \{0,1\}^n$). These generators are
31 $\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
32 $\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} and
33 $\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} where \textit{CI} means
34 \emph{Chaotic Iterations}.
35 We have firstly proven in~\cite{bcgr11:ip} that, to establish the chaotic nature
36 of algorithm $\textit{CIPRNG}_f^1$, it is necessary and sufficient that the
37 asynchronous iterations are strongly connected. We then have proven that it is necessary
38 and sufficient that the Markov matrix associated to this graph is doubly stochastic,
39 in order to have a uniform distribution of the outputs. We have finally established
40 sufficient conditions to guarantee the first property of connectivity. Among the
41 generated functions, we thus have considered for further investigations only the ones that
42 satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic
43 method allowing to directly obtain a strongly connected iteration graph having a doubly
44 stochastic Markov matrix.
47 However, it cannot be directly deduced
48 that $\chi_{\textit{14Secrypt}}$ is chaotic
49 since we do not output all the successive
50 values of iterating $F_f$.
51 This algorithm only displays a
52 subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and
53 it is indeed definitively false that the chaos property is
54 preserved for any subsequence of a chaotic sequence.
55 This article presents conditions to preserve this property.
57 An approach to generate a large class of chaotic functions has
58 been presented in~\cite{chgw14oip}.
59 It is basically fourfold:
60 first build a $\mathsf{N}$-cube, next remove an Hamiltonian cycle, further add self-loop
61 on each vertex and finally, translate this into a Boolean map.
62 We are then left to check whether this approach proposes maps with the required conditions
64 The answer is indeed positive. The pseudorandom number generation can thus be seen as a
65 random walk in a $\mathsf{N}$-cube without a Hamiltonian cycle.
67 In the PRNG context, there remains to find which subsequence
68 is theoretically and practically
69 sufficient to extract.
70 A uniform distribution is indeed awaited and this
71 cannot be obtained in a walk in the hypercube
72 with paths of short length $b$.
74 is $b$ the slower is the
75 algorithm to generate pseudorandom
78 corresponding Markov chain is close
79 to the uniform distribution is a metric
80 that should be theoretically and practically studied.
81 Finally, the ability of the approach to face classical
82 tests suite has to be evaluated.
85 %A upper bound of this time quadratic in the number of
89 The remainder of this article is organized as follows. The next section is devoted to
90 preliminaries, basic notations, and terminologies regarding Boolean map iterations.
91 Then, in Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is recalled
92 while the proofs of chaos of our most general PRNGs is provided.
93 This is the first major contribution.
94 Section~\ref{sec:SCCfunc} shows how to generate functions with required properties
95 making the PRNG chaotic.
96 The next section (Sect.~\ref{sec:hypercube}) defines the theoretical framework
97 to study the stopping-time, \textit{i.e.}, time until reaching
98 a uniform distribution.
99 This is the second major contribution.
100 The Section~\ref{sec:prng} gives practical results on evaluating the PRNG against the NIST suite.
101 This research work ends by a conclusion section, where the contribution is summarized and
102 intended future work is outlined.
