Ava

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 20e256606089108345f7624f6f22121113fd72ec..983aa92ea4681a4dd78a68a607f6a6972a04b927 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -11,6 +11,11 @@
 \usepackage[ruled,vlined]{algorithm2e}
 \usepackage{listings}
 \usepackage[standard]{ntheorem}
 \usepackage[ruled,vlined]{algorithm2e}
 \usepackage{listings}
 \usepackage[standard]{ntheorem}

+\usepackage{algorithmic}
+\usepackage{slashbox}
+\usepackage{ctable}
+\usepackage{tabularx}
+\usepackage{multirow}

 
 % Pour mathds : les ensembles IR, IN, etc.
 \usepackage{dsfont}
 
 % Pour mathds : les ensembles IR, IN, etc.
 \usepackage{dsfont}


@@ -85,7 +90,13 @@ On the other side, speed is not the main requirement in cryptography: the great
 need is to define \emph{secure} generators able to withstand malicious
 attacks. Roughly speaking, an attacker should not be able in practice to make 
 the distinction between numbers obtained with the secure generator and a true random
 need is to define \emph{secure} generators able to withstand malicious
 attacks. Roughly speaking, an attacker should not be able in practice to make 
 the distinction between numbers obtained with the secure generator and a true random

-sequence. 
+sequence. \begin{color}{red} Or, in an equivalent formulation, he or she should not be
+able (in practice) to predict the next bit of the generator, having the knowledge of all the 
+binary digits that have been already released. ``Being able in practice'' refers here
+to the possibility to achieve this attack in polynomial time, and to the exponential growth
+of the difficulty of this challenge when the size of the parameters of the PRNG increases.
+\end{color}
+

 Finally, a small part of the community working in this domain focuses on a
 third requirement, that is to define chaotic generators.
 The main idea is to take benefits from a chaotic dynamical system to obtain a
 Finally, a small part of the community working in this domain focuses on a
 third requirement, that is to define chaotic generators.
 The main idea is to take benefits from a chaotic dynamical system to obtain a


@@ -119,10 +130,19 @@ statistical perfection refers to the ability to pass the whole
 {\it BigCrush} battery of tests, which is widely considered as the most
 stringent statistical evaluation of a sequence claimed as random.
 This battery can be found in the well-known TestU01 package~\cite{LEcuyerS07}.
 {\it BigCrush} battery of tests, which is widely considered as the most
 stringent statistical evaluation of a sequence claimed as random.
 This battery can be found in the well-known TestU01 package~\cite{LEcuyerS07}.

+\begin{color}{red}
+More precisely, each time we performed a test on a PRNG, we ran it
+twice in order to observe if all $p-$values are inside [0.01, 0.99]. In
+fact, we observed that few $p-$values (less than ten) are sometimes
+outside this interval but inside [0.001, 0.999], so that is why a
+second run allows us to confirm that the values outside are not for
+the same test. With this approach all our PRNGs pass the {\it
+  BigCrush} successfully and all $p-$values are at least once inside
+[0.01, 0.99].
+\end{color}

 Chaos, for its part, refers to the well-established definition of a
 chaotic dynamical system proposed by Devaney~\cite{Devaney}.
 
 Chaos, for its part, refers to the well-established definition of a
 chaotic dynamical system proposed by Devaney~\cite{Devaney}.
 

-

 In a previous work~\cite{bgw09:ip,guyeux10} we have proposed a post-treatment on PRNGs making them behave
 as a chaotic dynamical system. Such a post-treatment leads to a new category of
 PRNGs. We have shown that proofs of Devaney's chaos can be established for this
 In a previous work~\cite{bgw09:ip,guyeux10} we have proposed a post-treatment on PRNGs making them behave
 as a chaotic dynamical system. Such a post-treatment leads to a new category of
 PRNGs. We have shown that proofs of Devaney's chaos can be established for this


@@ -152,8 +172,13 @@ The remainder of this paper  is organized as follows. In Section~\ref{section:re
   and on an iteration process called ``chaotic
 iterations'' on which the post-treatment is based. 
 The proposed PRNG and its proof of chaos are given in  Section~\ref{sec:pseudorandom}.
   and on an iteration process called ``chaotic
 iterations'' on which the post-treatment is based. 
 The proposed PRNG and its proof of chaos are given in  Section~\ref{sec:pseudorandom}.

-Section~\ref{sec:efficient    PRNG}   presents   an   efficient
-implementation of  this chaotic PRNG  on a CPU, whereas   Section~\ref{sec:efficient PRNG
+\begin{color}{red}
+Section~\ref{The generation of pseudorandom sequence} illustrates the statistical
+improvement related to the chaotic iteration based post-treatment, for
+our previously released PRNGs and a new efficient 
+implementation on CPU.
+\end{color}
+ Section~\ref{sec:efficient PRNG

   gpu}   describes and evaluates theoretically  the  GPU   implementation. 
 Such generators are experimented in 
 Section~\ref{sec:experiments}.
   gpu}   describes and evaluates theoretically  the  GPU   implementation. 
 Such generators are experimented in 
 Section~\ref{sec:experiments}.


@@ -161,8 +186,9 @@ We show in Section~\ref{sec:security analysis} that, if the inputted
 generator is cryptographically secure, then it is the case too for the
 generator provided by the post-treatment.
 Such a proof leads to the proposition of a cryptographically secure and
 generator is cryptographically secure, then it is the case too for the
 generator provided by the post-treatment.
 Such a proof leads to the proposition of a cryptographically secure and

-chaotic generator on GPU based on the famous Blum Blum Shum
-in Section~\ref{sec:CSGPU}, and to an improvement of the
+chaotic generator on GPU based on the famous Blum Blum Shub
+in Section~\ref{sec:CSGPU}, \begin{color}{red} to a practical
+security evaluation in Section~\ref{sec:Practicak evaluation}, \end{color} and to an improvement of the

 Blum-Goldwasser protocol in Sect.~\ref{Blum-Goldwasser}.
 This research work ends by a conclusion section, in which the contribution is
 summarized and intended future work is presented.
 Blum-Goldwasser protocol in Sect.~\ref{Blum-Goldwasser}.
 This research work ends by a conclusion section, in which the contribution is
 summarized and intended future work is presented.


@@ -170,7 +196,7 @@ summarized and intended future work is presented.
 
 
 
 
 
 

-\section{Related works on GPU based PRNGs}
+\section{Related work on GPU based PRNGs}

 \label{section:related works}
 
 Numerous research works on defining GPU based PRNGs have already been proposed  in the
 \label{section:related works}
 
 Numerous research works on defining GPU based PRNGs have already been proposed  in the


@@ -224,9 +250,12 @@ We can finally remark that, to the best of our knowledge, no GPU implementation
 \label{section:BASIC RECALLS}
 
 This section is devoted to basic definitions and terminologies in the fields of
 \label{section:BASIC RECALLS}
 
 This section is devoted to basic definitions and terminologies in the fields of

-topological chaos and chaotic iterations.
-\subsection{Devaney's Chaotic Dynamical Systems}
+topological chaos and chaotic iterations. We assume the reader is familiar
+with basic notions on topology (see for instance~\cite{Devaney}).
+

 
 

+\subsection{Devaney's Chaotic Dynamical Systems}
+\label{subsec:Devaney}

 In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$
 denotes the $i^{th}$ component of a vector $V$. $f^{k}=f\circ ...\circ f$
 is for the $k^{th}$ composition of a function $f$. Finally, the following
 In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$
 denotes the $i^{th}$ component of a vector $V$. $f^{k}=f\circ ...\circ f$
 is for the $k^{th}$ composition of a function $f$. Finally, the following


@@ -237,7 +266,7 @@ Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
 \mathcal{X} \rightarrow \mathcal{X}$.
 
 \begin{definition}
 \mathcal{X} \rightarrow \mathcal{X}$.
 
 \begin{definition}

-$f$ is said to be \emph{topologically transitive} if, for any pair of open sets
+The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets

 $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
 \varnothing$.
 \end{definition}
 $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
 \varnothing$.
 \end{definition}


@@ -256,7 +285,7 @@ necessarily the same period).
 
 
 \begin{definition}[Devaney's formulation of chaos~\cite{Devaney}]
 
 
 \begin{definition}[Devaney's formulation of chaos~\cite{Devaney}]

-$f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
+The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and

 topologically transitive.
 \end{definition}
 
 topologically transitive.
 \end{definition}
 


@@ -264,12 +293,12 @@ The chaos property is strongly linked to the notion of ``sensitivity'', defined
 on a metric space $(\mathcal{X},d)$ by:
 
 \begin{definition}
 on a metric space $(\mathcal{X},d)$ by:
 
 \begin{definition}

-\label{sensitivity} $f$ has \emph{sensitive dependence on initial conditions}
+\label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions}

 if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
 neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
 $d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
 
 if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
 neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
 $d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
 

-$\delta$ is called the \emph{constant of sensitivity} of $f$.
+The constant $\delta$ is called the \emph{constant of sensitivity} of $f$.

 \end{definition}
 
 Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is
 \end{definition}
 
 Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is


@@ -328,17 +357,15 @@ Let us now recall how to define a suitable metric space where chaotic iterations
 are continuous. For further explanations, see, e.g., \cite{guyeux10}.
 
 Let $\delta $ be the \emph{discrete Boolean metric}, $\delta
 are continuous. For further explanations, see, e.g., \cite{guyeux10}.
 
 Let $\delta $ be the \emph{discrete Boolean metric}, $\delta

-(x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function:
-%%RAPH : ici j'ai coupé la dernière ligne en 2, c'est moche mais bon
-\begin{equation}
+(x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function
+$F_{f}:  \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} 
+\longrightarrow  \mathds{B}^{\mathsf{N}}$
+\begin{equation*}

 \begin{array}{lrll}
 \begin{array}{lrll}

-F_{f}: & \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} &
-\longrightarrow & \mathds{B}^{\mathsf{N}} \\
-& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+ \right.\\
-&       &              & \left. f(E)_{k}.\overline{\delta
-(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
+& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+ f(E)_{k}.\overline{\delta
+(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}%

 \end{array}%
 \end{array}%

-\end{equation}%
+\end{equation*}%

 \noindent where + and . are the Boolean addition and product operations.
 Consider the phase space:
 \begin{equation}
 \noindent where + and . are the Boolean addition and product operations.
 Consider the phase space:
 \begin{equation}


@@ -415,7 +442,7 @@ the metric space $(\mathcal{X},d)$.
 \end{proposition}
 
 The chaotic property of $G_f$ has been firstly established for the vectorial
 \end{proposition}
 
 The chaotic property of $G_f$ has been firstly established for the vectorial

-Boolean negation $f(x_1,\hdots, x_\mathsf{N}) =  (\overline{x_1},\hdots, \overline{x_\mathsf{N}})$ \cite{guyeux10}. To obtain a characterization, we have secondly
+Boolean negation $f_0(x_1,\hdots, x_\mathsf{N}) =  (\overline{x_1},\hdots, \overline{x_\mathsf{N}})$ \cite{guyeux10}. To obtain a characterization, we have secondly

 introduced the notion of asynchronous iteration graph recalled bellow.
 
 Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. The
 introduced the notion of asynchronous iteration graph recalled bellow.
 
 Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. The


@@ -472,33 +499,58 @@ Let us finally remark that the vectorial negation satisfies the hypotheses of bo
 
 We have proposed in~\cite{bgw09:ip} a new family of generators that receives 
 two PRNGs as inputs. These two generators are mixed with chaotic iterations, 
 
 We have proposed in~\cite{bgw09:ip} a new family of generators that receives 
 two PRNGs as inputs. These two generators are mixed with chaotic iterations, 

-leading thus to a new PRNG that improves the statistical properties of each
-generator taken alone. Furthermore, our generator 
-possesses various chaos properties that none of the generators used as input
+leading thus to a new PRNG that 
+\begin{color}{red}
+should improve the statistical properties of each
+generator taken alone. 
+Furthermore, the generator obtained by this way possesses various chaos properties that none of the generators used as input

 present.
 
 
 present.
 
 

+

 \begin{algorithm}[h!]
 \begin{small}
 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$
 ($n$ bits)}
 \KwOut{a configuration $x$ ($n$ bits)}
 $x\leftarrow x^0$\;
 \begin{algorithm}[h!]
 \begin{small}
 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$
 ($n$ bits)}
 \KwOut{a configuration $x$ ($n$ bits)}
 $x\leftarrow x^0$\;

-$k\leftarrow b + \textit{XORshift}(b)$\;
+$k\leftarrow b + PRNG_1(b)$\;

 \For{$i=0,\dots,k$}
 {
 \For{$i=0,\dots,k$}
 {

-$s\leftarrow{\textit{XORshift}(n)}$\;
+$s\leftarrow{PRNG_2(n)}$\;

 $x\leftarrow{F_f(s,x)}$\;
 }
 return $x$\;
 \end{small}
 $x\leftarrow{F_f(s,x)}$\;
 }
 return $x$\;
 \end{small}

-\caption{PRNG with chaotic functions}
+\caption{An arbitrary round of $Old~ CI~ PRNG_f(PRNG_1,PRNG_2)$}

 \label{CI Algorithm}
 \end{algorithm}
 
 
 
 
 \label{CI Algorithm}
 \end{algorithm}
 
 
 
 

+This generator is synthesized in Algorithm~\ref{CI Algorithm}.
+It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation   des   IC   chaotiques};
+an integer $b$, ensuring that the number of executed iterations
+between two outputs is at least $b$
+and at most $2b+1$; and an initial configuration $x^0$.
+It returns the new generated configuration $x$.  Internally, it embeds two
+inputted generators $PRNG_i(k), i=1,2$,
+ which must return integers
+uniformly distributed
+into $\llbracket 1 ; k \rrbracket$.
+For instance, these PRNGs can be the \textit{XORshift}~\cite{Marsaglia2003},
+being a category of very fast PRNGs designed by George Marsaglia
+that repeatedly uses the transform of exclusive or (XOR, $\oplus$) on a number
+with a bit shifted version of it. Such a PRNG, which has a period of
+$2^{32}-1=4.29\times10^9$, is summed up in Algorithm~\ref{XORshift}. 
+This XORshift, or any other reasonable PRNG, is used
+in our own generator to compute both the number of iterations between two
+outputs (provided by $PRNG_1$) and the strategy elements ($PRNG_2$).
+
+%This former generator has successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} ones.
+
+

 \begin{algorithm}[h!]
 \begin{small}
 \KwIn{the internal configuration $z$ (a 32-bit word)}
 \begin{algorithm}[h!]
 \begin{small}
 \KwIn{the internal configuration $z$ (a 32-bit word)}


@@ -514,31 +566,94 @@ return $y$\;
 \end{algorithm}
 
 
 \end{algorithm}
 
 

+\subsection{A ``New CI PRNG''}
+
+In order to make the Old CI PRNG usable in practice, we have proposed 
+an adapted version of the chaotic iteration based generator in~\cite{bg10:ip}.
+In this ``New CI PRNG'', we prevent from changing twice a given
+bit between two outputs.
+This new generator is designed by the following process. 
+
+First of all, some chaotic iterations have to be done to generate a sequence 
+$\left(x^n\right)_{n\in\mathds{N}} \in \left(\mathds{B}^{32}\right)^\mathds{N}$ 
+of Boolean vectors, which are the successive states of the iterated system. 
+Some of these vectors will be randomly extracted and our pseudorandom bit 
+flow will be constituted by their components. Such chaotic iterations are 
+realized as follows. Initial state $x^0 \in \mathds{B}^{32}$ is a Boolean 
+vector taken as a seed and chaotic strategy $\left(S^n\right)_{n\in\mathds{N}}\in 
+\llbracket 1, 32 \rrbracket^\mathds{N}$ is
+an \emph{irregular decimation} of $PRNG_2$ sequence, as described in 
+Algorithm~\ref{Chaotic iteration1}.
+
+Then, at each iteration, only the $S^n$-th component of state $x^n$ is 
+updated, as follows: $x_i^n = x_i^{n-1}$ if $i \neq S^n$, else $x_i^n = \overline{x_i^{n-1}}$.
+Such a procedure is equivalent to achieve chaotic iterations with
+the Boolean vectorial negation $f_0$ and some well-chosen strategies.
+Finally, some $x^n$ are selected
+by a sequence $m^n$ as the pseudorandom bit sequence of our generator.
+$(m^n)_{n \in \mathds{N}} \in \mathcal{M}^\mathds{N}$ is computed from $PRNG_1$, where $\mathcal{M}\subset \mathds{N}^*$ is a finite nonempty set of integers.
+
+The basic design procedure of the New CI generator is summarized in Algorithm~\ref{Chaotic iteration1}.
+The internal state is $x$, the output state is $r$. $a$ and $b$ are those computed by the two input
+PRNGs. Lastly, the value $g(a)$ is an integer defined as in Eq.~\ref{Formula}.
+This function must be chosen such that the outputs of the resulted PRNG are uniform in $\llbracket 0, 2^\mathsf{N}-1 \rrbracket$. Function of \eqref{Formula} achieves this
+goal (other candidates and more information can be found in ~\cite{bg10:ip}).

 
 

+\begin{equation}
+\label{Formula}
+m^n = g(y^n)=
+\left\{
+\begin{array}{l}
+0 \text{ if }0 \leqslant{y^n}<{C^0_{32}},\\
+1 \text{ if }{C^0_{32}} \leqslant{y^n}<\sum_{i=0}^1{C^i_{32}},\\
+2 \text{ if }\sum_{i=0}^1{C^i_{32}} \leqslant{y^n}<\sum_{i=0}^2{C^i_{32}},\\
+\vdots~~~~~ ~~\vdots~~~ ~~~~\\
+N \text{ if }\sum_{i=0}^{N-1}{C^i_{32}}\leqslant{y^n}<1.\\
+\end{array}
+\right.
+\end{equation}

 
 

-
-This generator is synthesized in Algorithm~\ref{CI Algorithm}.
-It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation   des   IC   chaotiques};
-an integer $b$, ensuring that the number of executed iterations is at least $b$
-and at most $2b+1$; and an initial configuration $x^0$.
-It returns the new generated configuration $x$.  Internally, it embeds two
-\textit{XORshift}$(k)$ PRNGs~\cite{Marsaglia2003} that return integers
-uniformly distributed
-into $\llbracket 1 ; k \rrbracket$.
-\textit{XORshift} is a category of very fast PRNGs designed by George Marsaglia,
-which repeatedly uses the transform of exclusive or (XOR, $\oplus$) on a number
-with a bit shifted version of it. This PRNG, which has a period of
-$2^{32}-1=4.29\times10^9$, is summed up in Algorithm~\ref{XORshift}. It is used
-in our PRNG to compute the strategy length and the strategy elements.
-
-This former generator has successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} ones.
+\begin{algorithm}
+\textbf{Input:} the internal state $x$ (32 bits)\\
+\textbf{Output:} a state $r$ of 32 bits
+\begin{algorithmic}[1]
+\FOR{$i=0,\dots,N$}
+{
+\STATE$d_i\leftarrow{0}$\;
+}
+\ENDFOR
+\STATE$a\leftarrow{PRNG_1()}$\;
+\STATE$k\leftarrow{g(a)}$\;
+\WHILE{$i=0,\dots,k$}
+
+\STATE$b\leftarrow{PRNG_2()~mod~\mathsf{N}}$\;
+\STATE$S\leftarrow{b}$\;
+    \IF{$d_S=0$}
+    {
+\STATE      $x_S\leftarrow{ \overline{x_S}}$\;
+\STATE      $d_S\leftarrow{1}$\;
+
+    }
+    \ELSIF{$d_S=1$}
+    {
+\STATE      $k\leftarrow{ k+1}$\;
+    }\ENDIF
+\ENDWHILE\\
+\STATE $r\leftarrow{x}$\;
+\STATE return $r$\;
+\medskip
+\caption{An arbitrary round of the new CI generator}
+\label{Chaotic iteration1}
+\end{algorithmic}
+\end{algorithm}
+\end{color}

 
 \subsection{Improving the Speed of the Former Generator}
 
 
 \subsection{Improving the Speed of the Former Generator}
 

-Instead of updating only one cell at each iteration, we can try to choose a
-subset of components and to update them together. Such an attempt leads
-to a kind of merger of the two sequences used in Algorithm 
-\ref{CI Algorithm}. When the updating function is the vectorial negation,
+Instead of updating only one cell at each iteration,\begin{color}{red} we now propose to choose a
+subset of components and to update them together, for speed improvements. Such a proposition leads\end{color}
+to a kind of merger of the two sequences used in Algorithms 
+\ref{CI Algorithm} and \ref{Chaotic iteration1}. When the updating function is the vectorial negation,

 this algorithm can be rewritten as follows:
 
 \begin{equation}
 this algorithm can be rewritten as follows:
 
 \begin{equation}


@@ -579,9 +694,12 @@ than the ones presented in Definition \ref{Def:chaotic iterations} because, inst
 we select a subset of components to change.
 
 
 we select a subset of components to change.
 
 

-Obviously, replacing Algorithm~\ref{CI Algorithm} by 
+Obviously, replacing the previous CI PRNG Algorithms by 

 Equation~\ref{equation Oplus}, which is possible when the iteration function is
 Equation~\ref{equation Oplus}, which is possible when the iteration function is

-the vectorial negation, leads to a speed improvement. However, proofs
+the vectorial negation, leads to a speed improvement 
+(the resulting generator will be referred as ``Xor CI PRNG''
+in what follows).
+However, proofs

 of chaos obtained in~\cite{bg10:ij} have been established
 only for chaotic iterations of the form presented in Definition 
 \ref{Def:chaotic iterations}. The question is now to determine whether the
 of chaos obtained in~\cite{bg10:ij} have been established
 only for chaotic iterations of the form presented in Definition 
 \ref{Def:chaotic iterations}. The question is now to determine whether the


@@ -591,11 +709,11 @@ faster, does not deflate their topological chaos properties.
 \subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations}
 \label{deuxième def}
 Let us consider the discrete dynamical systems in chaotic iterations having 
 \subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations}
 \label{deuxième def}
 Let us consider the discrete dynamical systems in chaotic iterations having 

-the general form:
+the general form: $\forall    n\in     \mathds{N}^{\ast     }$, $  \forall     i\in
+\llbracket1;\mathsf{N}\rrbracket $,

 
 \begin{equation}
 
 \begin{equation}

-\forall    n\in     \mathds{N}^{\ast     },    \forall     i\in
-\llbracket1;\mathsf{N}\rrbracket ,x_i^n=\left\{
+  x_i^n=\left\{

 \begin{array}{ll}
   x_i^{n-1} &  \text{ if  } i \notin \mathcal{S}^n \\
   \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n.
 \begin{array}{ll}
   x_i^{n-1} &  \text{ if  } i \notin \mathcal{S}^n \\
   \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n.


@@ -620,15 +738,13 @@ Let us introduce the following function:
 where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$.
 
 Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function:
 where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$.
 
 Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function:

-%%RAPH : j'ai coupé la dernière ligne en 2, c'est moche
-\begin{equation}
-\begin{array}{lrll}
-F_{f}: & \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} &
-\longrightarrow & \mathds{B}^{\mathsf{N}} \\
-& (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+\right.\\
-&       &             &\left.f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
+$F_{f}:  \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} 
+\longrightarrow \mathds{B}^{\mathsf{N}}$
+\begin{equation*}
+\begin{array}{rll}
+ (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}%

 \end{array}%
 \end{array}%

-\end{equation}%
+\end{equation*}%

 where + and . are the Boolean addition and product operations, and $\overline{x}$ 
 is the negation of the Boolean $x$.
 Consider the phase space:
 where + and . are the Boolean addition and product operations, and $\overline{x}$ 
 is the negation of the Boolean $x$.
 Consider the phase space:


@@ -758,16 +874,16 @@ thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal.
 \noindent As a consequence, the $k+1$ first entries of the strategies of $%
 G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of
 the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $%
 \noindent As a consequence, the $k+1$ first entries of the strategies of $%
 G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of
 the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $%

-10^{-(k+1)}\leqslant \varepsilon $.\bigskip \newline
+10^{-(k+1)}\leqslant \varepsilon $.
+

 In conclusion,
 %%RAPH : ici j'ai rajouté une ligne
 In conclusion,
 %%RAPH : ici j'ai rajouté une ligne

-\begin{flushleft}$$
-\forall \varepsilon >0,\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}%
-,\forall n\geqslant N_{0},$$
-$$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right)
+$
+\forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}
+,$ $\forall n\geqslant N_{0},$
+$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right)

 \leqslant \varepsilon .
 \leqslant \varepsilon .

-$$
-\end{flushleft}
+$

 $G_{f}$ is consequently continuous.
 \end{proof}
 
 $G_{f}$ is consequently continuous.
 \end{proof}
 


@@ -807,7 +923,7 @@ where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties
 claimed in the lemma.
 \end{proof}
 
 claimed in the lemma.
 \end{proof}
 

-We can now prove Theorem~\ref{t:chaos des general}...
+We can now prove the Theorem~\ref{t:chaos des general}.

 
 \begin{proof}[Theorem~\ref{t:chaos des general}]
 Firstly, strong transitivity implies transitivity.
 
 \begin{proof}[Theorem~\ref{t:chaos des general}]
 Firstly, strong transitivity implies transitivity.


@@ -836,21 +952,329 @@ have $d((S,E),(\tilde S,E))<\epsilon$.
 \end{proof}
 
 
 \end{proof}
 
 

+\begin{color}{red}
+\section{Statistical Improvements Using Chaotic Iterations}
+
+\label{The generation of pseudorandom sequence}

 
 

-\section{Efficient PRNG based on Chaotic Iterations}
-\label{sec:efficient PRNG}

 
 

-Based on the proof presented in the previous section, it is now possible to 
-improve the speed of the generator formerly presented in~\cite{bgw09:ip,guyeux10}. 
-The first idea is to consider
-that the provided strategy is a pseudorandom Boolean vector obtained by a
-given PRNG.
-An iteration of the system is simply the bitwise exclusive or between
-the last computed state and the current strategy.
-Topological properties of disorder exhibited by chaotic 
-iterations can be inherited by the inputted generator, we hope by doing so to 
-obtain some statistical improvements while preserving speed.
+Let us now explain why we are reasonable grounds to believe that chaos 
+can improve statistical properties.
+We will show in this section that chaotic properties as defined in the
+mathematical theory of chaos are related to some statistical tests that can be found
+in the NIST battery. Furthermore, we will check that, when mixing defective PRNGs with
+chaotic iterations, the new generator presents better statistical properties
+(this section summarizes and extends the work of~\cite{bfg12a:ip}).

 
 

+
+
+\subsection{Qualitative relations between topological properties and statistical tests}
+
+
+There are various relations between topological properties that describe an unpredictable behavior for a discrete 
+dynamical system on the one
+hand, and statistical tests to check the randomness of a numerical sequence
+on the other hand. These two mathematical disciplines follow a similar 
+objective in case of a recurrent sequence (to characterize an intrinsically complicated behavior for a
+recurrent sequence), with two different but complementary approaches.
+It is true that these illustrative links give only qualitative arguments, 
+and proofs should be provided later to make such arguments irrefutable. However 
+they give a first understanding of the reason why we think that chaotic properties should tend
+to improve the statistical quality of PRNGs.
+
+Let us now list some of these relations between topological properties defined in the mathematical
+theory of chaos and tests embedded into the NIST battery. Such relations need to be further 
+investigated, but they presently give a first illustration of a trend to search similar properties in the 
+two following fields: mathematical chaos and statistics.
+
+
+\begin{itemize}
+    \item \textbf{Regularity}. As stated in Section~\ref{subsec:Devaney}, a chaotic dynamical system must 
+have an element of regularity. Depending on the chosen definition of chaos, this element can be the existence of
+a dense orbit, the density of periodic points, etc. The key idea is that a dynamical system with no periodicity
+is not as chaotic as a system having periodic orbits: in the first situation, we can predict something and gain a
+knowledge about the behavior of the system, that is, it never enter into a loop. A similar importance for regularity is emphasized in
+the two following tests~\cite{Nist10}:
+    \begin{itemize}
+        \item \textbf{Non-overlapping Template Matching Test}. Detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern.
+        \item \textbf{Discrete Fourier Transform (Spectral) Test}. Detect periodic features (i.e., repetitive patterns that are near each other) in the tested sequence that would indicate a deviation from the assumption of randomness.
+    \end{itemize}
+
+\item \textbf{Transitivity}. This topological property introduced previously states that the dynamical system is intrinsically complicated: it cannot be simplified into 
+two subsystems that do not interact, as we can find in any neighborhood of any point another point whose orbit visits the whole phase space. 
+This focus on the places visited by orbits of the dynamical system takes various nonequivalent formulations in the mathematical theory
+of chaos, namely: transitivity, strong transitivity, total transitivity, topological mixing, and so on~\cite{bg10:ij}. A similar attention 
+is brought on stated visited during a random walk in the two tests below~\cite{Nist10}:
+    \begin{itemize}
+        \item \textbf{Random Excursions Variant Test}. Detect deviations from the expected number of visits to various states in the random walk.
+        \item \textbf{Random Excursions Test}. Determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence.
+    \end{itemize}
+
+\item \textbf{Chaos according to Li and Yorke}. Two points of the phase space $(x,y)$ define a couple of Li-Yorke when $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0$, meaning that their orbits always oscillates as the iterations pass. When a system is compact and contains an uncountable set of such points, it is claimed as chaotic according
+to Li-Yorke~\cite{Li75,Ruette2001}. This property is related to the following test~\cite{Nist10}.
+    \begin{itemize}
+        \item \textbf{Runs Test}. To determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow.
+    \end{itemize}
+    \item \textbf{Topological entropy}. Both in topological and statistical fields.
+    \begin{itemize}
+\item \textbf{Approximate Entropy Test}. Compare the frequency of overlapping blocks of two consecutive/adjacent lengths (m and m+1) against the expected result for a random sequence (m is the length of each block).
+    \end{itemize}
+
+    \item \textbf{Non-linearity, complexity}.
+    \begin{itemize}
+\item \textbf{Binary Matrix Rank Test}. Check for linear dependence among fixed length substrings of the original sequence.
+\item \textbf{Linear Complexity Test}. Determine whether or not the sequence is complex enough to be considered random (M is the length in bits of a block).
+      \end{itemize}
+\end{itemize}
+
+
+
+
+
+\subsection{Details of some Existing Generators}
+
+The list of defective PRNGs we will use 
+as inputs for the statistical tests to come is introduced here.
+
+Firstly, the simple linear congruency generators (LCGs) will be used. 
+They are defined by the following recurrence:
+\begin{equation}
+x^n = (ax^{n-1} + c)~mod~m,
+\label{LCG}
+\end{equation}
+where $a$, $c$, and $x^0$ must be, among other things, non-negative and less than 
+$m$~\cite{LEcuyerS07}. In what follows, 2LCGs and 3LCGs refer as two (resp. three) 
+combinations of such LCGs. For further details, see~\cite{bfg12a:ip,combined_lcg}.
+
+Secondly, the multiple recursive generators (MRGs) will be used, which
+are based on a linear recurrence of order 
+$k$, modulo $m$~\cite{LEcuyerS07}:
+\begin{equation}
+x^n = (a^1x^{n-1}+~...~+a^kx^{n-k})~mod~m .
+\label{MRG}
+\end{equation}
+Combination of two MRGs (referred as 2MRGs) is also used in these experiments.
+
+Generators based on linear recurrences with carry will be regarded too.
+This family of generators includes the add-with-carry (AWC) generator, based on the recurrence:
+\begin{equation}
+\label{AWC}
+\begin{array}{l}
+x^n = (x^{n-r} + x^{n-s} + c^{n-1})~mod~m, \\
+c^n= (x^{n-r} + x^{n-s} + c^{n-1}) / m, \end{array}\end{equation}
+the SWB generator, having the recurrence:
+\begin{equation}
+\label{SWB}
+\begin{array}{l}
+x^n = (x^{n-r} - x^{n-s} - c^{n-1})~mod~m, \\
+c^n=\left\{
+\begin{array}{l}
+1 ~~~~~\text{if}~ (x^{i-r} - x^{i-s} - c^{i-1})<0\\
+0 ~~~~~\text{else},\end{array} \right. \end{array}\end{equation}
+and the SWC generator designed by R. Couture, which is based on the following recurrence:
+\begin{equation}
+\label{SWC}
+\begin{array}{l}
+x^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ mod ~ 2^w, \\
+c^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ / ~ 2^w. \end{array}\end{equation}
+
+Then the generalized feedback shift register (GFSR) generator has been implemented, that is:
+\begin{equation}
+x^n = x^{n-r} \oplus x^{n-k} .
+\label{GFSR}
+\end{equation}
+
+
+Finally, the nonlinear inversive (INV) generator~\cite{LEcuyerS07} has been studied, which is:
+
+\begin{equation}
+\label{INV}
+\begin{array}{l}
+x^n=\left\{
+\begin{array}{ll}
+(a^1 + a^2 / z^{n-1})~mod~m & \text{if}~ z^{n-1} \neq 0 \\
+a^1 & \text{if}~  z^{n-1} = 0 .\end{array} \right. \end{array}\end{equation}
+
+
+
+\begin{table}
+\renewcommand{\arraystretch}{1.3}
+\caption{TestU01 Statistical Test}
+\label{TestU011}
+\centering
+  \begin{tabular}{lccccc}
+    \toprule
+Test name &Tests& Logistic             & XORshift      & ISAAC\\
+Rabbit                                 &       38      &21             &14     &0       \\
+Alphabit                       &       17      &16             &9      &0       \\
+Pseudo DieHARD                         &126    &0              &2      &0      \\
+FIPS\_140\_2                   &16     &0              &0      &0      \\
+SmallCrush                     &15     &4              &5      &0       \\
+Crush                          &144    &95             &57     &0       \\
+Big Crush                      &160    &125            &55     &0       \\ \hline
+Failures               &       &261            &146    &0       \\
+\bottomrule
+  \end{tabular}
+\end{table}
+
+
+
+\begin{table}
+\renewcommand{\arraystretch}{1.3}
+\caption{TestU01 Statistical Test for Old CI algorithms ($\mathsf{N}=4$)}
+\label{TestU01 for Old CI}
+\centering
+  \begin{tabular}{lcccc}
+    \toprule
+\multirow{3}*{Test name} & \multicolumn{4}{c}{Old CI}\\
+&Logistic& XORshift& ISAAC&ISAAC  \\ 
+&+& +& + & + \\ 
+&Logistic& XORshift& XORshift&ISAAC  \\ \cmidrule(r){2-5}
+Rabbit                                         &7      &2      &0      &0       \\
+Alphabit                               & 3     &0      &0      &0       \\
+DieHARD                        &0      &0      &0      &0      \\
+FIPS\_140\_2                   &0      &0      &0      &0      \\
+SmallCrush                             &2      &0      &0      &0       \\
+Crush                                  &47     &4      &0      &0       \\
+Big Crush                              &79     &3      &0      &0       \\ \hline
+Failures                               &138    &9      &0      &0       \\
+\bottomrule
+  \end{tabular}
+\end{table}
+
+
+
+
+
+\subsection{Statistical tests}
+\label{Security analysis}
+
+Three batteries of tests are reputed and usually used
+to evaluate the statistical properties of newly designed pseudorandom
+number generators. These batteries are named DieHard~\cite{Marsaglia1996},
+the NIST suite~\cite{ANDREW2008}, and the most stringent one called
+TestU01~\cite{LEcuyerS07}, which encompasses the two other batteries.
+
+
+
+\label{Results and discussion}
+\begin{table*}
+\renewcommand{\arraystretch}{1.3}
+\caption{NIST and DieHARD tests suite passing rates for PRNGs without CI}
+\label{NIST and DieHARD tests suite passing rate the for PRNGs without CI}
+\centering
+  \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|}
+    \hline\hline
+Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline
+\backslashbox{\textbf{$Tests$}} {\textbf{$PRNG$}} & LCG& MRG& AWC & SWB  & SWC & GFSR & INV & LCG2& LCG3& MRG2 \\ \hline
+NIST & 11/15 & 14/15 &\textbf{15/15} & \textbf{15/15}   & 14/15 & 14/15  & 14/15 & 14/15& 14/15& 14/15 \\ \hline
+DieHARD & 16/18 & 16/18 & 15/18 & 16/18 & \textbf{18/18} & 16/18 & 16/18 & 16/18& 16/18& 16/18\\ \hline
+\end{tabular}
+\end{table*}
+
+Table~\ref{NIST and DieHARD tests suite passing rate the for PRNGs without CI} shows the 
+results on the two firsts batteries recalled above, indicating that all the PRNGs presented
+in the previous section
+cannot pass all these tests. In other words, the statistical quality of these PRNGs cannot 
+fulfill the up-to-date standards presented previously. We have shown in~\cite{bfg12a:ip} that the use of chaotic
+iterations can solve this issue.
+%More precisely, to
+%illustrate the effects of chaotic iterations on these defective PRNGs, experiments have been divided in three parts~\cite{bfg12a:ip}:
+%\begin{enumerate}
+%  \item \textbf{Single CIPRNG}: The PRNGs involved in CI computing are of the same category.
+%  \item \textbf{Mixed CIPRNG}: Two different types of PRNGs are mixed during the chaotic iterations process.
+%  \item \textbf{Multiple CIPRNG}: The generator is obtained by repeating the composition of the iteration function as follows: $x^0\in \mathds{B}^{\mathsf{N}}$, and $\forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket, x_i^n=$
+%\begin{equation}
+%\begin{array}{l}
+%\left\{
+%\begin{array}{l}
+%x_i^{n-1}~~~~~\text{if}~S^n\neq i \\
+%\forall j\in \llbracket1;\mathsf{m}\rrbracket,f^m(x^{n-1})_{S^{nm+j}}~\text{if}~S^{nm+j}=i.\end{array} \right. \end{array}
+%\end{equation}
+%$m$ is called the \emph{functional power}.
+%\end{enumerate}
+%
+The obtained results are reproduced in Table
+\ref{NIST and DieHARD tests suite passing rate the for single CIPRNGs}.
+The scores written in boldface indicate that all the tests have been passed successfully, whereas an 
+asterisk ``*'' means that the considered passing rate has been improved.
+The improvements are obvious for both the ``Old CI'' and ``New CI'' generators.
+Concerning the ``Xor CI PRNG'', the score is less spectacular: a large speed improvement makes that statistics
+ are not as good as for the two other versions of these CIPRNGs.
+However 8 tests have been improved (with no deflation for the other results).
+
+
+\begin{table*}
+\renewcommand{\arraystretch}{1.3}
+\caption{NIST and DieHARD tests suite passing rates for PRNGs with CI}
+\label{NIST and DieHARD tests suite passing rate the for single CIPRNGs}
+\centering
+  \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|}
+    \hline
+Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline
+\backslashbox{\textbf{$Tests$}} {\textbf{$Single~CIPRNG$}} & LCG  & MRG & AWC & SWB & SWC & GFSR & INV& LCG2 & LCG3& MRG2 \\ \hline\hline
+Old CIPRNG\\ \hline \hline
+NIST & \textbf{15/15} *  & \textbf{15/15} * & \textbf{15/15}   & \textbf{15/15}   & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline
+DieHARD & \textbf{18/18} *  & \textbf{18/18} * & \textbf{18/18} *  & \textbf{18/18} *  & \textbf{18/18}  & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * \\ \hline
+New CIPRNG\\ \hline \hline
+NIST & \textbf{15/15} *  & \textbf{15/15} * & \textbf{15/15}   & \textbf{15/15}  & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline
+DieHARD & \textbf{18/18} *  & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18}  & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} *\\ \hline
+Xor CIPRNG\\ \hline\hline
+NIST & 14/15*& \textbf{15/15} *   & \textbf{15/15}   & \textbf{15/15}   & 14/15 & \textbf{15/15} * & 14/15& \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15}  \\ \hline
+DieHARD & 16/18 & 16/18 & 17/18* & \textbf{18/18} * & \textbf{18/18}  & \textbf{18/18} * & 16/18 & 16/18 & 16/18& 16/18\\ \hline
+\end{tabular}
+\end{table*}
+
+
+We have then investigate in~\cite{bfg12a:ip} if it is possible to improve
+the statistical behavior of the Xor CI version by combining more than one 
+$\oplus$ operation. Results are summarized in Table~\ref{threshold}, illustrating
+the progressive increasing effects of chaotic iterations, when giving time to chaos to get settled in.
+Thus rapid and perfect PRNGs, regarding the NIST and DieHARD batteries, can be obtained 
+using chaotic iterations on defective generators.
+
+\begin{table*}
+\renewcommand{\arraystretch}{1.3}
+\caption{Number of $\oplus$ operations to pass the whole NIST and DieHARD batteries}
+\label{threshold}
+\centering
+  \begin{tabular}{|l||c|c|c|c|c|c|c|c|}
+    \hline
+Inputted $PRNG$ & LCG & MRG & SWC & GFSR & INV& LCG2 & LCG3  & MRG2 \\ \hline\hline
+Threshold  value $m$& 19 & 7  & 2& 1 & 11& 9& 3& 4\\ \hline\hline
+\end{tabular}
+\end{table*}
+
+Finally, the TestU01 battery has been launched on three well-known generators 
+(a logistic map, a simple XORshift, and the cryptographically secure ISAAC, 
+see Table~\ref{TestU011}). These results can be compared with 
+Table~\ref{TestU01 for Old CI}, which gives the scores obtained by the
+Old CI PRNG that has received these generators.
+The obvious improvement speaks for itself, and together with the other
+results recalled in this section, it reinforces the opinion that a strong
+correlation between topological properties and statistical behavior exists.
+
+
+Next subsection will now give a concrete original implementation of the Xor CI PRNG, the
+fastest generator in the chaotic iteration based family. In the remainder,
+this generator will be simply referred as CIPRNG, or ``the proposed PRNG'', if this statement does not
+raise ambiguity.
+\end{color}
+
+\subsection{Efficient Implementation of a PRNG based on Chaotic Iterations}
+\label{sec:efficient PRNG}
+%
+%Based on the proof presented in the previous section, it is now possible to 
+%improve the speed of the generator formerly presented in~\cite{bgw09:ip,guyeux10}. 
+%The first idea is to consider
+%that the provided strategy is a pseudorandom Boolean vector obtained by a
+%given PRNG.
+%An iteration of the system is simply the bitwise exclusive or between
+%the last computed state and the current strategy.
+%Topological properties of disorder exhibited by chaotic 
+%iterations can be inherited by the inputted generator, we hope by doing so to 
+%obtain some statistical improvements while preserving speed.
+%

 %%RAPH : j'ai viré tout ca
 %% Let us give an example using 16-bits numbers, to clearly understand how the bitwise xor operations
 %% are
 %%RAPH : j'ai viré tout ca
 %% Let us give an example using 16-bits numbers, to clearly understand how the bitwise xor operations
 %% are


@@ -882,7 +1306,7 @@ obtain some statistical improvements while preserving speed.
 
 
 
 
 
 

-\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iterations},label=algo:seqCIPRNG}
+\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iterations},label={algo:seqCIPRNG}}

 \begin{small}
 \begin{lstlisting}
 
 \begin{small}
 \begin{lstlisting}
 


@@ -1232,8 +1656,10 @@ $y\bigoplus_{i=1}^{i=j} w_i^\prime=y\bigoplus_{i=1}^{i=j} w_i$. It follows,
 by a direct induction, that $w_i=w_i^\prime$. Furthermore, since $\mathbb{B}^{kN}$
 is finite, each $\varphi_y$ is bijective. Therefore, and using (\ref{PCH-1}),
 one has
 by a direct induction, that $w_i=w_i^\prime$. Furthermore, since $\mathbb{B}^{kN}$
 is finite, each $\varphi_y$ is bijective. Therefore, and using (\ref{PCH-1}),
 one has

+$\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]$ and,
+therefore, 

 \begin{equation}\label{PCH-2}
 \begin{equation}\label{PCH-2}

-\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]=\mathrm{Pr}[D(U_{kN})=1].
+\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(U_{kN})=1].

 \end{equation}
 
 Now, using (\ref{PCH-1}) again, one has  for every $x$,
 \end{equation}
 
 Now, using (\ref{PCH-1}) again, one has  for every $x$,


@@ -1269,7 +1695,7 @@ It is  possible to build a  cryptographically secure PRNG based  on the previous
 algorithm (Algorithm~\ref{algo:gpu_kernel2}).   Due to Proposition~\ref{cryptopreuve},
 it simply consists  in replacing
 the  {\it  xor-like} PRNG  by  a  cryptographically  secure one.  
 algorithm (Algorithm~\ref{algo:gpu_kernel2}).   Due to Proposition~\ref{cryptopreuve},
 it simply consists  in replacing
 the  {\it  xor-like} PRNG  by  a  cryptographically  secure one.  

-We have chosen the Blum Blum Shum generator~\cite{BBS} (usually denoted by BBS) having the form:
+We have chosen the Blum Blum Shub generator~\cite{BBS} (usually denoted by BBS) having the form:

 $$x_{n+1}=x_n^2~ mod~ M$$  where $M$ is the product of  two prime numbers (these
 prime numbers  need to be congruent  to 3 modulus  4). BBS is known to be
 very slow and only usable for cryptographic applications. 
 $$x_{n+1}=x_n^2~ mod~ M$$  where $M$ is the product of  two prime numbers (these
 prime numbers  need to be congruent  to 3 modulus  4). BBS is known to be
 very slow and only usable for cryptographic applications. 


@@ -1388,6 +1814,41 @@ secure.
 
 
 
 
 
 

+\begin{color}{red}
+\subsection{Practical Security Evaluation}
+\label{sec:Practicak evaluation}
+
+Suppose now that the PRNG will work during 
+$M=100$ time units, and that during this period,
+an attacker can realize $10^{12}$ clock cycles.
+We thus wonder whether, during the PRNG's 
+lifetime, the attacker can distinguish this 
+sequence from truly random one, with a probability
+greater than $\varepsilon = 0.2$.
+We consider that $N$ has 900 bits.
+
+The random process is the BBS generator, which
+is cryptographically secure. More precisely, it
+is $(T,\varepsilon)-$secure: no 
+$(T,\varepsilon)-$distinguishing attack can be
+successfully realized on this PRNG, if~\cite{Fischlin}
+$$
+T \leqslant \dfrac{L(N)}{6 N (log_2(N))\varepsilon^{-2}M^2}-2^7 N \varepsilon^{-2} M^2 log_2 (8 N \varepsilon^{-1}M)
+$$
+where $M$ is the length of the output ($M=100$ in
+our example), and $L(N)$ is equal to
+$$
+2.8\times 10^{-3} exp \left(1.9229 \times (N ~ln(2)^\frac{1}{3}) \times ln(N~ln 2)^\frac{2}{3}\right)
+$$
+is the number of clock cycles to factor a $N-$bit
+integer.
+
+A direct numerical application shows that this attacker 
+cannot achieve its $(10^{12},0.2)$ distinguishing
+attack in that context.
+
+\end{color}
+

 \subsection{Toward a Cryptographically Secure and Chaotic Asymmetric Cryptosystem}
 \label{Blum-Goldwasser}
 We finish this research work by giving some thoughts about the use of
 \subsection{Toward a Cryptographically Secure and Chaotic Asymmetric Cryptosystem}
 \label{Blum-Goldwasser}
 We finish this research work by giving some thoughts about the use of


@@ -1470,10 +1931,10 @@ namely the BigCrush.
 Furthermore, we have shown that when the inputted generator is cryptographically
 secure, then it is the case too for the PRNG we propose, thus leading to
 the possibility to develop fast and secure PRNGs using the GPU architecture.
 Furthermore, we have shown that when the inputted generator is cryptographically
 secure, then it is the case too for the PRNG we propose, thus leading to
 the possibility to develop fast and secure PRNGs using the GPU architecture.

-Thoughts about an improvement of the Blum-Goldwasser cryptosystem, using the 
-proposed method, has been finally proposed.
+\begin{color}{red} An improvement of the Blum-Goldwasser cryptosystem, making it 
+behaves chaotically, has finally been proposed. \end{color}

 
 

-In future  work we plan to extend these researches, building a parallel PRNG for  clusters or
+In future  work we plan to extend this research, building a parallel PRNG for  clusters or

 grid computing. Topological properties of the various proposed generators will be investigated,
 and the use of other categories of PRNGs as input will be studied too. The improvement
 of Blum-Goldwasser will be deepened. Finally, we
 grid computing. Topological properties of the various proposed generators will be investigated,
 and the use of other categories of PRNGs as input will be studied too. The improvement
 of Blum-Goldwasser will be deepened. Finally, we