\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}
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
{\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}.
-
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
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}.
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 Shub
-in Section~\ref{sec:CSGPU}, and to an improvement of the
+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.
-\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
\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
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.
+
\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$}
{
-$s\leftarrow{\textit{XORshift}(n)}$\;
+$s\leftarrow{PRNG_2(n)}$\;
$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}
+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)}
\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 is 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}
-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}
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
-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
\end{proof}
+\begin{color}{red}
+\section{Statistical Improvements Using Chaotic Iterations}
-\section{Efficient PRNG based on Chaotic Iterations}
-\label{sec:efficient PRNG}
+\label{The generation of pseudorandom sequence}
+
+
+Let us now explain why we are reasonable grounds to believe that chaos
+can improve statistical properties.
+We will show in this section that, when mixing defective PRNGs with
+chaotic iterations, the result presents better statistical properties
+(this section summarizes the work of~\cite{bfg12a:ip}).
+
+\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 generator (LCGs) will be used.
+It is 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 too, 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 experimentations.
+
+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}
-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.
+Finally, the nonlinear inversive generator~\cite{LEcuyerS07} has been regarded too, 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 speed improvement makes that statistical
+results are not as good as for the two other versions of these CIPRNGs.
+
+
+\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~\ref{threshold}, showing
+that 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 as 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.
+
+
+Next subsection gives a concrete implementation of this Xor CI PRNG, which will
+new be simply called 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
-\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{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,
