avancées dans la réécriture

diff --git a/prng_gpu.tex b/prng_gpu.tex
index c7853b230ce4ab04aab4605b483b5b54a42afeb7..0c9f9c742e91de13b4286de29106cf7a76abfa8f 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -90,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


@@ -124,18 +130,18 @@ 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}.

-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
 \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
 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}
 [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
 
 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


@@ -166,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}.


@@ -176,7 +187,8 @@ 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 Shub
 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.
 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.


@@ -184,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


@@ -584,8 +596,8 @@ $(m^n)_{n \in \mathds{N}} \in \mathcal{M}^\mathds{N}$ is computed from $PRNG_1$,
 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}.
 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}
 
 \begin{equation}
 \label{Formula}


@@ -651,7 +663,7 @@ x^0 \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket, S \in \llbracket 0, 2^\mathsf{N
 \forall n \in \mathds{N}^*, x^n = x^{n-1} \oplus S^n,
 \end{array}
 \right.
 \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
 \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


@@ -661,7 +673,7 @@ as an integer having $\mathsf{N}$ bits too). More precisely, the $k-$th
 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.
 
 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:
 
 ordinary use as a good elementary brick in various PRNGs. It corresponds
 to the following discrete dynamical system in chaotic iterations:
 


@@ -683,7 +695,7 @@ we select a subset of components to change.
 
 
 Obviously, replacing the previous CI PRNG Algorithms by 
 
 
 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).
 the vectorial negation, leads to a speed improvement 
 (the resulting generator will be referred as ``Xor CI PRNG''
 in what follows).


@@ -1221,7 +1233,7 @@ raise ambiguity.
 
 
 
 
 
 

-\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}
 


@@ -1731,6 +1743,7 @@ secure.
 
 \begin{color}{red}
 \subsection{Practical Security Evaluation}
 
 \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,
 
 Suppose now that the PRNG will work during 
 $M=100$ time units, and that during this period,