pch : mise a jour de reponse pour les refs sur le nouveau document + mise à jour...

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 11a1d56bbd4b098c2abc1326113723497a16f7b5..bc0679701ad8ef020723f13e37e4a6a988d5d70d 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -14,6 +14,7 @@
 \usepackage{algorithmic}
 \usepackage{slashbox}
 \usepackage{ctable}
 \usepackage{algorithmic}
 \usepackage{slashbox}
 \usepackage{ctable}

+\usepackage{cite}

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


@@ -54,8 +55,8 @@ Guyeux, and Pierre-Cyrille Héam\thanks{Authors in alphabetic order}}
 \IEEEcompsoctitleabstractindextext{
 \begin{abstract}
 In this paper we present a new pseudorandom number generator (PRNG) on
 \IEEEcompsoctitleabstractindextext{
 \begin{abstract}
 In this paper we present a new pseudorandom number generator (PRNG) on

-graphics processing units  (GPU). This PRNG is based  on the so-called chaotic iterations.  It
-is firstly proven  to be chaotic according to the Devaney's  formulation. We thus propose  an efficient
+graphics processing units  (GPU). This PRNG is based  on the so-called chaotic iterations and
+it is thus chaotic according to the Devaney's  formulation. We propose  an efficient

 implementation  for  GPU that successfully passes the   {\it BigCrush} tests, deemed to be the  hardest
 battery of tests in TestU01.  Experiments show that this PRNG can generate
 about 20 billion of random numbers  per second on Tesla C1060 and NVidia GTX280
 implementation  for  GPU that successfully passes the   {\it BigCrush} tests, deemed to be the  hardest
 battery of tests in TestU01.  Experiments show that this PRNG can generate
 about 20 billion of random numbers  per second on Tesla C1060 and NVidia GTX280


@@ -179,8 +180,8 @@ Pseudorandom 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 initial
 random generator. The generation speed is significantly weaker.
 than in~\cite{conf/fpga/ThomasHL09,Marsaglia2003} (and with a better
 statistical behavior). Experiments are also provided using BBS as the initial
 random generator. The generation speed is significantly weaker.

-Note also that an original qualitative comparison between topological chaotic
-properties and statistical test is also proposed.
+%Note also that an original qualitative comparison between topological chaotic
+%properties and statistical test is also proposed.

 
 
 
 
 
 


@@ -191,12 +192,11 @@ 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{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 
+Section~\ref{sec:efficient PRNG} %{The generation of pseudorandom sequence} %illustrates the statistical
+%improvement related to the chaotic iteration based post-treatment, for
+%our previously released PRNGs and
+ contains a new efficient 

 implementation on CPU.
 implementation on CPU.

-

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


@@ -204,8 +204,8 @@ 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.
 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.

-A practical
-security evaluation is also outlined in Section~\ref{sec:Practicak evaluation}.
+%A practical
+%security evaluation is also outlined in Section~\ref{sec:Practicak evaluation}.

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


@@ -718,17 +718,25 @@ 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 
 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
+\ref{Def:chaotic iterations}. The question to determine whether the

 use of more general chaotic iterations to generate pseudorandom numbers 
 use of more general chaotic iterations to generate pseudorandom numbers 

-faster, does not deflate their topological chaos properties.
+faster, does not deflate their topological chaos properties, has been
+investigated in Annex~\ref{A-deuxième def}, leading to the following result.
+
+ \begin{theorem}
+ \label{t:chaos des general}
+  The general chaotic iterations defined in Equation~\ref{eq:generalIC}
+satisfy
+ the Devaney's property of chaos.
+ \end{theorem}

 
 
 %%RAF proof en supplementary, j'ai mis le theorem.
 % A vérifier
 
 
 
 %%RAF proof en supplementary, j'ai mis le theorem.
 % A vérifier
 

- \subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations}
-\label{deuxième def}
-The proof is given in Section~\ref{A-deuxième def} of the annex document.
+% \subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations}
+%\label{deuxième def}
+%The proof is given in Section~\ref{A-deuxième def} of the annex document.

 %% \label{deuxième def}
 %% Let us consider the discrete dynamical systems in chaotic iterations having 
 %% the general form: $\forall    n\in     \mathds{N}^{\ast     }$, $  \forall     i\in
 %% \label{deuxième def}
 %% Let us consider the discrete dynamical systems in chaotic iterations having 
 %% the general form: $\forall    n\in     \mathds{N}^{\ast     }$, $  \forall     i\in


@@ -981,10 +989,10 @@ The proof is given in Section~\ref{A-deuxième def} of the annex document.
 %%RAF : mis en supplementary
 
 
 %%RAF : mis en supplementary
 
 

-\section{Statistical Improvements Using Chaotic Iterations}
-\label{The generation of pseudorandom sequence}
-The content is this section is given in Section~\ref{A-The generation of pseudorandom sequence} of the annex document.
-
+%\section{Statistical Improvements Using Chaotic Iterations}
+%\label{The generation of pseudorandom sequence}
+%The content is this section is given in Section~\ref{A-The generation of pseudorandom sequence} of the annex document.
+The reasons to desire chaos to achieve randomness are given in Annex~\ref{A-The generation of pseudorandom sequence}.

 
 %% \label{The generation of pseudorandom sequence}
 
 
 %% \label{The generation of pseudorandom sequence}
 


@@ -1308,7 +1316,7 @@ The content is this section is given in Section~\ref{A-The generation of pseudor
 %% raise ambiguity.
 
 
 %% raise ambiguity.
 
 

-\subsection{First Efficient Implementation of a PRNG based on Chaotic Iterations}
+\section{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 
 \label{sec:efficient PRNG}
 %
 %Based on the proof presented in the previous section, it is now possible to 


@@ -1630,13 +1638,13 @@ as it is shown in the next sections.
 
 
 This section is dedicated to the security analysis of the
 
 
 This section is dedicated to the security analysis of the

-  proposed PRNGs, both from a theoretical and from a practical point of view.
+  proposed PRNGs.%, both from a theoretical and from a practical point of view.

 
 

-\subsection{Theoretical Proof of Security}
+%\subsection{Theoretical Proof of Security}

 \label{sec:security analysis}
 
 The standard definition
 \label{sec:security analysis}
 
 The standard definition

-  of {\it indistinguishability} used is the classical one as defined for
+  of {\it indistinguishability} used here 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
   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


@@ -1645,7 +1653,7 @@ The standard definition
   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
   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.
+is outlined in Annex~\ref{A-sec:Practicak evaluation}.

 
 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$.


@@ -1758,9 +1766,11 @@ proving that $H$ is not secure, which is a contradiction.
 
 
 
 
 
 

-\subsection{Practical Security Evaluation}
-\label{sec:Practicak evaluation}
-This subsection is given in Section~\ref{A-sec:Practicak evaluation} of the annex document.
+%\subsection{Practical Security Evaluation}
+%\label{sec:Practicak evaluation}
+%This subsection is given in Section
+A example of a practical security evaluation is outlined in
+Annex~\ref{A-sec:Practicak evaluation}.

 %%RAF mis en annexe
 
 
 %%RAF mis en annexe
 
 


@@ -2002,7 +2012,7 @@ 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
 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}
+a formulation similar to Annex~\ref{A-sec:Practicak evaluation} %.Eq.\eqref{mesureConcrete}

 must be established. Authors
 hope to achieve this difficult task in a future
 work.
 must be established. Authors
 hope to achieve this difficult task in a future
 work.