pch ajout contrib dans intro

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 39cee4062e6752b541cd31361f951fce7f31e20d..a32d94aa3d8c1a337657c67dabdf35fec5beec83 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -40,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}
 


@@ -166,6 +169,25 @@ 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, 
 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, 


@@ -1040,7 +1062,7 @@ not only sought in general to obtain chaos, but they are also required for rando
 \end{itemize}
 
 
 \end{itemize}
 
 

-We have proven in our previous works~\cite{} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation   des   IC   chaotiques} are, among other
+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.
 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.


@@ -1279,7 +1301,7 @@ this generator will be simply referred as CIPRNG, or ``the proposed PRNG'', if t
 raise ambiguity.
 \end{color}
 
 raise ambiguity.
 \end{color}
 

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


@@ -1358,7 +1380,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}


@@ -1594,7 +1622,16 @@ as it is shown in the next sections.
 \section{Security Analysis}
 \label{sec:security analysis}
 
 \section{Security Analysis}
 \label{sec:security analysis}
 

-
+\PCH{This section is dedicated to the analysis of the security of the
+  proposed PRNGs from a theoretical point of view. The standard definition
+  of {\it indistinguishability} used is the classical one as defined for
+  instance in~\cite[chapter~3]{Goldreich}. It is important to emphasize that
+  this property shows that predicting the future results of the PRNG's
+  cannot be done in a reasonable time compared to the generation time. 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.}

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