-The exploitation of chaotic systems to generate pseudorandom sequences is
-an hot topic~\cite{915396,915385,5376454}. Such systems are fundamentally
-chosen due to their unpredictable character and their sensitiveness to initial conditions.
-In most cases, these generators simply consist in iterating a chaotic function like
-the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots
-It thus remains to find optimal parameters in such functions so that attractors are
-avoided, hoping by doing so that the generated numbers follow a uniform distribution.
-In order to check the quality of the produced outputs, it is usual to test the
-PRNGs (Pseudo-Random Number Generators) with statistical batteries like
-the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07} ones.
+The exploitation of chaotic systems to generate pseudorandom sequences
+is a hot topic~\cite{915396,915385,5376454}. Such systems are
+fundamentally chosen due to their unpredictable character and their
+sensitiveness to initial conditions. In most cases, these generators
+simply consist in iterating a chaotic function like the logistic
+map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots It
+thus remains to find optimal parameters in such functions so that
+attractors are avoided, hoping by doing so that the generated numbers
+follow a uniform distribution. In order to check the quality of the
+produced outputs, it is usual to test the PRNGs (Pseudo-Random Number
+Generators) with statistical batteries like the so-called
+DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or
+TestU01~\cite{LEcuyerS07} ones.
-In its general understanding, chaos notion is often reduced to the strong
-sensitiveness to the initial conditions (the well known ``butterfly effect''):
-a continuous function $k$ defined on a metrical space is said
-\emph{strongly sensitive to the initial conditions} if for each point
-$x$ and each positive value $\epsilon$, it is possible to find another
-point $y$ as close as possible to $x$, and an integer $t$ such that the distance
-between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$,
-are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney}
-imposes to the chaotic function two other properties called
-\emph{transitivity} and \emph{regularity}. Functions evoked above have
-been studied according to these properties, and they have been proven as chaotic on $\R$.
-But nothing guarantees that such properties are preserved when iterating the functions
-on floating point numbers, which is the domain of interpretation of real numbers $\R$ on
-machines.
+In its general understanding, chaos notion is often reduced to the
+strong sensitiveness to the initial conditions (the well known
+``butterfly effect''): a continuous function $k$ defined on a metrical
+space is said \emph{strongly sensitive to the initial conditions} if
+for each point $x$ and each positive value $\epsilon$, it is possible
+to find another point $y$ as close as possible to $x$, and an integer
+$t$ such that the distance between the $t$-th iterates of $x$ and $y$,
+denoted by $k^t(x)$ and $k^t(y)$, are larger than $\epsilon$. However,
+in his definition of chaos, Devaney~\cite{Devaney} imposes to the
+chaotic function two other properties called \emph{transitivity} and
+\emph{regularity}. Functions evoked above have been studied according
+to these properties, and they have been proven as chaotic on $\R$.
+But nothing guarantees that such properties are preserved when
+iterating the functions on floating point numbers, which is the domain
+of interpretation of real numbers $\R$ on machines.
-To avoid this lack of chaos, we have previously presented some PRNGs that iterate
-continuous functions $G_f$ on a discrete domain $\{ 1, \ldots, n \}^{\Nats}
- \times \{0,1\}^n$, where $f$ is a Boolean function (\textit{i.e.}, $f :
- \{0,1\}^n \rightarrow \{0,1\}^n$). These generators are
-$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
-$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} and
-$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} where \textit{CI} means
-\emph{Chaotic Iterations}.
-We have firstly proven in~\cite{bcgr11:ip} that, to establish the chaotic nature
-of algorithm $\textit{CIPRNG}_f^1$, it is necessary and sufficient that the
-asynchronous iterations are strongly connected. We then have proven that it is necessary
-and sufficient that the Markov matrix associated to this graph is doubly stochastic,
-in order to have a uniform distribution of the outputs. We have finally established
-sufficient conditions to guarantee the first property of connectivity. Among the
-generated functions, we thus have considered for further investigations only the ones that
-satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic
-method allowing to directly obtain a strongly connected iteration graph having a doubly
-stochastic Markov matrix.
+To avoid this lack of chaos, we have previously presented some PRNGs
+that iterate continuous functions $G_f$ on a discrete domain $\{ 1,
+\ldots, n \}^{\Nats} \times \{0,1\}^n$, where $f$ is a Boolean
+function (\textit{i.e.}, $f : \{0,1\}^{\mathsf{N}}
+\rightarrow \{0,1\}^{\mathsf{N}}$).
+These generators are $\textit{CIPRNG}_f^1(u)$
+\cite{guyeuxTaiwan10,bcgr11:ip}, $\textit{CIPRNG}_f^2(u,v)$
+\cite{wbg10ip} and $\chi_{\textit{14Secrypt}}$
+\cite{DBLP:conf/secrypt/CouchotHGWB14} where \textit{CI} means
+\emph{Chaotic Iterations}. We have firstly proven in~\cite{bcgr11:ip}
+that, to establish the chaotic nature of algorithm
+$\textit{CIPRNG}_f^1$, it is necessary and sufficient that the
+asynchronous iterations are strongly connected. We then have proven
+that it is necessary and sufficient that the Markov matrix associated
+to this graph is doubly stochastic, in order to have a uniform
+distribution of the outputs. We have finally established sufficient
+conditions to guarantee the first property of connectivity. Among the
+generated functions, we thus have considered for further
+investigations only the ones that satisfy the second property
+too.
+However, it cannot be directly deduced that
+$\chi_{\textit{14Secrypt}}$ is chaotic since we do not output all the
+successive values of iterating $G_f$. This algorithm only displays a
+subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and it is
+indeed not correct that the chaos property is preserved for any
+subsequence of a chaotic sequence. This article presents conditions
+to preserve this property.
-However, it cannot be directly deduced
-that $\chi_{\textit{14Secrypt}}$ is chaotic
-since we do not output all the successive
-values of iterating $F_f$.
-This algorithm only displays a
-subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and
-it is indeed definitively false that the chaos property is
-preserved for any subsequence of a chaotic sequence.
-This article presents conditions to preserve this property.
-An approach to generate a large class of chaotic functions has
-been presented in~\cite{chgw14oip}.
-It is basically fourfold:
-first build a $\mathsf{N}$-cube, next remove an Hamiltonian cycle, further add self-loop
-on each vertex and finally, translate this into a Boolean map.
-We are then left to check whether this approach proposes maps with the required conditions
-for the chaos.
-The answer is indeed positive. The pseudorandom number generation can thus be seen as a
-random walk in a $\mathsf{N}$-cube without a Hamiltonian cycle.
+Finding a Boolean function which provides a strongly connected
+iteration graph having a doubly stochastic Markov matrix is however
+not an easy task.
+We have firstly proposed in~\cite{bcgr11:ip} a generate-and-test based
+approach that solves this issue. However, this one was not efficient enough.
+Thus, a second scheme has been further presented
+in~\cite{DBLP:conf/secrypt/CouchotHGWB14} by remarking that
+a $\mathsf{N}$-cube where an Hamiltonian cycle (or equivalently a Gray code)
+has been removed is strongly connected and has
+a doubly stochastic Markov matrix.
-In the PRNG context, there remains to find which subsequence
-is theoretically and practically
-sufficient to extract.
-A uniform distribution is indeed awaited and this
-cannot be obtained in a walk in the hypercube
-with paths of short length $b$.
-However, the higher
-is $b$ the slower is the
-algorithm to generate pseudorandom
-numbers.
-The time until the
-corresponding Markov chain is close
-to the uniform distribution is a metric
-that should be theoretically and practically studied.
-Finally, the ability of the approach to face classical
-tests suite has to be evaluated.
+However, the removed Hamiltonian cycle
+has a great influence in the quality of the output.
+For instance, if this one one is not balanced (\textit{i.e.},
+the number of changes in different bits are completely different),
+some bits would be hard to switch.
+This article shows an effective algorithm that efficiently
+implements the previous scheme and provides thus functions issued
+from removing in the $\mathsf{N}$-cube a \emph{balanced} Hamiltonian cycle.
+The length $b$ of the walk to reach a
+distribution close to the uniform one would be dramatically long.
+This article theoretically and practically
+studies the length $b$ until the corresponding Markov
+chain is close to the uniform distribution.
+Finally, the ability of the approach to face classical tests
+suite is evaluated.
-%A upper bound of this time quadratic in the number of
-%generated bits.
-The remainder of this article is organized as follows. The next section is devoted to
-preliminaries, basic notations, and terminologies regarding Boolean map iterations.
-Then, in Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is recalled
-while the proofs of chaos of our most general PRNGs is provided.
-This is the first major contribution.
-Section~\ref{sec:SCCfunc} shows how to generate functions with required properties
-making the PRNG chaotic.
-The next section (Sect.~\ref{sec:hypercube}) defines the theoretical framework
-to study the stopping-time, \textit{i.e.}, time until reaching
-a uniform distribution.
-This is the second major contribution.
-The Section~\ref{sec:prng} gives practical results on evaluating the PRNG against the NIST suite.
-This research work ends by a conclusion section, where the contribution is summarized and
-intended future work is outlined.
+This article, which
+is an extension of~\cite{DBLP:conf/secrypt/CouchotHGWB14}
+is organized as follows. The next
+section is devoted to preliminaries, basic notations, and
+terminologies regarding Boolean map iterations. Then, in
+Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is
+recalled while the proofs of chaos of our most general PRNGs is
+provided. This is the first major contribution.
+Section~\ref{sec:SCCfunc} recalls a general scheme
+to obtain functions with awaited behavior. Main theorems are recalled
+to make the document self-content.
+The next section (Sect.~\ref{sec:hamilton}) presents an algorithm that
+implements this scheme and proves it always produces a solution.
+This is the second major contribution
+The later section
+(Sect.~\ref{sec:hypercube}) defines the theoretical framework to study
+the mixing-time, \textit{i.e.}, time until reaching a uniform
+distribution. It proves that this one is at worth quadratic in the number
+of elements. Experiments show that the bound is practically largely much
+lower. This is the third major contribution. The
+Section~\ref{sec:prng} gives practical results on evaluating the PRNG
+against the NIST suite. This research work ends by a conclusion
+section, where the contribution is summarized and intended future work
+is outlined.
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End:
