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