Fin des travaux sur l'article

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 34ec700d4874d7fa276a8ee5e0a1002e61fa25f7..215675289e7c624b1f4e6b1dba8b717b424f8bd1 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}


@@ -35,6 +40,9 @@
 
 \newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}}
 
 
 \newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}}
 

+
+\newcommand{\PCH}[1]{\begin{color}{blue}#1\end{color}}
+

 \title{Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom Numbers on GPU}
 \begin{document}
 
 \title{Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom Numbers on GPU}
 \begin{document}
 


@@ -85,7 +93,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 +133,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


@@ -146,23 +169,49 @@ property.
 Last, but not least, we propose a rewriting of the Blum-Goldwasser asymmetric
 key encryption protocol by using the proposed method.
 
 Last, but not least, we propose a rewriting of the Blum-Goldwasser asymmetric
 key encryption protocol by using the proposed method.
 

+
+\PCH{
+{\bf Main contributions.} In this paper a new PRNG using chaotic iteration
+is defined. From a theoretical point of view, it is proved that it has fine
+topological chaotic properties and that it is cryptographically secured (when
+the based PRNG is also cryptographically secured). From a practical point of
+view, experiments point out a very good statistical behavior. Optimized
+original implementation of this PRNG are also proposed and experimented.
+Pseudo-random numbers are generated at a rate of 20GSamples/s which is faster
+than in~\cite{conf/fpga/ThomasHL09,Marsaglia2003} (and with a better
+statistical behavior). Experiments are also provided using BBS as the based
+random generator. The generation speed is significantly weaker but, as far
+as we know, it is the first cryptographically secured PRNG proposed on GPU.
+Note too that an original qualitative comparison between topological chaotic
+properties and statistical test is also proposed.
+}
+
+
+

 The remainder of this paper  is organized as follows. In Section~\ref{section:related
   works} we  review some GPU implementations  of PRNGs.  Section~\ref{section:BASIC
   RECALLS} gives some basic recalls  on the well-known Devaney's formulation of chaos, 
   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}.
 The remainder of this paper  is organized as follows. In Section~\ref{section:related
   works} we  review some GPU implementations  of PRNGs.  Section~\ref{section:BASIC
   RECALLS} gives some basic recalls  on the well-known Devaney's formulation of chaos, 
   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}.
 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.
   gpu}   describes and evaluates theoretically  the  GPU   implementation. 
 Such generators are experimented in 
 Section~\ref{sec:experiments}.
 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.

+\begin{color}{red} A practical
+security evaluation is also outlined in Section~\ref{sec:Practicak evaluation}.\end{color}

 Such a proof leads to the proposition of a cryptographically secure and
 chaotic generator on GPU based on the famous Blum Blum Shub
 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} 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 +219,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


@@ -229,7 +278,7 @@ with basic notions on topology (see for instance~\cite{Devaney}).
 
 
 \subsection{Devaney's Chaotic Dynamical Systems}
 
 
 \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


@@ -416,7 +465,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


@@ -473,33 +522,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)}


@@ -515,31 +589,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}


@@ -580,9 +717,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


@@ -761,6 +901,8 @@ the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $%
 
 In conclusion,
 %%RAPH : ici j'ai rajouté une ligne
 
 In conclusion,
 %%RAPH : ici j'ai rajouté une ligne

+%%TOF : ici j'ai rajouté un commentaire
+%%TOF : ici aussi

 $
 \forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}
 ,$ $\forall n\geqslant N_{0},$
 $
 \forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}
 ,$ $\forall n\geqslant N_{0},$


@@ -835,21 +977,345 @@ 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}
+
+
+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}).
+

 
 

-\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.
+\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 the following 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 enters into a loop. A similar importance for periodicity is emphasized in
+the two following NIST 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 states 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}. A similar property is regarded in the following NIST 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}. The desire to formulate an equivalency of the thermodynamics entropy
+has emerged both in the topological and statistical fields. Another time, a similar objective has led to two different
+rewritten of an entropy based disorder: the famous Shannon definition of entropy is approximated in the statistical approach, 
+whereas topological entropy is defined as follows.
+$x,y \in \mathcal{X}$ are $\varepsilon-$\emph{separated in time $n$} if there exists $k \leqslant n$ such that $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$. Then $(n,\varepsilon)-$separated sets are sets of points that are all $\varepsilon-$separated in time $n$, which
+leads to the definition of $s_n(\varepsilon,Y)$, being the maximal cardinality of all $(n,\varepsilon)-$separated sets. Using these notations, 
+the topological entropy is defined as follows: $$h_{top}(\mathcal{X},f)  = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}.$$
+This value measures the average exponential growth of the number of distinguishable orbit segments. 
+In this sense, it measures complexity of the topological dynamical system, whereas 
+the Shannon approach is in mind when defining the following test~\cite{Nist10}:
+    \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.
+    \end{itemize}
+
+    \item \textbf{Non-linearity, complexity}. Finally, let us remark that non-linearity and complexity are 
+not only sought in general to obtain chaos, but they are also required for randomness, as illustrated by the two tests below~\cite{Nist10}.
+    \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.
+      \end{itemize}
+\end{itemize}

 
 

+
+We have proven in our previous works~\cite{guyeux12:bc} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation   des   IC   chaotiques} are, among other
+things, strongly transitive, topologically mixing, chaotic as defined by Li and Yorke,
+and that they have a topological entropy and an exponent of Lyapunov both equal to $ln(\mathsf{N})$,
+where $\mathsf{N}$ is the size of the iterated vector.
+These topological properties make that we are ground to believe that a generator based on chaotic
+iterations will probably be able to pass all the existing statistical batteries for pseudorandomness like
+the NIST one. The following subsections, in which we prove that defective generators have their
+statistical properties improved by chaotic iterations, show that such an assumption is true.
+
+\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{First 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


@@ -881,7 +1347,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}
 


@@ -915,7 +1381,13 @@ works with 32-bits, we use the command \texttt{(unsigned int)}, that selects the
 
 Thus producing a pseudorandom number needs 6 xor operations with 6 32-bits numbers
 that  are provided by  3 64-bits  PRNGs.  This  version successfully  passes the
 
 Thus producing a pseudorandom number needs 6 xor operations with 6 32-bits numbers
 that  are provided by  3 64-bits  PRNGs.  This  version successfully  passes the

-stringent BigCrush battery of tests~\cite{LEcuyerS07}.
+stringent BigCrush battery of tests~\cite{LEcuyerS07}. 
+\begin{color}{red}At this point, we thus
+have defined an efficient and statistically unbiased generator. Its speed is
+directly related to the use of linear operations, but for the same reason,
+this fast generator cannot be proven as secure.
+\end{color}
+

 
 \section{Efficient PRNGs based on Chaotic Iterations on GPU}
 \label{sec:efficient PRNG gpu}
 
 \section{Efficient PRNGs based on Chaotic Iterations on GPU}
 \label{sec:efficient PRNG gpu}


@@ -1051,7 +1523,9 @@ version\label{IR}}
 \label{algo:gpu_kernel2} 
 \end{algorithm}
 
 \label{algo:gpu_kernel2} 
 \end{algorithm}
 

-\subsection{Theoretical Evaluation of the Improved Version}
+\begin{color}{red}
+\subsection{Chaos Evaluation of the Improved Version}
+\end{color}

 
 A run of Algorithm~\ref{algo:gpu_kernel2} consists in an operation ($x=x\oplus t$) having 
 the form of Equation~\ref{equation Oplus}, which is equivalent to the iterative
 
 A run of Algorithm~\ref{algo:gpu_kernel2} consists in an operation ($x=x\oplus t$) having 
 the form of Equation~\ref{equation Oplus}, which is equivalent to the iterative


@@ -1149,9 +1623,27 @@ as it is shown in the next sections.
 
 
 \section{Security Analysis}
 
 
 \section{Security Analysis}

-\label{sec:security analysis}

 
 
 
 

+\begin{color}{red}
+This section is dedicated to the security analysis of the
+  proposed PRNGs, both from a theoretical and a practical points of view.
+
+\subsection{Theoretical Proof of Security}
+\label{sec:security analysis}
+
+The standard definition
+  of {\it indistinguishability} used is the classical one as defined for
+  instance in~\cite[chapter~3]{Goldreich}. 
+  This property shows that predicting the future results of the PRNG
+  cannot be done in a reasonable time compared to the generation time. It is important to emphasize that this
+  is a relative notion between breaking time and the sizes of the
+  keys/seeds. Of course, if small keys or seeds are chosen, the system can
+  be broken in practice. But it also means that if the keys/seeds are large
+  enough, the system is secured.
+As a complement, an example of a concrete practical evaluation of security
+is outlined in the next subsection.
+\end{color}

 
 In this section the concatenation of two strings $u$ and $v$ is classically
 denoted by $uv$.
 
 In this section the concatenation of two strings $u$ and $v$ is classically
 denoted by $uv$.


@@ -1173,7 +1665,15 @@ internal coin tosses of $D$.
 
 Intuitively, it means that there is no polynomial time algorithm that can
 distinguish a perfect uniform random generator from $G$ with a non
 
 Intuitively, it means that there is no polynomial time algorithm that can
 distinguish a perfect uniform random generator from $G$ with a non

-negligible probability. The interested reader is referred
+negligible probability.
+\begin{color}{red}
+ An equivalent formulation of this well-known 
+security property means that it is possible 
+\emph{in practice} to predict the next bit of
+the generator, knowing all the previously 
+produced ones.
+\end{color}
+The interested reader is referred

 to~\cite[chapter~3]{Goldreich} for more information. Note that it is
 quite easily possible to change the function $\ell$ into any polynomial
 function $\ell^\prime$ satisfying $\ell^\prime(m)>m)$~\cite[Chapter 3.3]{Goldreich}.
 to~\cite[chapter~3]{Goldreich} for more information. Note that it is
 quite easily possible to change the function $\ell$ into any polynomial
 function $\ell^\prime$ satisfying $\ell^\prime(m)>m)$~\cite[Chapter 3.3]{Goldreich}.


@@ -1261,6 +1761,100 @@ proving that $H$ is not secure, which is a contradiction.
 \end{proof}
 
 
 \end{proof}
 
 

+
+\begin{color}{red}
+\subsection{Practical Security Evaluation}
+\label{sec:Practicak evaluation}
+
+Pseudorandom generators based on Eq.~\eqref{equation Oplus} are thus cryptographically secure when
+they are XORed with an already cryptographically
+secure PRNG. But, as stated previously,
+such a property does not mean that, whatever the
+key size, no attacker can predict the next bit
+knowing all the previously released ones.
+However, given a key size, it is possible to 
+measure in practice the minimum duration needed
+for an attacker to break a cryptographically
+secure PRNG, if we know the power of his/her
+machines. Such a concrete security evaluation 
+is related to the $(T,\varepsilon)-$security
+notion, which is recalled and evaluated in what 
+follows, for the sake of completeness.
+
+Let us firstly recall that,
+\begin{definition}
+Let $\mathcal{D} : \mathds{B}^M \longrightarrow \mathds{B}$ be a probabilistic algorithm that runs
+in time $T$. 
+Let $\varepsilon > 0$. 
+$\mathcal{D}$ is called a $(T,\varepsilon)-$distinguishing attack on pseudorandom
+generator $G$ if
+
+\begin{flushleft}
+$\left| Pr[\mathcal{D}(G(k)) = 1 \mid k \in_R \{0,1\}^\ell ]\right.$
+\end{flushleft}
+
+\begin{flushright}
+$ - \left. Pr[\mathcal{D}(s) = 1 \mid s \in_R \mathds{B}^M ]\right| \geqslant \varepsilon,$
+\end{flushright}
+
+\noindent where the probability is taken over the internal coin flips of $\mathcal{D}$, and the notation
+``$\in_R$'' indicates the process of selecting an element at random and uniformly over the
+corresponding set.
+\end{definition}
+
+Let us recall that the running time of a probabilistic algorithm is defined to be the
+maximum of the expected number of steps needed to produce an output, maximized
+over all inputs; the expected number is averaged over all coin flips made by the algorithm~\cite{Knuth97}.
+We are now able to define the notion of cryptographically secure PRNGs:
+
+\begin{definition}
+A pseudorandom generator is $(T,\varepsilon)-$secure if there exists no $(T,\varepsilon)-$distinguishing attack on this pseudorandom generator.
+\end{definition}
+
+
+
+
+
+
+
+Suppose now that the PRNG of Eq.~\eqref{equation Oplus} 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.
+
+Predicting the next generated bit knowing all the
+previously released ones by Eq.~\eqref{equation Oplus} is obviously equivalent to predict the
+next bit in 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}
+\begin{equation}
+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)
+\label{mesureConcrete}
+\end{equation}
+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}
+
+

 \section{Cryptographical Applications}
 
 \subsection{A Cryptographically Secure PRNG for GPU}
 \section{Cryptographical Applications}
 
 \subsection{A Cryptographically Secure PRNG for GPU}


@@ -1384,45 +1978,41 @@ It should  be noticed that this generator has once more the form $x^{n+1} = x^n
 where $S^n$ is referred in this algorithm as $t$: each iteration of this
 PRNG ends with $x = x \wedge t$. This $S^n$ is only constituted
 by secure bits produced by the BBS generator, and thus, due to
 where $S^n$ is referred in this algorithm as $t$: each iteration of this
 PRNG ends with $x = x \wedge t$. This $S^n$ is only constituted
 by secure bits produced by the BBS generator, and thus, due to

-Proposition~\ref{cryptopreuve}, the resulted PRNG is cryptographically
-secure.
-
-
+Proposition~\ref{cryptopreuve}, the resulted PRNG is 
+cryptographically secure.

 
 \begin{color}{red}
 
 \begin{color}{red}

-\subsection{Practical Security 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.
-
+As stated before, even if the proposed PRNG is cryptocaphically
+secure, it does not mean that such a generator
+can be used as described here when attacks are
+awaited. The problem is to determine the minimum 
+time required for an attacker, with a given 
+computational power, to predict under a probability
+lower than 0.5 the $n+1$th bit, knowing the $n$
+previous ones. The proposed GPU generator will be
+useful in a security context, at least in some 
+situations where a secret protected by a pseudorandom
+keystream is rapidly obsolete, if this time to 
+predict the next bit is large enough when compared
+to both the generation and transmission times.
+It is true that the prime numbers used in the last
+section are very small compared to up-to-date 
+security recommends. However the attacker has not
+access to each BBS, but to the output produced 
+by Algorithm~\ref{algo:bbs_gpu}, which is quite
+more complicated than a simple BBS. Indeed, to
+determine if this cryptographically secure PRNG
+on GPU can be useful in security context with the 
+proposed parameters, or if it is only a very fast
+and statistically perfect generator on GPU, its
+$(T,\varepsilon)-$security must be determined, and
+a formulation similar to Eq.\eqref{mesureConcrete}
+must be established. Authors
+hope to achieve to realize this difficult task in a future
+work.

 \end{color}
 
 \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