@Article{CB01,
author = {S.~Contassot-Vivier and J.M.~Bahi},
- title = {Convergence dans les systèmes booléens asynchrones et application aux
- réseaux de Hopfield},
- journal = {Calculateurs Parallèles},
+ title = {Convergence dans les systèmes booléens asynchrones et application aux
+ réseaux de Hopfield},
+ journal = {Calculateurs Parallèles},
year = {2001},
OPTkey = {},
volume = {13},
@Article{Rob78,
author = {F.~Robert},
- title = {Th\'{e}or\`{e}me de Perron-Frobenius et Stein-Rosenberg booléens},
+ title = {Th\'{e}or\`{e}me de Perron-Frobenius et Stein-Rosenberg booléens},
journal = {Linear Algebra and Its Applications},
year = {1978},
OPTkey = {},
}
@Article{GFSP85,
- author = {E.~Golès and F.~Fogelman-Soulie and D.~Pellegrin},
+ author = {E.~Golès and F.~Fogelman-Soulie and D.~Pellegrin},
title = {Decreasing energy functions as a tool for studying threshold networks},
journal = {Disc. Appl. Math.},
year = {1985},
@PhdThesis{Pel86,
author = {D.~Pellegrin},
- title = {Algorithmique discrète et réseaux d'automates},
+ title = {Algorithmique discrète et réseaux d'automates},
school = {Grenoble},
year = {1986},
OPTkey = {},
domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
equipe = {and},
classement = {COM},
-author = {Couchot, Jean-Fran\c{c}ois and Héam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques},
+author = {Couchot, Jean-Fran\c{c}ois and Héam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques},
title = {Traversing a n-cube without Balanced Hamiltonian Cycle to Generate Pseudorandom Numbers},
-howpublished = {15-th Mons Theoretical Computer Science Days (15e Journées Montoises d'Informatique Théorique), Nancy, France},
+howpublished = {15-th Mons Theoretical Computer Science Days (15e Journées Montoises d'Informatique Théorique), Nancy, France},
day = 23,
month = sep,
year = 2014,
% Markov.bib
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-@inproceedings{chgw14oip,
- author = {Jean-François Couchot and
- Pierre-Cyrille Héam and
- Christophe Guyeux and
- Qianxue Wang and
- Jacques M. Bahi},
- title = {Pseudorandom Number Generators with Balanced Gray Codes.},
- booktitle = {SECRYPT},
- year = {2014},
- pages = {469-475},
- address = {Vienna, Austria},
- publisher = {Springer}
-}
@Article{rwfg,
month = jun,
year = 2011}
-@incollection{bcgr11ip,
-year={2011},
-isbn={978-3-642-22952-7},
-booktitle={Fundamentals of Computation Theory},
-volume={6914},
-series={Lecture Notes in Computer Science},
-editor={Owe, Olaf and Steffen, Martin and Telle, JanArne},
-doi={10.1007/978-3-642-22953-4_11},
-title={On the Link between Strongly Connected Iteration Graphs and Chaotic Boolean Discrete-Time Dynamical Systems},
-url={http://dx.doi.org/10.1007/978-3-642-22953-4_11},
-publisher={Springer Berlin Heidelberg},
-keywords={Boolean network; discrete-time dynamical system; topological chaos},
-author={Bahi, Jacques M. and Couchot, Jean-Francois and Guyeux, Christophe and Richard, Adrien},
-pages={126-137},
-language={English},
-address={Berlin}
-}
@INPROCEEDINGS{bg10aip,
author = {Bahi, Jacques and Guyeux, Christophe},
@ARTICLE{DBLPjournalsAbs-1112-5239,
author = {Jacques M. Bahi and Rapha{\"e}l Couturier and Christophe Guyeux and
- Pierre-Cyrille H{é}am},
+ Pierre-Cyrille H{é}am},
title = {Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom
Numbers on GPU},
journal = {CoRR},
title = {Discrete Iterations, a Metric Study},
publisher = {Springer-Verlag},
year = {1986},
- author = {François Robert},
+ author = {François Robert},
volume = {6},
series = {Series in Computational Mathematics}
}
-@INPROCEEDINGS{cghwb14ip,
- author = {Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Heam,
-Pierre-Cyrille, and Wang, Qianxue and Bahi, Jacques},
- title = {Pseudorandom Number Generators with Balanced Gray Codes},
- booktitle = {SECRYPT 2014, the 11th International Conference on Security and Cryptography},
- year = {2014},
- pages = {***--***},
- address = {Vienna, Austria},
- month = aug,
- classement = {ACTI},
- doi = {10.1007/978-3-642-22953-4_11},
- domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
- equipe = {and},
- inhal = {no},
-}
-
@Article{ZanSup04,
author = {Suparta, IN and Zanten, AJ van},
title = {Totally balanced and exponentially balanced Gray codes},
+Let us us first recall the chaos theoretical context presented
+in~\cite{bcgr11:ip}. In this article, the space of interest
+is $\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$
+and the iteration function $\mathcal{H}_f$ is
+the map from
+$\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$
+to itself defined by
+\[
+\mathcal{H}_f(x,s)=(F_f(x,s_0),\sigma(s)).
+\]
+In this definition,
+$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow
+ \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}
+$
+ is a shift operation on sequences (\textit{i.e.}, a function that removes the
+first element of the sequence) formally defined with
+$$
+\sigma((u^k)_{k \in \Nats}) = (u^{k+1})_{k \in \Nats}.
+$$
+We have proven~\cite[Theorem 1]{bcgr11:ip} that
+$\mathcal{H}_f$ is chaotic in
+$\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$
+if and only if $\Gamma(f)$ is strongly connected.
+However, the corrolary which would say that $\chi_{\textit{14Secrypt}}$ is chaotic
+cannot be directly deduced since we do not output all the successive
+values of iterating $F_f$. Only a a few of them is concerned and
+any subsequence of a chaotic sequence is not necessarily
+a chaotic sequence too.
+This necessitates a rigorous proof, which is the aim of this section.
-\subsection{Notations and terminologies}\label{sec:notations}
-Denote by $\mathds{B}$ the Boolean set, by $\mathds{N}^\ast$ the set
-of natural integers $\{1,2,3, \hdots \}$, and by $\mathds{N}=\mathds{N}^\ast \cup \{0\}$.
-For $a,b \in \mathds{N}, a \leqslant b$, $\llbracket a, b \rrbracket$ means the set
-$\{a, a+1, \hdots , b\}$ of integers belonging between $a$ and $b$.
-For any finite set $X$, $|X|$ denotes its cardinality.
-The $n-$th of a sequence $v$ of vectors is $v^n$ while its $i-$th component is $v_i^n$,
-so $v=\left(v^n\right)_{n \in \mathds{N}}$.
-Finally, $\overline{x}$ stands for the negation of the Boolean $x$, while $\lfloor y \rfloor$ is
-the largest integer lower than $y$.
-\subsubsection{Devaney's Chaotic Dynamical Systems}
+
+\subsection{Devaney's Chaotic Dynamical Systems}
\label{subsec:Devaney}
element of the definition of chaos).
-\subsubsection{Introducing the \textit{CIPRNG} categories of chaotic iterations based pseudorandom number generators}
+\subsection{A Metric Space for PRNG Iterations}
+
+% Define by $\mathcal{S}_X$ the set of sequences whose elements belong in $X \subset \mathds{N}, X \neq \varnothing$,
+% that is, $\mathcal{S}_X = \mathcal{X}^\mathds{N}$.
+% Let $\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$, and
+% $\mathcal{P} \subset \mathds{N}^\ast$ a non empty and finite set of integers.
+
+% Any couple $(u,v) \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$ defines
+% a ``chaotic iterations based'' pseudorandom number generator, which is denoted by $\textit{CIPRNG}_f^2(u,v)$~\cite{wbg10:ip}. It is
+% defined as follows:
+% \begin{equation}
+% \label{CIPRNGver2}
+% \left\{
+% \begin{array}{l}
+% x^0 \in \mathds{B}^\mathsf{N}\\
+% \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=u^n \\ x_i^n & \text{else} \end{array} \right.\\
+% \forall n \in \mathds{N}, y^n = x^{v^n} .
+% \end{array}
+% \right.
+% \end{equation}
+% The outputted sequence produced by this generator is $\left(y^n\right)_{n \in \mathds{N}}$.
+% Remark that, given a sequence $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ called a ``chaotic strategy'',
+% the following way to iterate:
+% $$x^0 \in \mathds{B}^\mathsf{N}, \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=S^n \\ x_i^n & \text{else} \end{array} \right. ,$$
+% is referred in the discrete mathematics literature as ``chaotic iterations''~\cite{Robert} (a terminology which has
+% \emph{a priori} no relation with the mathematical theory of chaos recalled previously), which
+% explains the name provided to these categories of pseudorandom number generators.
+
+
+% The formerly proposed $\textit{CIPRNG}_f^1(u)$~\cite{bgw09:ip,guyeuxTaiwan10} is equal to \linebreak $\textit{CIPRNG}_f^2\left(u,\left(1\right)_{n\in \mathds{N}}\right)$, where $\left(1\right)_{n\in \mathds{N}}$ is the sequence that is
+% uniformly equal to 1.
+% It has been proven as chaotic for the vectorial Boolean negation $f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$,
+% $(x_1, \hdots , x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, \overline{x_\mathsf{N}})$ in \cite{bgw09:ip}
+% and for a larger set of well-chosen iteration functions in~\cite{bcgr11:ip} but,
+% as only one bit is modified at each iteration, this generator is not able to pass any reasonable statistical tests.
+
+% The $\textit{XOR~CIPRNG}(S)$, for its part~\cite{DBLP:journals/corr/abs-1112-5239}, is defined as follows: $x^0 \in \mathds{B}^\mathsf{N}$, and $\forall n \in \mathds{N}, x^{n+1} = x^n \oplus S^n$
+% where $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ and $\oplus$ stands for the bitwise \emph{exclusive or} (xor) operation
+% between the binary decomposition of $x^n$ and $S^n$. This is indeed a $CIPRNG_{f_0}^2 (u,v)$ generator:
+% %, for
+% %$u,v \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$:
+% for any given $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, $v^n$ is the number
+% of 1's in the binary decomposition of $S^n$ while $u^{v^n}, u^{v^n+1}, \hdots , u^{v^{n+1}-1}$
+% are the positions of these ones.
+% The $\textit{XOR~CIPRNG}$ has been proven chaotic and it is able to pass all the most stringent statistical
+% batteries of tests~\cite{DBLP:journals/corr/abs-1112-5239}, namely: DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, and TestU01~\cite{LEcuyerS07},
+% which encompasses the two former ones. Furthermore, the output sequence is cryptographically secure
+% when $S$ is cryptographically secure~\cite{DBLP:journals/corr/abs-1112-5239}.
+% We are then left to prove $\textit{CIPRNG}_f^2(u,v)$ is chaotic.
+
+% \subsection{The $\textit{CIPRNG}_f^2(u,v)$ is chaotic for well-chosen $f$}\label{sec:wellchosen}
+
+% \subsection{The generator as a discrete dynamical system}
+
+
+% This algorithm may be seen as $\mathsf{p}$ functional composition of $F_f$.
+% We thus introduce the function
+% $F_{f,\mathsf{p}} : \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^\mathsf{p} \rightarrow \mathds{B}^\mathsf{N}$ defined by
+
+% $$
+% F_{f,\mathsf{p}} (x,(u^0, u^1, \hdots, u^{\mathsf{p}-1})) \mapsto
+% F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{\mathsf{p}-1}).
+% $$
+
+
+
+
+Let us first introduce $\mathcal{P} \subset \mathds{N}$ a finite nonempty
+set having the cardinality $\mathsf{p} \in \mathds{N}^\ast$.
+Intuitively, this is the set of authorized numbers of iterations.
+Denote by $p_1, p_2, \hdots, p_\mathsf{p}$ the ordered elements of $\mathcal{P}$: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$
+and $p_1< p_2< \hdots < p_\mathsf{p}$. In our algorithm,
+$\mathsf{p}$ is 1 and $p_1$ is $b$.
-Define by $\mathcal{S}_X$ the set of sequences whose elements belong in $X \subset \mathds{N}, X \neq \varnothing$,
-that is, $\mathcal{S}_X = \mathcal{X}^\mathds{N}$.
-Let $\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$, and
-$\mathcal{P} \subset \mathds{N}^\ast$ a non empty and finite set of integers.
-Any couple $(u,v) \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$ defines
-a ``chaotic iterations based'' pseudorandom number generator, which is denoted by $\textit{CIPRNG}_f^2(u,v)$~\cite{wbg10:ip}. It is
-defined as follows:
-\begin{equation}
-\label{CIPRNGver2}
-\left\{
-\begin{array}{l}
- x^0 \in \mathds{B}^\mathsf{N}\\
- \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=u^n \\ x_i^n & \text{else} \end{array} \right.\\
- \forall n \in \mathds{N}, y^n = x^{v^n} .
-\end{array}
-\right.
-\end{equation}
-The outputted sequence produced by this generator is $\left(y^n\right)_{n \in \mathds{N}}$.
-Remark that, given a sequence $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ called a ``chaotic strategy'',
-the following way to iterate:
-$$x^0 \in \mathds{B}^\mathsf{N}, \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=S^n \\ x_i^n & \text{else} \end{array} \right. ,$$
-is referred in the discrete mathematics literature as ``chaotic iterations''~\cite{Robert} (a terminology which has
-\emph{a priori} no relation with the mathematical theory of chaos recalled previously), which
-explains the name provided to these categories of pseudorandom number generators.
-
-
-The formerly proposed $\textit{CIPRNG}_f^1(u)$~\cite{bgw09:ip,guyeuxTaiwan10} is equal to \linebreak $\textit{CIPRNG}_f^2\left(u,\left(1\right)_{n\in \mathds{N}}\right)$, where $\left(1\right)_{n\in \mathds{N}}$ is the sequence that is
-uniformly equal to 1.
-It has been proven as chaotic for the vectorial Boolean negation $f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$,
-$(x_1, \hdots , x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, \overline{x_\mathsf{N}})$ in \cite{bgw09:ip}
-and for a larger set of well-chosen iteration functions in~\cite{bcgr11:ip} but,
-as only one bit is modified at each iteration, this generator is not able to pass any reasonable statistical tests.
-
-The $\textit{XOR~CIPRNG}(S)$, for its part~\cite{DBLP:journals/corr/abs-1112-5239}, is defined as follows: $x^0 \in \mathds{B}^\mathsf{N}$, and $\forall n \in \mathds{N}, x^{n+1} = x^n \oplus S^n$
-where $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ and $\oplus$ stands for the bitwise \emph{exclusive or} (xor) operation
-between the binary decomposition of $x^n$ and $S^n$. This is indeed a $CIPRNG_{f_0}^2 (u,v)$ generator:
-%, for
-%$u,v \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$:
-for any given $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, $v^n$ is the number
-of 1's in the binary decomposition of $S^n$ while $u^{v^n}, u^{v^n+1}, \hdots , u^{v^{n+1}-1}$
-are the positions of these ones.
-The $\textit{XOR~CIPRNG}$ has been proven chaotic and it is able to pass all the most stringent statistical
-batteries of tests~\cite{DBLP:journals/corr/abs-1112-5239}, namely: DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, and TestU01~\cite{LEcuyerS07},
-which encompasses the two former ones. Furthermore, the output sequence is cryptographically secure
-when $S$ is cryptographically secure~\cite{DBLP:journals/corr/abs-1112-5239}.
-We are then left to prove $\textit{CIPRNG}_f^2(u,v)$ is chaotic.
-
-\subsection{The $\textit{CIPRNG}_f^2(u,v)$ is chaotic for well-chosen $f$}\label{sec:wellchosen}
-
-\subsubsection{The generator as a discrete dynamical system}
-
-
-Using notations of the previous section, consider a $\textit{CIPRNG}_f^2(u,v)$ generator $G$, with
-$\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$,
-$u \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, and $v \in \mathcal{S}_\mathcal{P}$, with
-$\mathcal{P} \subset \mathds{N}$ a finite nonempty set having the cardinality
-$\mathsf{p} \in \mathds{N}^\ast$.
-Denote by $p_1, p_2, \hdots, p_\mathsf{p}$ the ordered elements of $\mathcal{P}$: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$
-and $p_1< p_2< \hdots < p_\mathsf{p}$.
-Let
-$$
-\begin{array}{cccc}
- F_f: & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket & \longrightarrow & \mathds{B}^\mathsf{N}\\
- & (e,i) & \longmapsto & (e_1, \hdots , e_{i-1}, f(e)_i, e_{i+1}, \hdots , e_{\mathsf{N}})
-\end{array}
-$$
-and
+The Algorithm~\ref{CI Algorithm}
+may be seen as $b$ functional composition of $F_f$.
+However, it can be generalized with $p_i$, $p_i \in \mathcal{P}$,
+functional compositions of $F_f$.
+Thus, for any $p_i \in \mathcal{P}$ we introduce the function
+$F_{f,p_i} : \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^{p_i} \rightarrow \mathds{B}^\mathsf{N}$ defined by
+
$$
-\begin{array}{cccc}
- F_{f,\mathsf{p}} : & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^\mathsf{p} & \longrightarrow & \mathds{B}^\mathsf{N}\\
- & (e,(u^0, u^1, \hdots, u^{\mathsf{p}-1})) & \longmapsto & F_f(\hdots (F_f(F_f(e,u^0), u^1), \hdots), u^{\mathsf{p}-1}) .
-\end{array}
+F_{f,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1})) \mapsto
+F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{p_i-1}).
$$
-Denote by $\mathcal{X}_{\mathsf{N},\mathcal{P}}= \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, where
-$\mathds{S}_{\mathsf{N},\mathcal{P}}=\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}\times \mathcal{S}_\mathcal{P}$,
-we define the shift operation on sequences as follows,
-$$\begin{array}{cccc}
-\sigma:&\mathcal{S}_{X} &\longrightarrow
-& \mathcal{S}_{X} \\
-& (u^k)_{k \in \mathds{N}} & \longmapsto & (u^{k+1})_{k \in \mathds{N}},
-\end{array}
-$$
-and let
+
+The considered space is
+ $\mathcal{X}_{\mathsf{N},\mathcal{P}}= \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, where
+$\mathds{S}_{\mathsf{N},\mathcal{P}}=
+\llbracket 1, \mathsf{N} \rrbracket^{\Nats}\times
+\mathcal{P}^{\Nats}$.
+Each element in this space is a pair where the first element is
+$\mathsf{N}$-uple in $\Bool^{\mathsf{N}}$, as in the previous space.
+The second element is a pair $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ of infinite sequences.
+The sequence $(v^k)_{k \in \Nats}$ defines how many iterations are executed at time $k$ between two outputs.
+The sequence $(u^k)_{k \in \Nats}$ defines which elements is modified.
+
+Let us define the shift function $\Sigma$ for any element of $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
$$\begin{array}{cccc}
\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
&\mathds{S}_{\mathsf{N},\mathcal{P}} \\
-\subsubsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+\subsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows.
Consider
$p+n\times \max{(\mathcal{P})}$ digits.
\item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$ blocs of $n$
digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
-$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by O's if required.
+$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by 0's if required.
\item The case $v^0>\check{v}^0$ is dealt similarly.
\end{itemize}
\item The next $p$ digits are $|v^1-\check{v}^1|$, etc.
u=\underline{6,} ~ \underline{11,5}, ...\\
v=1,2,...
\end{array}
-\right.$\\
+\right.$
while
$\check{s}=\left\{
\begin{array}{l}
\check{u}=\underline{6,4} ~ \underline{1}, ...\\
\check{v}=2,1,...
\end{array}
-\right.$
+\right.$.
So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$,
u=\underline{6,7,} ~ \underline{4,2,} ...\\
v=2,2,...
\end{array}
-\right.$\\
+\right.$
while
$\check{s}=\left\{
\begin{array}{l}
Let us show that,
\begin{proposition}
-$d$ is a distance on $\mathcal{X}$.
+$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
\end{proposition}
\end{itemize}
\end{proof}
-\begin{figure}[h]
-\centering
-\includegraphics[scale=0.85]{graphe1.pdf}
-\caption{Chaotic iterations of $f_0$, defining the $CIPRNG_{f_0}^1$ ($\mathsf{N}=2$)}
-\label{graphe1}
-\end{figure}
-\subsubsection{The $\textit{CIPRNG}_f^2(u,v)$ as iterations on a graph}
-We define the directed graph $\mathcal{G}_{f,\mathcal{P}}$ as follows.
+\subsection{$\Gamma_{\mathcal{P}}(f)$ as an extension of $\Gamma(f)$}
+
+Let $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$.
+We define the directed graph $\Gamma_{\mathcal{P}}(f)$ as follows.
\begin{itemize}
\item Its vertices are the $2^\mathsf{N}$ elements of $\mathds{B}^\mathsf{N}$.
\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples
-having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
-\item There is an arc labeled $a_1, \hdots, a_{p_i}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if $y=F_{f,p_i} (x, (a_1, \hdots, a_{p_i})) $.
+ having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
+\item There is an arc labeled $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if
+$y=F_{f,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.
\end{itemize}
-
-\begin{figure}[h]
-\centering
-\includegraphics[scale=0.85]{graphe2.pdf}
-\caption{Iteration graph of $CIPRNG_{f_0}^2$, $\mathcal{P}=\{2,3\}$, $\mathsf{N}=2$}
-\label{graphe2}
+It is not hard to see that the graph $\Gamma_{\{1\}}(f)$ is
+$\Gamma(f)$.
+
+\begin{figure}[ht]
+ \centering
+ \begin{subfigure}[b]{0.45\textwidth}
+ \centering
+ \includegraphics[scale=0.85]{graphe1.pdf}
+ \caption{$\Gamma(f_0)$}
+ \label{graphe1}
+ \end{subfigure}%
+ ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
+ % (or a blank line to force the subfigure onto a new line)
+ \begin{subfigure}[b]{0.3\textwidth}
+ \centering
+ \includegraphics[scale=0.85]{graphe2.pdf}
+ \caption{$\Gamma_{\{2,3\}}(f_0)$}
+ \label{graphe2}
+ \end{subfigure}
+ ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
+ \caption{Iterating $f_0:(x_1,x_2) \mapsto (\overline{x_1}, \overline{x_2})$}
+ \label{fig:itg}
\end{figure}
+
\begin{xpl}
-Consider for instance $\mathsf{N}=2$, $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2, (x_1,x_2) \longmapsto (\overline{x_1}, \overline{x_2})$, and
-$\mathcal{P}=\{2,3\}$. Chaotic iterations of $f_0$ are given in Figure~\ref{graphe1} while the digraph $\mathcal{G}_{f_0,\{2,3\}}$ is depicted in
-Figure~\ref{graphe2}. Notice that here, orientations of arcs are not necessary
-since the function $f$ is equal to its inverse $f^{-1}$.
+Consider for instance $\mathsf{N}=2$,
+Let $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2$ be the negation function,
+\textit{i.e.}, $f_0(x_1,x_2) = (\overline{x_1}, \overline{x_2})$, and consider
+$\mathcal{P}=\{2,3\}$. The graphs of iterations are given in
+\textsc{Figure~\ref{fig:itg}}.
+The \textsc{Figure~\ref{graphe1}} shows what happens when
+displaying each iteration result.
+On the contrary, the \textsc{Figure~\ref{graphe2}} explicits the behaviors
+when always applying 2 or 3 modification and next outputing results.
+Notice that here, orientations of arcs are not necessary
+since the function $f_0$ is equal to its inverse $f_0^{-1}$.
\end{xpl}
-\subsubsection{Proofs of chaos}
+\subsection{Proofs of chaos}
We will show that,
\begin{proposition}
\label{prop:trans}
- $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected if and only if $G_f$ is
+ $\Gamma_{\mathcal{P}}(f)$ is strongly connected if and only if $G_f$ is
topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
\end{proposition}
\begin{proof}
-Suppose that $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected.
+Suppose that $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v}))
\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$.
We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and
In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
(v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$.
-Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\mathcal{G}_{f,\mathcal{P}}$
+Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\Gamma_{\mathcal{P}}(f)$
being strongly connected, there is a path between $e'$ and $\check{e}$. Denote
by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by
$V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$),
and $G_{f}^{k_1+k_2}(y)=\check{x}$.
-Conversely, if $\mathcal{G}_{f,\mathcal{P}}$ is not strongly connected, then there are
+Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are
2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
We show now that,
\begin{proposition}
-If $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected, then $G_f$ is
+If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is
regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
\end{proposition}
$$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
$$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
\subset \mathcal{B}(x,\varepsilon),$$
-and $y=G_f^{k_1}(e,(u,v))$. $\mathcal{G}_{f,\mathcal{P}}$ being strongly connected,
+and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected,
there is at least a path from the Boolean state $y_1$ of $y$ and $e$.
Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
Then the point:
$G_f$ being topologically transitive and regular, we can thus conclude that
\begin{Theo}
-The pseudorandom number generator $\textit{CIPRNG}_f^2$ denoted by $G_f$ in
-this section is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
-and only if its graph $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected.
+The function $G_f$ is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
+and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
\end{Theo}
+
+\begin{Corollary}
+ The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
+ on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.
+\end{Corollary}
+\begin{proof}
+ In this context, $\mathcal{P}$ is the singleton $\{b\}$.
+ If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach
+ its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
+ If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach itself
+ and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
+\end{proof}
-L'exploitation de \og systèmes chaotiques\fg{} pour générer des séquences
-pseudo-aléatoires est un sujet actif de recherche~\cite{915396,915385,5376454}.
-Ces systèmes sont choisis principalement
-en raison de leur imprévisibilité et de leur sensibilité aux conditions initiales.
+L'exploitation de \og systèmes chaotiques\fg{} pour générer des séquences
+pseudo-aléatoires est un sujet actif de recherche~\cite{915396,915385,5376454}.
+Ces systèmes sont choisis principalement
+en raison de leur imprévisibilité et de leur sensibilité aux conditions initiales.
-Souvent les travaux se limitent à itérer une fonction paramétrée
+Souvent les travaux se limitent à itérer une fonction paramétrée
\emph{chaotique} comme la fonction logistique~\cite{915396,915385}, ou encore
-celle du chat d'Arnold~\cite{5376454}\ldots Il reste à trouver les paramètres
-optimaux permettant d'éviter les attracteurs de telles fonctions et garantissant
-que les séquences de nombres produits suivent une loi de distribution uniforme.
-Pour vérifier la qualité des sorties produites il est usuel de soumettre les
-PRNG (Pseudo-Random Number Generator) à des tests statistiques tels
+celle du chat d'Arnold~\cite{5376454}\ldots Il reste à trouver les paramètres
+optimaux permettant d'éviter les attracteurs de telles fonctions et garantissant
+que les séquences de nombres produits suivent une loi de distribution uniforme.
+Pour vérifier la qualité des sorties produites il est usuel de soumettre les
+PRNG (Pseudo-Random Number Generator) à des tests statistiques tels
DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10} et TestU01~\cite{LEcuyerS07}.
-Dans son acception vulgarisée,
-la notion de chaos est souvent réduite à celle de forte sensibilité
+Dans son acception vulgarisée,
+la notion de chaos est souvent réduite à celle de forte sensibilité
aux conditions initiales (le fameux \og \emph{effet papillon}\fg{}):
-une fonction continue $k$ définie sur un espace métrique
+une fonction continue $k$ définie sur un espace métrique
est dite \emph{fortement sensible aux conditions initiales} si pour tout
point $x$ et pour toute valeur positive $\epsilon$
il est possible de trouver un point $y$, arbitrairement proche
de $x$, et un entier $t$ tels que la distance entre les
-$t^{\textrm{ièmes}}$ itérés de $x$ et de $y$
--- notés $k^t(x)$ et $k^t(y)$
--- est supérieure à $\epsilon$.
-Cependant, dans sa définition du chaos,
-Devaney~\cite{Devaney} impose à la fonction chaotique deux autres propriétés
-appelées \emph{transitivité} et \emph{régularité},
-Les fonctions citées plus haut ont été étudiées
-au regard de ces propriétés et ont été prouvées comme chaotiques sur $\R$.
-Cependant, rien ne garantit que ces propriétés sont préservées sur les nombres
-flottants qui est le domaine d'interprétation des nombres réels de $\R$.
-
-Pour éviter cette perte de chaos, nous avons présenté des PRNGs qui itèrent des
+$t^{\textrm{ièmes}}$ itérés de $x$ et de $y$
+-- notés $k^t(x)$ et $k^t(y)$
+-- est supérieure à $\epsilon$.
+Cependant, dans sa définition du chaos,
+Devaney~\cite{Devaney} impose à la fonction chaotique deux autres propriétés
+appelées \emph{transitivité} et \emph{régularité},
+Les fonctions citées plus haut ont été étudiées
+au regard de ces propriétés et ont été prouvées comme chaotiques sur $\R$.
+Cependant, rien ne garantit que ces propriétés sont préservées sur les nombres
+flottants qui est le domaine d'interprétation des nombres réels de $\R$.
+
+Pour éviter cette perte de chaos, nous avons présenté des PRNGs qui itèrent des
fonctions continues $G_f$ sur un domaine discret $\{ 1, \ldots, n \}^{\Nats}
-\times \{0,1\}^n$ où $f$ est une fonction booléenne (\textit{i.e.}, $f :
-\{0,1\}^n \rightarrow \{0,1\}^n$). Ces générateurs sont
-$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11ip},
+\times \{0,1\}^n$ où $f$ est une fonction booléenne (\textit{i.e.}, $f :
+\{0,1\}^n \rightarrow \{0,1\}^n$). Ces générateurs sont
+$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} et
-$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} où \textit{CI} signifie
+$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} où \textit{CI} signifie
\emph{Chaotic Iterations}.
-Dans~\cite{bcgr11ip} nous avons tout d'abord prouvé que pour établir la nature
-chaotique de l'algorithme $\textit{CIPRNG}_f^1$, il est nécessaire et suffisant
-que le graphe des itérations asynchrones soit fortement connexe. Nous avons
-ensuite prouvé que pour que la sortie de cet algorithme suive une loi de
-distribution uniforme, il est nécessaire et suffisant que la matrice de Markov
-associée à ce graphe soit doublement stochastique. Nous avons enfin établi des
-conditions suffisantes pour garantir la première propriété de connexité. Parmi
-les fonctions générées, on ne retenait ensuite que celles qui vérifiait la
-seconde propriété. Dans~\cite{chgw14oip}, nous avons proposé une démarche
-algorithmique permettant d'obtenir directement un graphe d'itérations fortement
+Dans~\cite{bcgr11:ip} nous avons tout d'abord prouvé que pour établir la nature
+chaotique de l'algorithme $\textit{CIPRNG}_f^1$, il est nécessaire et suffisant
+que le graphe des itérations asynchrones soit fortement connexe. Nous avons
+ensuite prouvé que pour que la sortie de cet algorithme suive une loi de
+distribution uniforme, il est nécessaire et suffisant que la matrice de Markov
+associée à ce graphe soit doublement stochastique. Nous avons enfin établi des
+conditions suffisantes pour garantir la première propriété de connexité. Parmi
+les fonctions générées, on ne retenait ensuite que celles qui vérifiait la
+seconde propriété. Dans~\cite{chgw14oip}, nous avons proposé une démarche
+algorithmique permettant d'obtenir directement un graphe d'itérations fortement
connexe et dont la matrice de Markov est doublement stochastique. Le travail
-présenté ici généralise ce dernier article en changeant le domaine d'itération,
-et donc de métrique. L'algorithme obtenu possède les même propriétés théoriques
-mais un temps de mélange plus réduit.
+présenté ici généralise ce dernier article en changeant le domaine d'itération,
+et donc de métrique. L'algorithme obtenu possède les même propriétés théoriques
+mais un temps de mélange plus réduit.
-% Pour décrire un peu plus précisément le principe de
-% la génération pseudo-aléatoire, considérons l'espace booléen
+% Pour décrire un peu plus précisément le principe de
+% la génération pseudo-aléatoire, considérons l'espace booléen
% $\Bool=\{0,1\}$
% muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{}
-% définies par les tableaux ci-dessous:
+% définies par les tableaux ci-dessous:
% \begin{center}
% \begin{tabular}{|c|c|c|}
% \end{center}
-% La fonction itérée est
-% une fonction $f$ de $\Bool^n$ dans lui-même qui à
+% La fonction itérée est
+% une fonction $f$ de $\Bool^n$ dans lui-même qui à
% un mot binaire $x = (x_1,\ldots,x_n)$
% associe le mot $(f_1(x),\ldots, f_n(x))$.
-% Un exemple de fonction de $\Bool^n$ dans lui-même
-% est la fonction négation
-% définie par
+% Un exemple de fonction de $\Bool^n$ dans lui-même
+% est la fonction négation
+% définie par
% $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$.
-% Le principe itératif, basé sur le mode opératoire dit \emph{asynchrone}, est le
-% suivant: à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, et
-% le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par $x^{t+1} = (x_1^t,\ldots ,
+% Le principe itératif, basé sur le mode opératoire dit \emph{asynchrone}, est le
+% suivant: à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, et
+% le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par $x^{t+1} = (x_1^t,\ldots ,
% x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
-% Au bout d'un nombre $N$ d'itérations, si la fonction (notée $G_f$ dans ce
-% document) que l'on peut associer à l'algorithme décrit ci-dessus a de \og
-% \emph{bonnes}\fg{} propriétés chaotiques, le mot $x^N$ doit être \og \emph{très
-% différent}\fg{} de $x^0$ de façon à sembler ne plus dépendre de $x_0$. En
-% effet, pour un générateur aléatoire, il faut que la structure de $x^N$ semble
-% être due au hasard; pour une application cryptographique, il faut qu'il soit
-% matériellement impossible (dans les conditions techniques actuelles) de
-% retrouver $x^0$ à partir de $x^N$.
+% Au bout d'un nombre $N$ d'itérations, si la fonction (notée $G_f$ dans ce
+% document) que l'on peut associer à l'algorithme décrit ci-dessus a de \og
+% \emph{bonnes}\fg{} propriétés chaotiques, le mot $x^N$ doit être \og \emph{très
+% différent}\fg{} de $x^0$ de façon à sembler ne plus dépendre de $x_0$. En
+% effet, pour un générateur aléatoire, il faut que la structure de $x^N$ semble
+% être due au hasard; pour une application cryptographique, il faut qu'il soit
+% matériellement impossible (dans les conditions techniques actuelles) de
+% retrouver $x^0$ à partir de $x^N$.
% Tous les mots de $\Bool^n$ peuvent constituer les $2^n$ sommets d'un
% \gls{graphoriente} (cf. glossaire) dans lequel un arc relie deux sommets $x$ et
-% $x'$ s'il existe une itération de l'algorithme de génération qui permet de
-% passer directement de $x$ à $x'$. Ce graphe est appelé le \emph{graphe d'itérations} et
+% $x'$ s'il existe une itération de l'algorithme de génération qui permet de
+% passer directement de $x$ à $x'$. Ce graphe est appelé le \emph{graphe d'itérations} et
% nous montrons ici que si l'on a un \gls{graphfortementconnexe} (cf. glossaire),
% alors la fonction $G_f$ est transitive, donc chaotique.
-% Enfin, un bon générateur aléatoire se doit de
+% Enfin, un bon générateur aléatoire se doit de
% fournir des nombres selon une \gls{distributionuniforme} (cf. glossaire).
-% La dernière partie de cet article donne,
-% dans le cas où le graphe d'itérations est fortement connexe,
-% une condition nécessaire et suffisante pour que
-% cette propriété soit satisfaite.
+% La dernière partie de cet article donne,
+% dans le cas où le graphe d'itérations est fortement connexe,
+% une condition nécessaire et suffisante pour que
+% cette propriété soit satisfaite.
-% Le chaos a été appliqué à des domaines variés en
+% Le chaos a été appliqué à des domaines variés en
% informatique, comme les fonctions de hachage,
-% la stéganographie, la génération de nombres pseudo
-% aléatoires\ldots
-% Toutes ces applications exploitent les propriétés définissant des
-% fonctions chaotiques et énoncées par Devaney, telles que la
-% transitivité, la régularité et la sensibilité aux conditions initiales.
-
-
-% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs
-% définis par une fonction chaotique $f$ d'un domaine $E$ dans lui-même.
-% En démarrant d'un état quelconque $x$ du sytème,
-% nommé par la suite \emph{configuration},
-% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots
-% où $f^k(x)$ est le $k^{\textrm{ème}}$ itéré de $f$ en $x$.
+% la stéganographie, la génération de nombres pseudo
+% aléatoires\ldots
+% Toutes ces applications exploitent les propriétés définissant des
+% fonctions chaotiques et énoncées par Devaney, telles que la
+% transitivité, la régularité et la sensibilité aux conditions initiales.
+
+
+% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs
+% définis par une fonction chaotique $f$ d'un domaine $E$ dans lui-même.
+% En démarrant d'un état quelconque $x$ du sytème,
+% nommé par la suite \emph{configuration},
+% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots
+% où $f^k(x)$ est le $k^{\textrm{ème}}$ itéré de $f$ en $x$.
% La plupart des applications informatiques dite \og chaotiques \fg{}
-% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$
-% où $f$ est la fonction \emph{tente} avec $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent})
-% ou la fonction \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log})
-% connues pour être chaotiques dans $\R$.
+% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$
+% où $f$ est la fonction \emph{tente} avec $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent})
+% ou la fonction \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log})
+% connues pour être chaotiques dans $\R$.
% \begin{figure}[hb]
% \begin{center}
% \label{fig:iter:log}
% }
% \end{center}
-% \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}}
+% \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}}
% \end{figure}
-% Cependant il n'a pas été établi que des fonctions prouvées
-% comme étant chaotiques sur $\R$ le restent sur les nombres à virgule flottante,
-% qui est le domaine d'interprétation informatique des réels.
-% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos
-% lors de l'exécution des programmes implémentant ces fonctions.
-% Ce document présente pour cela l'alternative suivante:
-% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$,
-% où $\Bool$ est le domaine des booléens $\{0,1\}$, on
+% Cependant il n'a pas été établi que des fonctions prouvées
+% comme étant chaotiques sur $\R$ le restent sur les nombres à virgule flottante,
+% qui est le domaine d'interprétation informatique des réels.
+% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos
+% lors de l'exécution des programmes implémentant ces fonctions.
+% Ce document présente pour cela l'alternative suivante:
+% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$,
+% où $\Bool$ est le domaine des booléens $\{0,1\}$, on
% construit une fonction $G_f : \llbracket 1 ; n \rrbracket^{\Nats} \times \Bool^n$,
-% où $\llbracket 1 ; n \rrbracket$ est l'ensemble des entiers
-% $\{1, 2, \hdots, n\}$ et on itère celle-ci.
-% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques
-% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant
-% l'implémentation.
-% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation
-% définie par
+% où $\llbracket 1 ; n \rrbracket$ est l'ensemble des entiers
+% $\{1, 2, \hdots, n\}$ et on itère celle-ci.
+% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques
+% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant
+% l'implémentation.
+% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation
+% définie par
% $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$.
-% De plus, plutôt que de trouver des exemples de telles fonctions $f$, et de prouver
-% (\textit{a posteriori}) la chaoticité de $G_f$, on peut penser à caractériser
-% les fonctions engendrant systématiquement des fonctions chaotiques.
-% Ce document présente une telle caractérisation
-% qui s'exprime sur le graphe des itérations asynchrones
-% de la fonction booléenne $f$, qui est, intuitivement, le graphe
-% de toutes les itérations possibles de la fonction.
-% Cette situation se réduit en un problème portant sur des graphes à $2^n$
+% De plus, plutôt que de trouver des exemples de telles fonctions $f$, et de prouver
+% (\textit{a posteriori}) la chaoticité de $G_f$, on peut penser à caractériser
+% les fonctions engendrant systématiquement des fonctions chaotiques.
+% Ce document présente une telle caractérisation
+% qui s'exprime sur le graphe des itérations asynchrones
+% de la fonction booléenne $f$, qui est, intuitivement, le graphe
+% de toutes les itérations possibles de la fonction.
+% Cette situation se réduit en un problème portant sur des graphes à $2^n$
% sommets.
-% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse
+% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse
% au graphe des interactions de $f$, qui, intuitivement,
-% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$
-% et qui ne contient que $n$ sommets (et qui est à comparer aux $2^n$
+% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$
+% et qui ne contient que $n$ sommets (et qui est à comparer aux $2^n$
% sommets.
-% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$.
-% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe
-% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques.
+% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$.
+% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe
+% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques.
-% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération
-% de nombres pseudo aléatoires, l'aléa étant intuitivement
+% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération
+% de nombres pseudo aléatoires, l'aléa étant intuitivement
% une notion proche de celle du chaos.
-% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins
-% garantir que l'ensemble des valeurs retournées par l'algorithme suit
-% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique.
-% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$
-% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires.
-% Cette idée est validée après évaluation
-% des générateurs de nombres pseudo aléatoires
+% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins
+% garantir que l'ensemble des valeurs retournées par l'algorithme suit
+% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique.
+% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$
+% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires.
+% Cette idée est validée après évaluation
+% des générateurs de nombres pseudo aléatoires
% sur une batterie de tests.
-% Le reste de ce document est organisé comme suit.
-% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
-% La chaoticité de la fonction engendrée $G_f$ est caractérisée en
+% Le reste de ce document est organisé comme suit.
+% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
+% La chaoticité de la fonction engendrée $G_f$ est caractérisée en
% section~\ref{sec:charac}.
-% Des conditions suffisantes pour obtenir cette chaoticité sont présentées en
+% Des conditions suffisantes pour obtenir cette chaoticité sont présentées en
% section~\ref{sec:sccg}.
-% L'application à la génération de nombres pseudo aléatoires est formalisée,
-% les fonctions dont l'image est uniformément distribuée sur le domaine sont
-% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}.
-
-Dans la section suivante, nous rappelons les notions élémentaires sur les
-systèmes booléens. La section~\ref{section:caracterisation} présente les
-définitions théoriques liées au chaos. Ensuite, une application de ces résultats
-à la génération de nombres pseudo-aléatoires est proposée en
-section~\ref{section:genpa} ainsi qu'une méthode permettant d'obtenir des
-matrices d'itérations doublement stochastiques en
-section~\ref{section:genmat}. Enfin, en section~\ref{section:expes} la qualité
-du PRNG obtenu est éprouvée avec les tests standards du domaine.
+% L'application à la génération de nombres pseudo aléatoires est formalisée,
+% les fonctions dont l'image est uniformément distribuée sur le domaine sont
+% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}.
+
+Dans la section suivante, nous rappelons les notions élémentaires sur les
+systèmes booléens. La section~\ref{section:caracterisation} présente les
+définitions théoriques liées au chaos. Ensuite, une application de ces résultats
+à la génération de nombres pseudo-aléatoires est proposée en
+section~\ref{section:genpa} ainsi qu'une méthode permettant d'obtenir des
+matrices d'itérations doublement stochastiques en
+section~\ref{section:genmat}. Enfin, en section~\ref{section:expes} la qualité
+du PRNG obtenu est éprouvée avec les tests standards du domaine.
%%% Local Variables:
\documentclass{ita}
\usepackage{graphicx}
+\usepackage{caption}
+\usepackage{subcaption}
+
\usepackage{dsfont}
\usepackage{stmaryrd}
-\usepackage[font=footnotesize]{subfig}
+%\usepackage[font=footnotesize]{subfig}
\usepackage{ifthen}
\usepackage{color}
\usepackage{algorithm2e}
\usepackage{epstopdf}
+%\usepackage{ntheorem}
-
-\usepackage[latin1]{inputenc}
+\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% Définitions personnelles
+% Définitions personnelles
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\definecolor{bleuclair}{rgb}{0.75,0.75,1.0}
\def \ts {\tau_{\rm stop}}
-% \theoremstyle{plain}
-% \theoremheaderfont{\normalfont\bfseries\sc}
-% \theorembodyfont{\slshape}
-% \theoremsymbol{\ensuremath{\diamondsuit}}
-% \theoremprework{\bigskip}
-% \theoremseparator{.}
-\newtheorem{Def}{\underline{Definition}}
-\newtheorem{Lemma}{\underline{Lemma}}
-\newtheorem{Theo}{\underline{Theorem}}
-% \theoremheaderfont{\sc}
-% \theorembodyfont{\upshape}
-% \theoremstyle{nonumberplain}
-% \theoremseparator{}
-% \theoremsymbol{\rule{1ex}{1ex}}
-\newtheorem{Proof}{Proof}
+\newtheorem{Def}{Definition}
+%\newtheorem{Lemma}{\underline{Lemma}}
+\newtheorem{Theo}{Theorem}
+\newtheorem{Corollary}{Corollary}
+\newtheorem{Lemma}{Lemma}
\newtheorem{proposition}{Proposition}
-\newtheorem{xpl}{Running Example}
+\newtheorem*{xpl}{Running Example}
\newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
%\newcommand{\ie}{\textit{i.e.}}
\begin{document}
-\author{Jean-François Couchot, Christophe Guyeux, Pierre-Cyrile Heam}
-\address{Institut FEMTO-ST, Université de Franche-Comté, Belfort, France}
+\author{Jean-François Couchot, Christophe Guyeux, Pierre-Cyrile Heam}
+\address{Institut FEMTO-ST, Université de Franche-Comté, Belfort, France}
-%\author{Sylvain Contassot-Vivier}
-%\address{Loria - UMR 7503, Université de Lorraine, Nancy, France}
-\date{...}
\begin{abstract}
-This paper extends the results presented in~\cite{bcgr11ip}
-and~\cite{chgw14oip} by using the \emph{chaotic} updating mode, in the sense
+This paper extends the results presented in~\cite{bcgr11:ip}
+and~\cite{DBLP:conf/secrypt/CouchotHGWB14}
+by using the \emph{chaotic} updating mode, in the sense
of F. Robert~\cite{Robert}. In this mode, several components of the system
may be updated at each iteration. At the theoretical level, we show that
the properties of chaos and uniformity of the obtained PRNG are preserved.
reduced mixing time.
\end{abstract}
+\maketitle
+
\section{Introduction}
%\input{intro}
\input{chaos}
\section{Generating....}
-\JFC{Reprendre Mons en synthétisant... conclusion: n-cube moins hamitonien.
-question efficacité d'un tel algo}
+\JFC{Reprendre Mons en synthétisant... conclusion: n-cube moins hamitonien.
+question efficacité d'un tel algo}
%\input{chaos}
\section{Random walk on the modified Hypercube}
\input{stopping}
% Donner la borne du stopping time quand on marche dedans (nouveau).
-% Énoncer le problème de la taille de cette borne
+% Énoncer le problème de la taille de cette borne
% (elle est certes finie, mais grande).
%\section{Quality study of the strategy}
-%6) Se pose alors la question de comment générer une stratégie de "bonne qualité". Par exemple, combien de générateurs aléatoires embarquer ? (nouveau)
+%6) Se pose alors la question de comment générer une stratégie de "bonne qualité". Par exemple, combien de générateurs aléatoires embarquer ? (nouveau)
\section{Application to Pseudorandom Number Generation}
\input{prng}
-\JFC{ajouter ici les expérimentations}
+\JFC{ajouter ici les expérimentations}
\section{Conclusion}
+++ /dev/null
-@inproceedings{chgw+14oip,
-inhal = {no},
-domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO, INFO:INFO_SE},
-equipe = {ie},
-classement = {COM},
-author = {Couchot, Jean-Fran\c{c}ois and H\'eam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques},
-title = {Pseudorandom Number Generators with Balanced Gray Codes},
-booktitle = {Secrypt 2014, 11th Int. Conf. on Security and Cryptography},
-pages = {***--***},
-address = {Vienna, Austria},
-month = aug,
-date = {28-30 aout},
-year = 2014,
-note = {Position short paper. To appear},
-
-}
-@Article{rwfg,
- author = {Laurent Saloff-Coste},
- title = {Random Walks on Finite Groups},
- journal = {Probability on Descrete Structures},
- year = {},
- OPTkey = {},
- volume = {110},
- OPTnumber = {},
- pages = {263-346},
- OPTmonth = {},
- note = {http://stat.stanford.edu/~cgates/PERSI/papers/rwfg.pdf},
- OPTannote = {}
-}
-
-@book{LevinPeresWilmer2006,
- added-at = {2010-01-19T17:51:27.000+0100},
- author = {Levin, David A. and Peres, Yuval and Wilmer, Elizabeth L.},
- biburl = {http://www.bibsonomy.org/bibtex/2097dc4d1d0e412b2444f540b04110797/tmalsburg},
- interhash = {61354795a6accb6407bfdbf04753a683},
- intrahash = {097dc4d1d0e412b2444f540b04110797},
- keywords = {markovchains probabilitytheory textbook},
- publisher = {American Mathematical Society},
- timestamp = {2010-01-19T17:51:27.000+0100},
- title = {{Markov chains and mixing times}},
- url = {http://scholar.google.com/scholar.bib?q=info:3wf9IU94tyMJ:scholar.google.com/&output=citation&hl=en&as_sdt=2000&ct=citation&cd=0},
- year = 2006
-}
-
-@BOOK{devaney,
- title = {An Introduction to Chaotic Dynamical Systems},
- publisher = {Addison-Wesley},
- year = {1989},
- author = {Devaney, Robert L.},
- address = {Redwood City, CA},
- edition = {2nd}
-}
-
-
-@ARTICLE{Banks92,
- author = {J. Banks and J. Brooks and G. Cairns and P. Stacey},
- title = {On {D}evaney's Definition of Chaos},
- journal = {Amer. Math. Monthly},
- year = {1992},
- volume = {99},
- pages = {332--334},
- keywords = {(c+),},
- owner = {guyeux},
- timestamp = {27/01/2008}
-}
-
-
-@INPROCEEDINGS{wbg10ip,
- author = {Wang, Qianxue and Bahi, Jacques and Guyeux, Christophe and Fang,
- Xiaole},
- title = {Randomness quality of {CI} chaotic generators. Application to Internet
- security},
- booktitle = {INTERNET'2010. The 2nd Int. Conf. on Evolving Internet},
- year = {2010},
- pages = {125--130},
- address = {Valencia, Spain},
- month = sep,
- publisher = {IEEE Computer Society Press},
- note = {Best Paper award},
- classement = {ACTI},
- doi = {10.1109/INTERNET.2010.30},
- domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
- equipe = {and},
- inhal = {no},
- url = {http://doi.ieeecomputersociety.org/10.1109/INTERNET.2010.30}
-}
-
-
-
-@INPROCEEDINGS{bgw10ip,
- author = {Bahi, Jacques and Guyeux, Christophe and Wang, Qianxue},
- title = {A Pseudo Random Numbers Generator Based on Chaotic Iterations. Application
- to Watermarking},
- booktitle = {WISM 2010, Int. Conf. on Web Information Systems and Mining},
- year = {2010},
- volume = {6318},
- series = {LNCS},
- pages = {202--211},
- address = {Sanya, China},
- month = oct,
- classement = {ACTI},
- doi = {10.1007/978-3-642-16515-3_26},
- domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
- equipe = {and},
- inhal = {no},
- url = {http://dx.doi.org/10.1007/978-3-642-16515-3_26}
-}
-
-
-
-@INPROCEEDINGS{bgw09ip,
- author = {Bahi, Jacques and Guyeux, Christophe and Wang, Qianxue},
- title = {A novel pseudo-random generator based on discrete chaotic iterations},
- booktitle = {INTERNET'09, 1-st Int. Conf. on Evolving Internet},
- year = {2009},
- pages = {71--76},
- address = {Cannes, France},
- month = aug,
- classement = {ACTI},
- doi = {10.1109/INTERNET.2009.18},
- domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
- equipe = {and},
- inhal = {no},
- url = {http://dx.doi.org/10.1109/INTERNET.2009.18}
-}
-
-
-
-@INPROCEEDINGS{guyeuxTaiwan10,
- author = {Bahi, Jacques M. and Guyeux, Christophe and Wang, Qianxue},
- title = {Improving random number generators by chaotic iterations. {A}pplication
- in data hiding},
- booktitle = {ICCASM 2010, Int. Conf. on Computer Application and System Modeling},
- year = {2010},
- pages = {V13-643--V13-647},
- address = {Taiyuan, China},
- month = oct,
- classement = {ACTI},
- doi = {10.1109/ICCASM.2010.5622199},
- domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
- equipe = {and},
- inhal = {no},
- url = {http://dx.doi.org/10.1109/ICCASM.2010.5622199}
-}
-
-@inproceedings{bcgw11ip,
-inhal = {no},
-domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-equipe = {and},
-classement = {ACTI},
-author = {Bahi, Jacques and Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Wang, Qianxue},
-title = {Class of Trustworthy Pseudo Random Number Generators},
-booktitle = {INTERNET 2011, the 3-rd Int. Conf. on Evolving Internet},
-pages = {72--77},
-address = {Luxembourg, Luxembourg},
-month = jun,
-year = 2011}
-
-
-
-@INPROCEEDINGS{bcgr11ip,
- author = {Bahi, Jacques and Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe
- and Richard, Adrien},
- title = {On the Link Between Strongly Connected Iteration Graphs and Chaotic
- Boolean Discrete-Time Dynamical Systems},
- booktitle = {FCT'11, 18th Int. Symp. on Fundamentals of Computation Theory},
- year = {2011},
- volume = {6914},
- series = {LNCS},
- pages = {126--137},
- address = {Oslo, Norway},
- month = aug,
- classement = {ACTI},
- doi = {10.1007/978-3-642-22953-4_11},
- domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
- equipe = {and},
- inhal = {no},
- url = "http://dx.doi.org/10.1007/978-3-642-22953-4_11"
-}
-
-
-
-@INPROCEEDINGS{bg10aip,
- author = {Bahi, Jacques and Guyeux, Christophe},
- title = {Topological chaos and chaotic iterations, application to Hash functions},
- booktitle = {IJCNN'10, Int. Joint Conf. on Neural Networks, joint to WCCI'10,
- IEEE World Congress on Computational Intelligence},
- year = {2010},
- pages = {1--7},
- address = {Barcelona, Spain},
- month = jul,
- note = {Best paper award},
- classement = {ACTI},
- doi = {10.1109/IJCNN.2010.5596512},
- domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
- equipe = {and},
- inhal = {no},
- url = {http://dx.doi.org/10.1109/IJCNN.2010.5596512}
-}
-
-
-@ARTICLE{DBLPjournals/corr/abs-1112-5239,
- author = {Jacques M. Bahi and Rapha{\"e}l Couturier and Christophe Guyeux and
- Pierre-Cyrille H{\'e}am},
- title = {Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom
- Numbers on GPU},
- journal = {CoRR},
- year = {2011},
- volume = {abs/1112.5239},
- bibsource = {DBLP, http://dblp.uni-trier.de},
- ee = {http://arxiv.org/abs/1112.5239}
-}
-
-@MISC{Nist10,
- author = {E. Barker and A. Roginsky},
- title = {DRAFT {N}{I}{S}{T} Special Publication 800-131 Recommendation for
- the Transitioning of Cryptographic Algorithms and Key Sizes},
- year = {2010},
- owner = {christophe},
- timestamp = {2010.08.18}
-}
-
-
-@ARTICLE{LEcuyerS07,
- author = {Pierre L'Ecuyer and Richard J. Simard},
- title = {Test{U01}: {A} {C} library for empirical testing of random number
- generators},
- journal = {ACM Trans. Math. Softw},
- year = {2007},
- volume = {33},
- number = {4},
- bibdate = {2007-11-06},
- bibsource = {DBLP, http://dblp.uni-trier.de/db/journals/toms/toms33.html#LEcuyerS07},
- url = {http://doi.acm.org/10.1145/1268776.1268777}
-}
-
-
-@ARTICLE{Marsaglia1996,
- author = {G. Marsaglia},
- title = {DIEHARD: a battery of tests of randomness},
- journal = {http://stat.fsu.edu/~geo/diehard.html},
- year = {1996},
- owner = {qianxue},
- timestamp = {2009.11.09}
-}
-
-@PHDTHESIS{Xiaole13,
- author = {Xiaole Fang},
- title = {Utilization of chaotic dynamics for generating pseudorandom numbers
- in various contexts},
- school = {Universit\'{e} de Franche-Comt\'{e}},
- year = {2013},
- owner = {guyeux},
- timestamp = {2008.01.02}
-}
-
-@BOOK{Robert,
- title = {Discrete Iterations, a Metric Study},
- publisher = {Springer-Verlag},
- year = {1986},
- author = {Fran\,cois Robert},
- volume = {6},
- series = {Series in Computational Mathematics}
-}
-
-
-@ARTICLE{915396,
-author={Stojanovski, T. and Pihl, J. and Kocarev, L.},
-journal={Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on},
-title={Chaos-based random number generators. Part II: practical realization},
-year={2001},
-month={Mar},
-volume={48},
-number={3},
-pages={382-385},
-keywords={CMOS analogue integrated circuits;chaos generators;circuit simulation;piecewise linear techniques;random number generation;redundancy;switched current circuits;0.8 micron;1 Mbit/s;chaos-based random number generators;chaotic piecewise-linear one-dimensional map;output bit rate;parasitic attractors;periodic attractors;post-layout circuit simulations;process conditions;redundancy;standard CMOS process;switched current techniques;Bit rate;CMOS process;Chaos;Circuits;Electric breakdown;Information analysis;Piecewise linear techniques;Power supplies;Random number generation;Temperature},
-doi={10.1109/81.915396},
-ISSN={1057-7122},}
-
-
-@ARTICLE{915385,
-author={Stojanovski, T. and Kocarev, L.},
-journal={Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on},
-title={Chaos-based random number generators-part I: analysis [cryptography]},
-year={2001},
-month={Mar},
-volume={48},
-number={3},
-pages={281-288},
-keywords={Markov processes;chaos;cryptography;piecewise linear techniques;random number generation;Markov generating partition;Markov information source;chaos-based random number generators;cryptography;information generation process;parameter values;piecewise-linear one-dimensional map;random number generator;Chaos;Cryptographic protocols;Cryptography;Current measurement;Low-frequency noise;Noise measurement;Random number generation;Random sequences;Security;Semiconductor device noise},
-doi={10.1109/81.915385},
-ISSN={1057-7122},}
-
-@INPROCEEDINGS{5376454,
-author={Li Cao and Lequan Min and Hongyan Zang},
-booktitle={Computational Intelligence and Security, 2009. CIS '09. International Conference on},
-title={A Chaos-Based Pseudorandom Number Generator and Performance Analysis},
-year={2009},
-month={Dec},
-volume={1},
-pages={494-498},
-keywords={binary sequences;chaos;discrete systems;random number generation;synchronisation;2D Arnold cat map;6D discrete chaos map;FIPA-140-2 tests;National Institute of Standard and Technology;binary number sequences;chaos-based pseudorandom number generator;confidence interval analysis;generalized chaos synchronization theorem;performance analysis;Chaos;Chaotic communication;Computational intelligence;NIST;Nonlinear dynamical systems;Performance analysis;Random number generation;Security;Space technology;Testing;Discrete chaos map;generalized chaos synchronization;one-time-pad;statistical test},
-doi={10.1109/CIS.2009.203},}
-
-@article{bfgw13ij,
-inhal = {no},
-domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-equipe = {and},
-classement = {ACLI},
-impact-factor ={1.065},
-isi-acro = {J NETW COMPUT APPL},
-author = {Bahi, Jacques and Fang, Xiaole and Guyeux, Christophe and Wang, Qianxue},
-title = {Suitability of chaotic iterations schemes using {XORshift} for security applications},
-journal = {JNCA, Journal of Network and Computer Applications},
-pages = {282--292},
-volume = 37,
-doi = {10.1016/j.jnca.2013.03.001},
-url = {http://dx.doi.org/10.1016/j.jnca.2013.03.001},
-abstract = {The design and engineering of original cryptographic solutions is a major concern to provide secure information systems. In a previous study, we have described a generator based on chaotic iterations, which uses the well-known XORshift generator. By doing so, we have improved the statistical performances of XORshift and make it behave chaotically, as defined by Devaney. The speed and security of this former generator have been improved in a second study, to make its usage more relevant in the Internet security context. In this paper, these contributions are summarized and a new version of the generator is introduced. It is based on a new Lookup Table implying a large improvement of speed. A comparison and a security analysis between the XORshift and these three versions of our generator are proposed, and various new statistical results are given. Finally, an application in the information hiding framework is presented, to give an illustrative example of the use of such a generator in the Internet security field.},
-publisher = {Elsevier},
-year = 2013,
-
-}
-
-
-@article{Marsaglia2003JSSOBKv08i14,
- author = "George Marsaglia",
- title = "Xorshift RNGs",
- journal = "Journal of Statistical Software",
- volume = "8",
- number = "14",
- pages = "1--6",
- day = "4",
- month = "7",
- year = "2003",
- CODEN = "JSSOBK",
- ISSN = "1548-7660",
- bibdate = "2003-07-04",
- URL = "http://www.jstatsoft.org/v08/i14",
- accepted = "2003-07-04",
- acknowledgement = "",
- keywords = "",
- submitted = "2003-05-06",
-}
-
-
-
-@INPROCEEDINGS{cghwb14ip,
- author = {Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Heam,
-Pierre-Cyrille, and Wang, Qianxue and Bahi, Jacques},
- title = {Pseudorandom Number Generators with Balanced Gray Codes},
- booktitle = {SECRYPT 2014, the 11th International Conference on Security and Cryptography},
- year = {2014},
- pages = {***--***},
- address = {Vienna, Austria},
- month = aug,
- classement = {ACTI},
- doi = {10.1007/978-3-642-22953-4_11},
- domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
- equipe = {and},
- inhal = {no},
-}
-
-@Article{ZanSup04,
- author = {Suparta, IN and Zanten, AJ van},
- title = {Totally balanced and exponentially balanced Gray codes},
- journal = {Discrete Analysis and Operation Research (Russia)},
- year = {2004},
- OPTkey = {},
- volume = {11},
- number = {4},
- pages = {81-98},
- OPTmonth = {},
- OPTnote = {},
- OPTannote = {}
-}
-
-@Article{Feder2009NTB,
- title = "Nearly tight bounds on the number of Hamiltonian
- circuits of the hypercube and generalizations",
- author = "Tom{\'a}s Feder and Carlos S. Subi",
- journal = "Info. Process. Lett",
- year = "2009",
- number = "5",
- volume = "109",
- pages = "267--272",
- URL = "http://dx.doi.org/10.1016/j.ipl.2008.10.015",
-}
-
-
of disjunction '+', of negation '$\overline{~}$', and of
disjunctive union $\oplus$.
-Let $n$ be a positive integer. A {\emph{Boolean map} $f$ is
-a function from $\Bool^n$
+Let us first introduce basic notations.
+Let $\mathsf{N}$ be a positive integer. The set $\{1, 2, \hdots , \mathsf{N}\}$
+of integers belonging between $1$ and $\mathsf{N}$
+is further denoted as $\llbracket 1, \mathsf{N} \rrbracket$.
+A {\emph{Boolean map} $f$ is
+a function from $\Bool^{\mathsf{N}}$
to itself
such that
-$x=(x_1,\dots,x_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$.
+$x=(x_1,\dots,x_{\mathsf{N}})$ maps to $f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x))$.
+In what follows, for any finite set $X$, $|X|$ denotes its cardinality and
+$\lfloor y \rfloor$ is
+the largest integer lower than $y$.
+
Functions are iterated as follows.
At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be
-``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''.
+``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;{\mathsf{N}} \rrbracket$ called ``strategy''.
Formally,
-let $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by
+let $F_f: \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket$ to $\Bool^{\mathsf{N}}$ be defined by
\[
-F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n).
+F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}}).
\]
-Then, let $x^0\in\Bool^n$ be an initial configuration
+Then, let $x^0\in\Bool^{\mathsf{N}}$ be an initial configuration
and $s\in
-\llbracket1;n\rrbracket^\Nats$ be a strategy,
+\llbracket1;{\mathsf{N}}\rrbracket^\Nats$ be a strategy,
the dynamics are described by the recurrence
\begin{equation}\label{eq:asyn}
-x^{t+1}=F_f(s_t,x^t).
+x^{t+1}=F_f(x^t,s_t).
\end{equation}
+
+
+
Let be given a Boolean map $f$. Its associated
{\emph{iteration graph}} $\Gamma(f)$ is the
directed graph such that the set of vertices is
-$\Bool^n$, and for all $x\in\Bool^n$ and $i\in \llbracket1;n\rrbracket$,
-the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$.
+$\Bool^{\mathsf{N}}$, and for all $x\in\Bool^{\mathsf{N}}$ and $i\in \llbracket1;{\mathsf{N}}\rrbracket$,
+the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(x,i)$.
+Each arc $(x,F_f(x,i))$ is labelled with $i$.
+
\begin{xpl}
-Let us consider for instance $n=3$.
+Let us consider for instance ${\mathsf{N}}=3$.
Let
$f^*: \Bool^3 \rightarrow \Bool^3$ be defined by
$f^*(x_1,x_2,x_3) =
\overline{x_1}\overline{x_3} + x_1x_2)$.
The iteration graph $\Gamma(f^*)$ of this function is given in
Figure~\ref{fig:iteration:f*}.
+\end{xpl}
-\vspace{-1em}
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.5]{images/iter_f0c}
\end{center}
-\vspace{-0.5em}
\caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*}
\end{figure}
-\end{xpl}
-
-Let thus be given such kind of map.
-This article focuses on studying its iterations according to
-the equation~(\ref{eq:asyn}) with a given strategy.
-First of all, this can be interpreted as walking into its iteration graph
-where the choice of the edge to follow is decided by the strategy.
-Notice that the iteration graph is always a subgraph of
-$n$-cube augmented with all the self-loop, \textit{i.e.}, all the
-edges $(v,v)$ for any $v \in \Bool^n$.
-Next, if we add probabilities on the transition graph, iterations can be
-interpreted as Markov chains.
+Let us finally recall the pseudorandom number generator $\chi_{\textit{14Secrypt}}$
+\cite{DBLP:conf/secrypt/CouchotHGWB14}
+formalized in Algorithm~\ref{CI Algorithm}.
+It is based on random walks in $\Gamma(f)$.
+More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$,
+an input PRNG \textit{Random},
+an integer $b$ that corresponds to a number of iterations, and
+an initial configuration $x^0$.
+Starting from $x^0$, the algorithm repeats $b$ times
+a random choice of which edge to follow and traverses this edge.
+The final configuration is thus outputted.
-\begin{xpl}
-Let us consider for instance
-the graph $\Gamma(f)$ defined
-in \textsc{Figure~\ref{fig:iteration:f*}.} and
-the probability function $p$ defined on the set of edges as follows:
-$$
-p(e) \left\{
-\begin{array}{ll}
-= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
-= \frac{1}{6} \textrm{ otherwise.}
-\end{array}
-\right.
-$$
-The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is
-\[
-P=\dfrac{1}{6} \left(
-\begin{array}{llllllll}
-4&1&1&0&0&0&0&0 \\
-1&4&0&0&0&1&0&0 \\
-0&0&4&1&0&0&1&0 \\
-0&1&1&4&0&0&0&0 \\
-1&0&0&0&4&0&1&0 \\
-0&0&0&0&1&4&0&1 \\
-0&0&0&0&1&0&4&1 \\
-0&0&0&1&0&1&0&4
-\end{array}
-\right)
-\]
-\end{xpl}
+\begin{algorithm}[ht]
+\begin{scriptsize}
+%\JFC{Mettre ceci dans une boite flottante}
+\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ (${\mathsf{N}}$ bits)}
+\KwOut{a configuration $x$ (${\mathsf{N}}$ bits)}
+$x\leftarrow x^0$\;
+\For{$i=0,\dots,b-1$}
+{
+$s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
+$x\leftarrow{F_f(x,s)}$\;
+}
+return $x$\;
+\end{scriptsize}
+\caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ PRNG}
+\label{CI Algorithm}
+\end{algorithm}
-% % Let us first recall the \emph{Total Variation} distance $\tv{\pi-\mu}$,
-% % which is defined for two distributions $\pi$ and $\mu$ on the same set
-% % $\Bool^n$ by:
-% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$
-% % It is known that
-% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$
-
-% % Let then $M(x,\cdot)$ be the
-% % distribution induced by the $x$-th row of $M$. If the Markov chain
-% % induced by
-% % $M$ has a stationary distribution $\pi$, then we define
-% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
-% Intuitively $d(t)$ is the largest deviation between
-% the distribution $\pi$ and $M^t(x,\cdot)$, which
-% is the result of iterating $t$ times the function.
-% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time}
-% with respect to $\varepsilon$ is given by
-% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% It defines the smallest iteration number
-% that is sufficient to obtain a deviation lesser than $\varepsilon$.
-% Notice that the upper and lower bounds of mixing times cannot
-% directly be computed with eigenvalues formulae as expressed
-% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work
-% only consider reversible Markov matrices whereas we do no restrict our
-% matrices to such a form.
+With all this material, we can study the chaos properties of these
+function.
+This is the aims of the next section.
the output of $\textit{Random(1)}$ is uniform in $\{0,1\}$.
Let $f: \Bool^{n} \rightarrow \Bool^{n}$.
-It has been shown~\cite[Th. 4, p. 135]{BCGR11}} that
+It has been shown~\cite[Th. 4, p. 135]{bcgr11:ip} that
if its iteration graph is strongly connected, then
the output of $\chi_{\textit{14Secrypt}}$ follows
a law that tends to the uniform distribution
+
+
+
+Let thus be given such kind of map.
+This article focuses on studying its iterations according to
+the equation~(\ref{eq:asyn}) with a given strategy.
+First of all, this can be interpreted as walking into its iteration graph
+where the choice of the edge to follow is decided by the strategy.
+Notice that the iteration graph is always a subgraph of
+${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the
+edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$.
+Next, if we add probabilities on the transition graph, iterations can be
+interpreted as Markov chains.
+
+\begin{xpl}
+Let us consider for instance
+the graph $\Gamma(f)$ defined
+in \textsc{Figure~\ref{fig:iteration:f*}.} and
+the probability function $p$ defined on the set of edges as follows:
+$$
+p(e) \left\{
+\begin{array}{ll}
+= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
+= \frac{1}{6} \textrm{ otherwise.}
+\end{array}
+\right.
+$$
+The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is
+\[
+P=\dfrac{1}{6} \left(
+\begin{array}{llllllll}
+4&1&1&0&0&0&0&0 \\
+1&4&0&0&0&1&0&0 \\
+0&0&4&1&0&0&1&0 \\
+0&1&1&4&0&0&0&0 \\
+1&0&0&0&4&0&1&0 \\
+0&0&0&0&1&4&0&1 \\
+0&0&0&0&1&0&4&1 \\
+0&0&0&1&0&1&0&4
+\end{array}
+\right)
+\]
+\end{xpl}
+
+
+% % Let us first recall the \emph{Total Variation} distance $\tv{\pi-\mu}$,
+% % which is defined for two distributions $\pi$ and $\mu$ on the same set
+% % $\Bool^n$ by:
+% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$
+% % It is known that
+% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$
+
+% % Let then $M(x,\cdot)$ be the
+% % distribution induced by the $x$-th row of $M$. If the Markov chain
+% % induced by
+% % $M$ has a stationary distribution $\pi$, then we define
+% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
+% Intuitively $d(t)$ is the largest deviation between
+% the distribution $\pi$ and $M^t(x,\cdot)$, which
+% is the result of iterating $t$ times the function.
+% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time}
+% with respect to $\varepsilon$ is given by
+% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
+% It defines the smallest iteration number
+% that is sufficient to obtain a deviation lesser than $\varepsilon$.
+% Notice that the upper and lower bounds of mixing times cannot
+% directly be computed with eigenvalues formulae as expressed
+% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work
+% only consider reversible Markov matrices whereas we do no restrict our
+% matrices to such a form.
+
+
+
+
+
+
+
This section considers functions $f: \Bool^n \rightarrow \Bool^n $
issued from an hypercube where an Hamiltonian path has been removed.
A specific random walk in this modified hypercube is first
