1 The exploitation of chaotic systems to generate pseudorandom sequences
2 is a hot topic~\cite{915396,915385,5376454}. Such systems are
3 fundamentally chosen due to their unpredictable character and their
4 sensitiveness to initial conditions. In most cases, these generators
5 simply consist in iterating a chaotic function like the logistic
6 map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots It
7 thus remains to find optimal parameters in such functions so that
8 attractors are avoided, hoping by doing so that the generated numbers
9 follow a uniform distribution. In order to check the quality of the
10 produced outputs, it is usual to test the PRNGs (Pseudo-Random Number
11 Generators) with statistical batteries like the so-called
12 DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or
13 TestU01~\cite{LEcuyerS07} ones.
15 In its general understanding, chaos notion is often reduced to the
16 strong sensitiveness to the initial conditions (the well known
17 ``butterfly effect''): a continuous function $k$ defined on a metrical
18 space is said \emph{strongly sensitive to the initial conditions} if
19 for each point $x$ and each positive value $\epsilon$, it is possible
20 to find another point $y$ as close as possible to $x$, and an integer
21 $t$ such that the distance between the $t$-th iterates of $x$ and $y$,
22 denoted by $k^t(x)$ and $k^t(y)$, are larger than $\epsilon$. However,
23 in his definition of chaos, Devaney~\cite{Devaney} imposes to the
24 chaotic function two other properties called \emph{transitivity} and
25 \emph{regularity}. Functions evoked above have been studied according
26 to these properties, and they have been proven as chaotic on $\R$.
27 But nothing guarantees that such properties are preserved when
28 iterating the functions on floating point numbers, which is the domain
29 of interpretation of real numbers $\R$ on machines.
31 To avoid this lack of chaos, we have previously presented some PRNGs
32 that iterate continuous functions $G_f$ on a discrete domain $\{ 1,
33 \ldots, n \}^{\Nats} \times \{0,1\}^n$, where $f$ is a Boolean
34 function (\textit{i.e.}, $f : \{0,1\}^{\mathsf{N}}
35 \rightarrow \{0,1\}^{\mathsf{N}}$).
36 These generators are $\textit{CIPRNG}_f^1(u)$
37 \cite{guyeuxTaiwan10,bcgr11:ip}, $\textit{CIPRNG}_f^2(u,v)$
38 \cite{wbg10ip}, and $\chi_{\textit{14Secrypt}}$
39 \cite{DBLP:conf/secrypt/CouchotHGWB14} where \textit{CI} means
40 \emph{Chaotic Iterations}. We have firstly proven in~\cite{bcgr11:ip}
41 that, to establish the chaotic nature of algorithm
42 $\textit{CIPRNG}_f^1$, it is necessary and sufficient that the
43 asynchronous iterations are strongly connected. We then have proven
44 that it is necessary and sufficient that the Markov matrix associated
45 to this graph is doubly stochastic, in order to have a uniform
46 distribution of the outputs. We have finally established sufficient
47 conditions to guarantee the first property of connectivity. Among the
48 generated functions, we thus have considered for further
49 investigations only the ones that satisfy the second property
52 However, it cannot be directly deduced that
53 $\chi_{\textit{14Secrypt}}$ is chaotic since we do not output all the
54 successive values of iterating $G_f$. This algorithm only displays a
55 subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and it is
56 indeed not correct that the chaos property is preserved for any
57 subsequence of a chaotic sequence. This article presents conditions
58 to preserve this property.
61 Finding a Boolean function which provides a strongly connected
62 iteration graph having a doubly stochastic Markov matrix is however
64 We have firstly proposed in~\cite{bcgr11:ip} a generate-and-test based
65 approach that solves this issue. However, this one was not efficient enough.
66 Thus, a second scheme has been further presented
67 in~\cite{DBLP:conf/secrypt/CouchotHGWB14} by remarking that
68 a $\mathsf{N}$-cube where an Hamiltonian cycle (or equivalently a Gray code)
69 has been removed is strongly connected and has
70 a doubly stochastic Markov matrix.
72 However, the removed Hamiltonian cycle
73 has a great influence in the quality of the output.
74 For instance, if this one is not balanced (\textit{i.e.},
75 the number of changes in different bits are completely different),
76 some bits would be hard to switch.
77 This article shows an effective algorithm that efficiently
78 implements the previous scheme and provides thus functions issued
79 from removing, in the $\mathsf{N}$-cube, a \emph{balanced} Hamiltonian cycle.
81 The length $b$ of the walk to reach a
82 distribution close to the uniform one would be dramatically long.
83 This article theoretically and practically
84 studies the length $b$ until the corresponding Markov
85 chain is close to the uniform distribution.
86 Finally, the ability of the approach to face classical tests
92 is an extension of~\cite{DBLP:conf/secrypt/CouchotHGWB14},
93 is organized as follows. The next
94 section is devoted to preliminaries, basic notations, and
95 terminologies regarding Boolean map iterations. Then, in
96 Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is
97 recalled while the proofs of chaos of our most general PRNGs is
98 provided. This is the first major contribution.
99 Section~\ref{sec:SCCfunc} recalls a general scheme
100 to obtain functions with awaited behavior. Main theorems are recalled
101 to make the document self-content.
102 The next section (Sect.~\ref{sec:hamilton}) presents an algorithm that
103 implements this scheme and proves that it always produces a solution.
104 This is the second major contribution.
105 Then, Section~\ref{sec:hypercube} defines the theoretical framework to study
106 the mixing-time, \textit{i.e.}, time until reaching an uniform
107 distribution. It proves that this one is at worth quadratic in the number
108 of elements. Experiments show that the bound is in practice largely much
109 lower. This is the third major contribution.
110 Section~\ref{sec:prng} gives practical results on evaluating the PRNG
111 against the NIST suite. This research work ends by a conclusion
112 section, where the contribution is summarized and intended future work
117 %%% TeX-master: "main"
118 %%% ispell-dictionary: "american"
