X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/f34b3c375a174c19a28052a60bc942cf22d76a00..4ad2ccae91afa1f83fad9be3c87213a9b8d81734:/prng_gpu.tex?ds=inline

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 74b5d86..a57e2a0 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -41,8 +41,8 @@
 \author{Jacques M. Bahi, Rapha\"{e}l Couturier,  Christophe
 Guyeux, and Pierre-Cyrille HÃ©am\thanks{Authors in alphabetic order}}
    
-\maketitle
 
+\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
@@ -57,6 +57,13 @@ A chaotic version of the Blum-Goldwasser asymmetric key encryption scheme is fin
 
 
 \end{abstract}
+}
+
+\maketitle
+
+\IEEEdisplaynotcompsoctitleabstractindextext
+\IEEEpeerreviewmaketitle
+
 
 \section{Introduction}
 
@@ -154,7 +161,7 @@ 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.
 Such a proof leads to the proposition of a cryptographically secure and
-chaotic generator on GPU based on the famous Blum Blum Shum
+chaotic generator on GPU based on the famous Blum Blum Shub
 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
@@ -217,7 +224,10 @@ We can finally remark that, to the best of our knowledge, no GPU implementation
 \label{section:BASIC RECALLS}
 
 This section is devoted to basic definitions and terminologies in the fields of
-topological chaos and chaotic iterations.
+topological chaos and chaotic iterations. We assume the reader is familiar
+with basic notions on topology (see for instance~\cite{Devaney}).
+
+
 \subsection{Devaney's Chaotic Dynamical Systems}
 
 In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$
@@ -230,7 +240,7 @@ Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
 \mathcal{X} \rightarrow \mathcal{X}$.
 
 \begin{definition}
-$f$ is said to be \emph{topologically transitive} if, for any pair of open sets
+The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets
 $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
 \varnothing$.
 \end{definition}
@@ -249,7 +259,7 @@ necessarily the same period).
 
 
 \begin{definition}[Devaney's formulation of chaos~\cite{Devaney}]
-$f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
+The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
 topologically transitive.
 \end{definition}
 
@@ -257,12 +267,12 @@ The chaos property is strongly linked to the notion of ``sensitivity'', defined
 on a metric space $(\mathcal{X},d)$ by:
 
 \begin{definition}
-\label{sensitivity} $f$ has \emph{sensitive dependence on initial conditions}
+\label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions}
 if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
 neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
 $d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
 
-$\delta$ is called the \emph{constant of sensitivity} of $f$.
+The constant $\delta$ is called the \emph{constant of sensitivity} of $f$.
 \end{definition}
 
 Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is
@@ -321,17 +331,15 @@ Let us now recall how to define a suitable metric space where chaotic iterations
 are continuous. For further explanations, see, e.g., \cite{guyeux10}.
 
 Let $\delta $ be the \emph{discrete Boolean metric}, $\delta
-(x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function:
-%%RAPH : ici j'ai coupÃ© la derniÃ¨re ligne en 2, c'est moche mais bon
-\begin{equation}
+(x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function
+$F_{f}:  \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} 
+\longrightarrow  \mathds{B}^{\mathsf{N}}$
+\begin{equation*}
 \begin{array}{lrll}
-F_{f}: & \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} &
-\longrightarrow & \mathds{B}^{\mathsf{N}} \\
-& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+ \right.\\
-&       &              & \left. f(E)_{k}.\overline{\delta
-(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
+& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+ f(E)_{k}.\overline{\delta
+(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}%
 \end{array}%
-\end{equation}%
+\end{equation*}%
 \noindent where + and . are the Boolean addition and product operations.
 Consider the phase space:
 \begin{equation}
@@ -584,11 +592,11 @@ faster, does not deflate their topological chaos properties.
 \subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations}
 \label{deuxiÃ¨me def}
 Let us consider the discrete dynamical systems in chaotic iterations having 
-the general form:
+the general form: $\forall    n\in     \mathds{N}^{\ast     }$, $  \forall     i\in
+\llbracket1;\mathsf{N}\rrbracket $,
 
 \begin{equation}
-\forall    n\in     \mathds{N}^{\ast     },    \forall     i\in
-\llbracket1;\mathsf{N}\rrbracket ,x_i^n=\left\{
+  x_i^n=\left\{
 \begin{array}{ll}
   x_i^{n-1} &  \text{ if  } i \notin \mathcal{S}^n \\
   \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n.
@@ -613,15 +621,13 @@ Let us introduce the following function:
 where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$.
 
 Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function:
-%%RAPH : j'ai coupÃ© la derniÃ¨re ligne en 2, c'est moche
-\begin{equation}
-\begin{array}{lrll}
-F_{f}: & \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} &
-\longrightarrow & \mathds{B}^{\mathsf{N}} \\
-& (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+\right.\\
-&       &             &\left.f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
+$F_{f}:  \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} 
+\longrightarrow \mathds{B}^{\mathsf{N}}$
+\begin{equation*}
+\begin{array}{rll}
+ (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}%
 \end{array}%
-\end{equation}%
+\end{equation*}%
 where + and . are the Boolean addition and product operations, and $\overline{x}$ 
 is the negation of the Boolean $x$.
 Consider the phase space:
@@ -631,7 +637,7 @@ Consider the phase space:
 \end{equation}
 \noindent and the map defined on $\mathcal{X}$:
 \begin{equation}
-G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf}
+G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), %\label{Gf} %%RAPH, j'ai virÃ© ce label qui existe dÃ©jÃ  avant...
 \end{equation}
 \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma
 (S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in
@@ -751,16 +757,16 @@ thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal.
 \noindent As a consequence, the $k+1$ first entries of the strategies of $%
 G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of
 the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $%
-10^{-(k+1)}\leqslant \varepsilon $.\bigskip \newline
+10^{-(k+1)}\leqslant \varepsilon $.
+
 In conclusion,
 %%RAPH : ici j'ai rajoutÃ© une ligne
-\begin{flushleft}$$
-\forall \varepsilon >0,\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}%
-,\forall n\geqslant N_{0},$$
-$$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right)
+$
+\forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}
+,$ $\forall n\geqslant N_{0},$
+$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right)
 \leqslant \varepsilon .
-$$
-\end{flushleft}
+$
 $G_{f}$ is consequently continuous.
 \end{proof}
 
@@ -800,7 +806,7 @@ where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties
 claimed in the lemma.
 \end{proof}
 
-We can now prove Theorem~\ref{t:chaos des general}...
+We can now prove the Theorem~\ref{t:chaos des general}.
 
 \begin{proof}[Theorem~\ref{t:chaos des general}]
 Firstly, strong transitivity implies transitivity.
@@ -1225,8 +1231,10 @@ $y\bigoplus_{i=1}^{i=j} w_i^\prime=y\bigoplus_{i=1}^{i=j} w_i$. It follows,
 by a direct induction, that $w_i=w_i^\prime$. Furthermore, since $\mathbb{B}^{kN}$
 is finite, each $\varphi_y$ is bijective. Therefore, and using (\ref{PCH-1}),
 one has
+$\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]$ and,
+therefore, 
 \begin{equation}\label{PCH-2}
-\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]=\mathrm{Pr}[D(U_{kN})=1].
+\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(U_{kN})=1].
 \end{equation}
 
 Now, using (\ref{PCH-1}) again, one has  for every $x$,
@@ -1235,7 +1243,7 @@ D^\prime(H(x))=D(\varphi_y(H(x))),
 \end{equation}
 where $y$ is randomly generated. By construction, $\varphi_y(H(x))=X(yx)$,
 thus
-\begin{equation}\label{PCH-3}
+\begin{equation}%\label{PCH-3}      %%RAPH : j'ai virÃ© ce label qui existe dÃ©jÃ , il est 3 ligne avant
 D^\prime(H(x))=D(yx),
 \end{equation}
 where $y$ is randomly generated. 
@@ -1262,7 +1270,7 @@ It is  possible to build a  cryptographically secure PRNG based  on the previous
 algorithm (Algorithm~\ref{algo:gpu_kernel2}).   Due to Proposition~\ref{cryptopreuve},
 it simply consists  in replacing
 the  {\it  xor-like} PRNG  by  a  cryptographically  secure one.  
-We have chosen the Blum Blum Shum generator~\cite{BBS} (usually denoted by BBS) having the form:
+We have chosen the Blum Blum Shub generator~\cite{BBS} (usually denoted by BBS) having the form:
 $$x_{n+1}=x_n^2~ mod~ M$$  where $M$ is the product of  two prime numbers (these
 prime numbers  need to be congruent  to 3 modulus  4). BBS is known to be
 very slow and only usable for cryptographic applications. 
@@ -1463,10 +1471,10 @@ namely the BigCrush.
 Furthermore, we have shown that when the inputted generator is cryptographically
 secure, then it is the case too for the PRNG we propose, thus leading to
 the possibility to develop fast and secure PRNGs using the GPU architecture.
-Thoughts about an improvement of the Blum-Goldwasser cryptosystem, using the 
-proposed method, has been finally proposed.
+An improvement of the Blum-Goldwasser cryptosystem, making it 
+behaves chaotically, has finally been proposed.
 
-In future  work we plan to extend these researches, building a parallel PRNG for  clusters or
+In future  work we plan to extend this research, building a parallel PRNG for  clusters or
 grid computing. Topological properties of the various proposed generators will be investigated,
 and the use of other categories of PRNGs as input will be studied too. The improvement
 of Blum-Goldwasser will be deepened. Finally, we
