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}.
-Chaos, for its part, refers to the well-established definition of a
-chaotic dynamical system proposed by Devaney~\cite{Devaney}.
\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
+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
+ 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
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
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 pseudo-random bit
+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
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 pseudo-random bit sequence of our generator.
+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 is required to make the outputs uniform in $\llbracket 0, 2^\mathsf{N}-1 \rrbracket$
-(the reader is referred to~\cite{bg10:ip} for more information).
+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}
}
\ENDFOR
\STATE$a\leftarrow{PRNG_1()}$\;
-\STATE$m\leftarrow{g(a)}$\;
-\STATE$k\leftarrow{m}$\;
+\STATE$k\leftarrow{g(a)}$\;
\WHILE{$i=0,\dots,k$}
\STATE$b\leftarrow{PRNG_2()~mod~\mathsf{N}}$\;
\forall n \in \mathds{N}^*, x^n = x^{n-1} \oplus S^n,
\end{array}
\right.
-\label{equation Oplus0}
+\label{equation Oplus}
\end{equation}
where $\oplus$ is for the bitwise exclusive or between two integers.
This rewriting can be understood as follows. The $n-$th term $S^n$ of the
component of this state (a binary digit) changes if and only if the $k-$th
digit in the binary decomposition of $S^n$ is 1.
-The single basic component presented in Eq.~\ref{equation Oplus0} is of
+The single basic component presented in Eq.~\ref{equation Oplus} is of
ordinary use as a good elementary brick in various PRNGs. It corresponds
to the following discrete dynamical system in chaotic iterations:
Obviously, replacing the previous CI PRNG Algorithms by
-Equation~\ref{equation Oplus0}, 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
(the resulting generator will be referred as ``Xor CI PRNG''
in what follows).
\begin{color}{red}
\section{Statistical Improvements Using Chaotic Iterations}
-\label{The generation of pseudo-random sequence}
+\label{The generation of pseudorandom sequence}
Let us now explain why we are reasonable grounds to believe that chaos
-\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,
