-\documentclass{article}
+%\documentclass{article}
+\documentclass[10pt,journal,letterpaper,compsoc]{IEEEtran}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fullpage}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{listings}
\usepackage[standard]{ntheorem}
+\usepackage{algorithmic}
+\usepackage{slashbox}
% Pour mathds : les ensembles IR, IN, etc.
\usepackage{dsfont}
\begin{document}
\author{Jacques M. Bahi, Rapha\"{e}l Couturier, Christophe
-Guyeux, and Pierre-Cyrille Heam\thanks{Authors in alphabetic order}}
+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
\end{abstract}
+}
+
+\maketitle
+
+\IEEEdisplaynotcompsoctitleabstractindextext
+\IEEEpeerreviewmaketitle
+
\section{Introduction}
Furthermore, we show that the proposed post-treatment preserves the
cryptographical security of the inputted PRNG, when this last has such a
property.
-Last, but not least, we propose a rewritting of the Blum-Goldwasser asymmetric
+Last, but not least, we propose a rewriting of the Blum-Goldwasser asymmetric
key encryption protocol by using the proposed method.
The remainder of this paper is organized as follows. In Section~\ref{section:related
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
\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}$
\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}
\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}
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
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:
-\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)+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}
\end{proposition}
The chaotic property of $G_f$ has been firstly established for the vectorial
-Boolean negation $f(x_1,\hdots, x_\mathsf{N}) = (\overline{x_1},\hdots, \overline{x_\mathsf{N}})$ \cite{guyeux10}. To obtain a characterization, we have secondly
+Boolean negation $f_0(x_1,\hdots, x_\mathsf{N}) = (\overline{x_1},\hdots, \overline{x_\mathsf{N}})$ \cite{guyeux10}. To obtain a characterization, we have secondly
introduced the notion of asynchronous iteration graph recalled bellow.
Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. The
We have proposed in~\cite{bgw09:ip} a new family of generators that receives
two PRNGs as inputs. These two generators are mixed with chaotic iterations,
-leading thus to a new PRNG that improves the statistical properties of each
-generator taken alone. Furthermore, our generator
-possesses various chaos properties that none of the generators used as input
+leading thus to a new PRNG that
+\begin{color}{red}
+should improves the statistical properties of each
+generator taken alone.
+Furthermore, the generator obtained by this way possesses various chaos properties that none of the generators used as input
present.
+
+
\begin{algorithm}[h!]
-%\begin{scriptsize}
+\begin{small}
\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$
($n$ bits)}
\KwOut{a configuration $x$ ($n$ bits)}
$x\leftarrow x^0$\;
-$k\leftarrow b + \textit{XORshift}(b)$\;
+$k\leftarrow b + PRNG_1(b)$\;
\For{$i=0,\dots,k$}
{
-$s\leftarrow{\textit{XORshift}(n)}$\;
+$s\leftarrow{PRNG_2(n)}$\;
$x\leftarrow{F_f(s,x)}$\;
}
return $x$\;
-%\end{scriptsize}
-\caption{PRNG with chaotic functions}
+\end{small}
+\caption{An arbitrary round of $Old~ CI~ PRNG_f(PRNG_1,PRNG_2)$}
\label{CI Algorithm}
\end{algorithm}
+
+
+
+This generator is synthesized in Algorithm~\ref{CI Algorithm}.
+It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques};
+an integer $b$, ensuring that the number of executed iterations
+between two outputs is at least $b$
+and at most $2b+1$; and an initial configuration $x^0$.
+It returns the new generated configuration $x$. Internally, it embeds two
+inputted generators $PRNG_i(k), i=1,2$,
+ which must return integers
+uniformly distributed
+into $\llbracket 1 ; k \rrbracket$.
+For instance, these PRNGs can be the \textit{XORshift}~\cite{Marsaglia2003},
+being a category of very fast PRNGs designed by George Marsaglia
+that repeatedly uses the transform of exclusive or (XOR, $\oplus$) on a number
+with a bit shifted version of it. Such a PRNG, which has a period of
+$2^{32}-1=4.29\times10^9$, is summed up in Algorithm~\ref{XORshift}.
+This XORshift, or any other reasonable PRNG, is used
+in our own generator to compute both the number of iterations between two
+outputs (provided by $PRNG_1$) and the strategy elements ($PRNG_2$).
+
+%This former generator has successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} ones.
+
+
\begin{algorithm}[h!]
+\begin{small}
\KwIn{the internal configuration $z$ (a 32-bit word)}
\KwOut{$y$ (a 32-bit word)}
$z\leftarrow{z\oplus{(z\ll13)}}$\;
$z\leftarrow{z\oplus{(z\ll5)}}$\;
$y\leftarrow{z}$\;
return $y$\;
-\medskip
+\end{small}
\caption{An arbitrary round of \textit{XORshift} algorithm}
\label{XORshift}
\end{algorithm}
+\subsection{A ``New CI PRNG''}
+
+In order to make the Old CI PRNG usable in practice, we have proposed
+an adapted version of the chaotic iteration based generator in~\cite{bg10:ip}.
+In this ``New CI PRNG'', we prevent from changing twice a given
+bit between two outputs.
+This new generator is designed by the following process.
+
+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
+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
+\llbracket 1, 32 \rrbracket^\mathds{N}$ is
+an \emph{irregular decimation} of $PRNG_2$ sequence, as described in
+Algorithm~\ref{Chaotic iteration1}.
+
+Then, at each iteration, only the $S^n$-th component of state $x^n$ is
+updated, as follows: $x_i^n = x_i^{n-1}$ if $i \neq S^n$, else $x_i^n = \overline{x_i^{n-1}}$.
+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.
+$(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).
+\begin{equation}
+\label{Formula}
+m^n = g(y^n)=
+\left\{
+\begin{array}{l}
+0 \text{ if }0 \leqslant{y^n}<{C^0_{32}},\\
+1 \text{ if }{C^0_{32}} \leqslant{y^n}<\sum_{i=0}^1{C^i_{32}},\\
+2 \text{ if }\sum_{i=0}^1{C^i_{32}} \leqslant{y^n}<\sum_{i=0}^2{C^i_{32}},\\
+\vdots~~~~~ ~~\vdots~~~ ~~~~\\
+N \text{ if }\sum_{i=0}^{N-1}{C^i_{32}}\leqslant{y^n}<1.\\
+\end{array}
+\right.
+\end{equation}
-
-This generator is synthesized in Algorithm~\ref{CI Algorithm}.
-It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques};
-an integer $b$, ensuring that the number of executed iterations is at least $b$
-and at most $2b+1$; and an initial configuration $x^0$.
-It returns the new generated configuration $x$. Internally, it embeds two
-\textit{XORshift}$(k)$ PRNGs~\cite{Marsaglia2003} that return integers
-uniformly distributed
-into $\llbracket 1 ; k \rrbracket$.
-\textit{XORshift} is a category of very fast PRNGs designed by George Marsaglia,
-which repeatedly uses the transform of exclusive or (XOR, $\oplus$) on a number
-with a bit shifted version of it. This PRNG, which has a period of
-$2^{32}-1=4.29\times10^9$, is summed up in Algorithm~\ref{XORshift}. It is used
-in our PRNG to compute the strategy length and the strategy elements.
-
-This former generator has successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} ones.
+\begin{algorithm}
+\textbf{Input:} the internal state $x$ (32 bits)\\
+\textbf{Output:} a state $r$ of 32 bits
+\begin{algorithmic}[1]
+\FOR{$i=0,\dots,N$}
+{
+\STATE$d_i\leftarrow{0}$\;
+}
+\ENDFOR
+\STATE$a\leftarrow{PRNG_1()}$\;
+\STATE$m\leftarrow{g(a)}$\;
+\STATE$k\leftarrow{m}$\;
+\WHILE{$i=0,\dots,k$}
+
+\STATE$b\leftarrow{PRNG_2()~mod~\mathsf{N}}$\;
+\STATE$S\leftarrow{b}$\;
+ \IF{$d_S=0$}
+ {
+\STATE $x_S\leftarrow{ \overline{x_S}}$\;
+\STATE $d_S\leftarrow{1}$\;
+
+ }
+ \ELSIF{$d_S=1$}
+ {
+\STATE $k\leftarrow{ k+1}$\;
+ }\ENDIF
+\ENDWHILE\\
+\STATE $r\leftarrow{x}$\;
+\STATE return $r$\;
+\medskip
+\caption{An arbitrary round of the new CI generator}
+\label{Chaotic iteration1}
+\end{algorithmic}
+\end{algorithm}
+\end{color}
\subsection{Improving the Speed of the Former Generator}
-Instead of updating only one cell at each iteration, we can try to choose a
-subset of components and to update them together. Such an attempt leads
-to a kind of merger of the two sequences used in Algorithm
-\ref{CI Algorithm}. When the updating function is the vectorial negation,
+Instead of updating only one cell at each iteration,\begin{color}{red} we now propose to choose a
+subset of components and to update them together, for speed improvements. Such a proposition leads\end{color}
+to a kind of merger of the two sequences used in Algorithms
+\ref{CI Algorithm} and \ref{Chaotic iteration1}. When the updating function is the vectorial negation,
this algorithm can be rewritten as follows:
\begin{equation}
\forall n \in \mathds{N}^*, x^n = x^{n-1} \oplus S^n,
\end{array}
\right.
-\label{equation Oplus}
+\label{equation Oplus0}
\end{equation}
where $\oplus$ is for the bitwise exclusive or between two integers.
-This rewritting can be understood as follows. The $n-$th term $S^n$ of the
+This rewriting can be understood as follows. The $n-$th term $S^n$ of the
sequence $S$, which is an integer of $\mathsf{N}$ binary digits, presents
the list of cells to update in the state $x^n$ of the system (represented
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.
-The single basic component presented in Eq.~\ref{equation Oplus} is of
+The single basic component presented in Eq.~\ref{equation Oplus0} is of
ordinary use as a good elementary brick in various PRNGs. It corresponds
to the following discrete dynamical system in chaotic iterations:
we select a subset of components to change.
-Obviously, replacing Algorithm~\ref{CI Algorithm} by
-Equation~\ref{equation Oplus}, which is possible when the iteration function is
+Obviously, replacing the previous CI PRNG Algorithms by
+Equation~\ref{equation Oplus0}, which is possible when the iteration function is
the vectorial negation, leads to a speed improvement. However, proofs
of chaos obtained in~\cite{bg10:ij} have been established
only for chaotic iterations of the form presented in Definition
\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.
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:
-\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)+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:
\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
d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
\label{nouveau d}
\end{equation}
-\noindent where
-\begin{equation}
-\left\{
-\begin{array}{lll}
-\displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
-}\delta (E_{k},\check{E}_{k})}\textrm{ is once more the Hamming distance}, \\
-\displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
-\sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.%
-\end{array}%
-\right.
-\end{equation}
+\noindent where $ \displaystyle{d_{e}(E,\check{E})} = \displaystyle{\sum_{k=1}^{\mathsf{N}%
+ }\delta (E_{k},\check{E}_{k})}$ is once more the Hamming distance, and
+$ \displaystyle{d_{s}(S,\check{S})} = \displaystyle{\dfrac{9}{\mathsf{N}}%
+ \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}$,
+%%RAPH : ici, j'ai supprimé tous les sauts à la ligne
+%% \begin{equation}
+%% \left\{
+%% \begin{array}{lll}
+%% \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
+%% }\delta (E_{k},\check{E}_{k})} \textrm{ is once more the Hamming distance}, \\
+%% \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
+%% \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.%
+%% \end{array}%
+%% \right.
+%% \end{equation}
where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as
$A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$.
\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,
-$$
-\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)
+%%RAPH : ici j'ai rajouté une ligne
+$
+\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 .
-$$
+$
$G_{f}$ is consequently continuous.
\end{proof}
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.
that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$.
Consider the strategy $\tilde S$ that alternates the first $t_1$ terms
-of $S$ and the first $t_2$ terms of $S'$: $$\tilde
-S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It
+of $S$ and the first $t_2$ terms of $S'$:
+%%RAPH : j'ai coupé la ligne en 2
+$$\tilde
+S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It
is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after
$t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic
point. Since $\tilde S_t=S_t$ for $t<t_1$, by the choice of $t_1$, we
\end{proof}
+\begin{color}{red}
+\section{Statistical Improvements Using Chaotic Iterations}
+
+\label{The generation of pseudo-random sequence}
+
+
+Let us now explain why we are reasonable grounds to believe that chaos
+can improve statistical properties.
+We will show in this section that, when mixing defective PRNGs with
+chaotic iterations, the result presents better statistical properties
+(this section summarizes the work of~\cite{bfg12a:ip}).
+
+\subsection{Details of some Existing Generators}
+
+The list of defective PRNGs we will use
+as inputs for the statistical tests to come is introduced here.
+
+Firstly, the simple linear congruency generator (LCGs) will be used.
+It is defined by the following recurrence:
+\begin{equation}
+x^n = (ax^{n-1} + c)~mod~m
+\label{LCG}
+\end{equation}
+where $a$, $c$, and $x^0$ must be, among other things, non-negative and less than
+$m$~\cite{LEcuyerS07}. In what follows, 2LCGs and 3LCGs refer as two (resp. three)
+combinations of such LCGs. For further details, see~\cite{bfg12a:ip,combined_lcg}.
+
+Secondly, the multiple recursive generators (MRGs) will be used too, which
+are based on a linear recurrence of order
+$k$, modulo $m$~\cite{LEcuyerS07}:
+\begin{equation}
+x^n = (a^1x^{n-1}+~...~+a^kx^{n-k})~mod~m
+\label{MRG}
+\end{equation}
+Combination of two MRGs (referred as 2MRGs) is also used in these experimentations.
+
+Generators based on linear recurrences with carry will be regarded too.
+This family of generators includes the add-with-carry (AWC) generator, based on the recurrence:
+\begin{equation}
+\label{AWC}
+\begin{array}{l}
+x^n = (x^{n-r} + x^{n-s} + c^{n-1})~mod~m, \\
+c^n= (x^{n-r} + x^{n-s} + c^{n-1}) / m, \end{array}\end{equation}
+the SWB generator, having the recurrence:
+\begin{equation}
+\label{SWB}
+\begin{array}{l}
+x^n = (x^{n-r} - x^{n-s} - c^{n-1})~mod~m, \\
+c^n=\left\{
+\begin{array}{l}
+1 ~~~~~\text{if}~ (x^{i-r} - x^{i-s} - c^{i-1})<0\\
+0 ~~~~~\text{else},\end{array} \right. \end{array}\end{equation}
+and the SWC generator designed by R. Couture, which is based on the following recurrence:
+\begin{equation}
+\label{SWC}
+\begin{array}{l}
+x^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ mod ~ 2^w, \\
+c^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ / ~ 2^w. \end{array}\end{equation}
+
+Then the generalized feedback shift register (GFSR) generator has been implemented, that is:
+\begin{equation}
+x^n = x^{n-r} \oplus x^{n-k}
+\label{GFSR}
+\end{equation}
+
+
+Finally, the nonlinear inversive generator~\cite{LEcuyerS07} has been regarded too, which is:
+
+\begin{equation}
+\label{INV}
+\begin{array}{l}
+x^n=\left\{
+\begin{array}{ll}
+(a^1 + a^2 / z^{n-1})~mod~m & \text{if}~ z^{n-1} \neq 0 \\
+a^1 & \text{if}~ z^{n-1} = 0 .\end{array} \right. \end{array}\end{equation}
+
+
+
+
+
+\subsection{Statistical tests}
+\label{Security analysis}
+
+Three batteries of tests are reputed and usually used
+to evaluate the statistical properties of newly designed pseudorandom
+number generators. These batteries are named DieHard~\cite{Marsaglia1996},
+the NIST suite~\cite{ANDREW2008}, and the most stringent one called
+TestU01~\cite{LEcuyerS07}, which encompasses the two other batteries.
+
+
+
+\label{Results and discussion}
+\begin{table*}
+\renewcommand{\arraystretch}{1.3}
+\caption{NIST and DieHARD tests suite passing rates for PRNGs without CI}
+\label{NIST and DieHARD tests suite passing rate the for PRNGs without CI}
+\centering
+ \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|}
+ \hline\hline
+Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline
+\backslashbox{\textbf{$Tests$}} {\textbf{$PRNG$}} & LCG& MRG& AWC & SWB & SWC & GFSR & INV & LCG2& LCG3& MRG2 \\ \hline
+NIST & 11/15 & 14/15 &\textbf{15/15} & \textbf{15/15} & 14/15 & 14/15 & 14/15 & 14/15& 14/15& 14/15 \\ \hline
+DieHARD & 16/18 & 16/18 & 15/18 & 16/18 & \textbf{18/18} & 16/18 & 16/18 & 16/18& 16/18& 16/18\\ \hline
+\end{tabular}
+\end{table*}
+
+Table~\ref{NIST and DieHARD tests suite passing rate the for PRNGs without CI} shows the
+results on the two firsts batteries recalled above, indicating that all the PRNGs presented
+in the previous section
+cannot pass all these tests. In other words, the statistical quality of these PRNGs cannot
+fulfill the up-to-date standards presented previously. We have shown in~\cite{bfg12a:ip} that the use of chaotic
+iterations can solve this issue.
+More precisely, to
+illustrate the effects of chaotic iterations on these defective PRNGs, experiments have been divided in three parts~\cite{bfg12a:ip}:
+\begin{enumerate}
+ \item \textbf{Single CIPRNG}: The PRNGs involved in CI computing are of the same category.
+ \item \textbf{Mixed CIPRNG}: Two different types of PRNGs are mixed during the chaotic iterations process.
+ \item \textbf{Multiple CIPRNG}: The generator is obtained by repeating the composition of the iteration function as follows: $x^0\in \mathds{B}^{\mathsf{N}}$, and $\forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket, x_i^n=$
+\begin{equation}
+\begin{array}{l}
+\left\{
+\begin{array}{l}
+x_i^{n-1}~~~~~\text{if}~S^n\neq i \\
+\forall j\in \llbracket1;\mathsf{m}\rrbracket,f^m(x^{n-1})_{S^{nm+j}}~\text{if}~S^{nm+j}=i.\end{array} \right. \end{array}
+\end{equation}
+$m$ is called the \emph{functional power}.
+\end{enumerate}
+
+
+We have performed statistical analysis of each of the aforementioned CIPRNGs.
+The results are reproduced in Tables~\ref{NIST and DieHARD tests suite passing rate the for PRNGs without CI} and \ref{NIST and DieHARD tests suite passing rate the for single CIPRNGs}.
+The scores written in boldface indicate that all the tests have been passed successfully, whereas an asterisk ``*'' means that the considered passing rate has been improved.
+
+\subsubsection{Tests based on the Single CIPRNG}
+
+\begin{table*}
+\renewcommand{\arraystretch}{1.3}
+\caption{NIST and DieHARD tests suite passing rates for PRNGs with CI}
+\label{NIST and DieHARD tests suite passing rate the for single CIPRNGs}
+\centering
+ \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|}
+ \hline
+Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline
+\backslashbox{\textbf{$Tests$}} {\textbf{$Single~CIPRNG$}} & LCG & MRG & AWC & SWB & SWC & GFSR & INV& LCG2 & LCG3& MRG2 \\ \hline\hline
+Old CIPRNG\\ \hline \hline
+NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline
+DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * \\ \hline
+New CIPRNG\\ \hline \hline
+NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline
+DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} *\\ \hline
+Xor CIPRNG\\ \hline\hline
+NIST & 14/15*& \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & 14/15 & \textbf{15/15} * & 14/15& \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} \\ \hline
+DieHARD & 16/18 & 16/18 & 17/18* & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & 16/18 & 16/18 & 16/18& 16/18\\ \hline
+\end{tabular}
+\end{table*}
+
+The statistical tests results of the PRNGs using the single CIPRNG method are given in Table~\ref{NIST and DieHARD tests suite passing rate the for single CIPRNGs}.
+We can observe that, except for the Xor CIPRNG, all of the CIPRNGs have passed the 15 tests of the NIST battery and the 18 tests of the DieHARD one.
+Moreover, considering these scores, we can deduce that both the single Old CIPRNG and the single New CIPRNG are relatively steadier than the single Xor CIPRNG approach, when applying them to different PRNGs.
+However, the Xor CIPRNG is obviously the fastest approach to generate a CI random sequence, and it still improves the statistical properties relative to each generator taken alone, although the test values are not as good as desired.
+
+Therefore, all of these three ways are interesting, for different reasons, in the production of pseudorandom numbers and,
+on the whole, the single CIPRNG method can be considered to adapt to or improve all kinds of PRNGs.
+
+To have a realization of the Xor CIPRNG that can pass all the tests embedded into the NIST battery, the Xor CIPRNG with multiple functional powers are investigated in Section~\ref{Tests based on Multiple CIPRNG}.
+
+
+\subsubsection{Tests based on the Mixed CIPRNG}
+
+To compare the previous approach with the CIPRNG design that uses a Mixed CIPRNG, we have taken into account the same inputted generators than in the previous section.
+These inputted couples $(PRNG_1,PRNG_2)$ of PRNGs are used in the Mixed approach as follows:
+\begin{equation}
+\left\{
+\begin{array}{l}
+x^0 \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket, S \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket^\mathds{N} \\
+\forall n \in \mathds{N}^*, x^n = x^{n-1} \oplus PRNG_1\oplus PRNG_2,
+\end{array}
+\right.
+\label{equation Oplus}
+\end{equation}
+
+With this Mixed CIPRNG approach, both the Old CIPRNG and New CIPRNG continue to pass all the NIST and DieHARD suites.
+In addition, we can see that the PRNGs using a Xor CIPRNG approach can pass more tests than previously.
+The main reason of this success is that the Mixed Xor CIPRNG has a longer period.
+Indeed, let $n_{P}$ be the period of a PRNG $P$, then the period deduced from the single Xor CIPRNG approach is obviously equal to:
+\begin{equation}
+n_{SXORCI}=
+\left\{
+\begin{array}{ll}
+n_{P}&\text{if~}x^0=x^{n_{P}}\\
+2n_{P}&\text{if~}x^0\neq x^{n_{P}}.\\
+\end{array}
+\right.
+\label{equation Oplus}
+\end{equation}
+
+Let us now denote by $n_{P1}$ and $n_{P2}$ the periods of respectively the $PRNG_1$ and $PRNG_2$ generators, then the period of the Mixed Xor CIPRNG will be:
+\begin{equation}
+n_{XXORCI}=
+\left\{
+\begin{array}{ll}
+LCM(n_{P1},n_{P2})&\text{if~}x^0=x^{LCM(n_{P1},n_{P2})}\\
+2LCM(n_{P1},n_{P2})&\text{if~}x^0\neq x^{LCM(n_{P1},n_{P2})}.\\
+\end{array}
+\right.
+\label{equation Oplus}
+\end{equation}
+
+In Table~\ref{DieHARD fail mixex CIPRNG}, we only show the results for the Mixed CIPRNGs that cannot pass all DieHARD suites (the NIST tests are all passed). It demonstrates that Mixed Xor CIPRNG involving LCG, MRG, LCG2, LCG3, MRG2, or INV cannot pass the two following tests, namely the ``Matrix Rank 32x32'' and the ``COUNT-THE-1's'' tests contained into the DieHARD battery. Let us recall their definitions:
+
+\begin{itemize}
+ \item \textbf{Matrix Rank 32x32.} A random 32x32 binary matrix is formed, each row having a 32-bit random vector. Its rank is an integer that ranges from 0 to 32. Ranks less than 29 must be rare, and their occurences must be pooled with those of rank 29. To achieve the test, ranks of 40,000 such random matrices are obtained, and a chisquare test is performed on counts for ranks 32,31,30 and for ranks $\leq29$.
+
+ \item \textbf{COUNT-THE-1's TEST} Consider the file under test as a stream of bytes (four per 2 bit integer). Each byte can contain from 0 to 8 1's, with probabilities 1,8,28,56,70,56,28,8,1 over 256. Now let the stream of bytes provide a string of overlapping 5-letter words, each ``letter'' taking values A,B,C,D,E. The letters are determined by the number of 1's in a byte: 0,1, or 2 yield A, 3 yields B, 4 yields C, 5 yields D and 6,7, or 8 yield E. Thus we have a monkey at a typewriter hitting five keys with various probabilities (37,56,70,56,37 over 256). There are $5^5$ possible 5-letter words, and from a string of 256,000 (over-lapping) 5-letter words, counts are made on the frequencies for each word. The quadratic form in the weak inverse of the covariance matrix of the cell counts provides a chisquare test: Q5-Q4, the difference of the naive Pearson sums of $(OBS-EXP)^2/EXP$ on counts for 5- and 4-letter cell counts.
+\end{itemize}
+
+The reason of these fails is that the output of LCG, LCG2, LCG3, MRG, and MRG2 under the experiments are in 31-bit. Compare with the Single CIPRNG, using different PRNGs to build CIPRNG seems more efficient in improving random number quality (mixed Xor CI can 100\% pass NIST, but single cannot).
+
+\begin{table*}
+\renewcommand{\arraystretch}{1.3}
+\caption{Scores of mixed Xor CIPRNGs when considering the DieHARD battery}
+\label{DieHARD fail mixex CIPRNG}
+\centering
+ \begin{tabular}{|l||c|c|c|c|c|c|}
+ \hline
+\backslashbox{\textbf{$PRNG_1$}} {\textbf{$PRNG_0$}} & LCG & MRG & INV & LCG2 & LCG3 & MRG2 \\ \hline\hline
+LCG &\backslashbox{} {} &16/18&16/18 &16/18 &16/18 &16/18\\ \hline
+MRG &16/18 &\backslashbox{} {} &16/18&16/18 &16/18 &16/18\\ \hline
+INV &16/18 &16/18&\backslashbox{} {} &16/18 &16/18&16/18 \\ \hline
+LCG2 &16/18 &16/18 &16/18 &\backslashbox{} {} &16/18&16/18\\ \hline
+LCG3 &16/18 &16/18 &16/18&16/18&\backslashbox{} {} &16/18\\ \hline
+MRG2 &16/18 &16/18 &16/18&16/18 &16/18 &\backslashbox{} {} \\ \hline
+\end{tabular}
+\end{table*}
+
+\subsubsection{Tests based on the Multiple CIPRNG}
+\label{Tests based on Multiple CIPRNG}
+
+Until now, the combination of at most two input PRNGs has been investigated.
+We now regard the possibility to use a larger number of generators to improve the statistics of the generated pseudorandom numbers, leading to the multiple functional power approach.
+For the CIPRNGs which have already pass both the NIST and DieHARD suites with 2 inputted PRNGs (all the Old and New CIPRNGs, and some of the Xor CIPRNGs), it is not meaningful to consider their adaption of this multiple CIPRNG method, hence only the Multiple Xor CIPRNGs, having the following form, will be investigated.
+\begin{equation}
+\left\{
+\begin{array}{l}
+x^0 \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket, S \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket^\mathds{N} \\
+\forall n \in \mathds{N}^*, x^n = x^{n-1} \oplus S^{nm}\oplus S^{nm+1}\ldots \oplus S^{nm+m-1} ,
+\end{array}
+\right.
+\label{equation Oplus}
+\end{equation}
+
+The question is now to determine the value of the threshold $m$ (the functional power) making the multiple CIPRNG being able to pass the whole NIST battery.
+Such a question is answered in Table~\ref{threshold}.
+
+
+\begin{table*}
+\renewcommand{\arraystretch}{1.3}
+\caption{Functional power $m$ making it possible to pass the whole NIST battery}
+\label{threshold}
+\centering
+ \begin{tabular}{|l||c|c|c|c|c|c|c|c|}
+ \hline
+Inputted $PRNG$ & LCG & MRG & SWC & GFSR & INV& LCG2 & LCG3 & MRG2 \\ \hline\hline
+Threshold value $m$& 19 & 7 & 2& 1 & 11& 9& 3& 4\\ \hline\hline
+\end{tabular}
+\end{table*}
+
+\subsubsection{Results Summary}
+
+We can summarize the obtained results as follows.
+\begin{enumerate}
+\item The CIPRNG method is able to improve the statistical properties of a large variety of PRNGs.
+\item Using different PRNGs in the CIPRNG approach is better than considering several instances of one unique PRNG.
+\item The statistical quality of the outputs increases with the functional power $m$.
+\end{enumerate}
+
+\end{color}
\section{Efficient PRNG based on Chaotic Iterations}
\label{sec:efficient PRNG}
iterations can be inherited by the inputted generator, we hope by doing so to
obtain some statistical improvements while preserving speed.
-
-Let us give an example using 16-bits numbers, to clearly understand how the bitwise xor operations
-are
-done.
-Suppose that $x$ and the strategy $S^i$ are given as
-binary vectors.
-Table~\ref{TableExemple} shows the result of $x \oplus S^i$.
-
-\begin{table}
-$$
-\begin{array}{|cc|cccccccccccccccc|}
-\hline
-x &=&1&0&1&1&1&0&1&0&1&0&0&1&0&0&1&0\\
-\hline
-S^i &=&0&1&1&0&0&1&1&0&1&1&1&0&0&1&1&1\\
-\hline
-x \oplus S^i&=&1&1&0&1&1&1&0&0&0&1&1&1&0&1&0&1\\
-\hline
-
-\hline
- \end{array}
-$$
-\caption{Example of an arbitrary round of the proposed generator}
-\label{TableExemple}
-\end{table}
-
-
-
-
-\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iteration\
-s},label=algo:seqCIPRNG}
+%%RAPH : j'ai viré tout ca
+%% Let us give an example using 16-bits numbers, to clearly understand how the bitwise xor operations
+%% are
+%% done.
+%% Suppose that $x$ and the strategy $S^i$ are given as
+%% binary vectors.
+%% Table~\ref{TableExemple} shows the result of $x \oplus S^i$.
+
+%% \begin{table}
+%% \begin{scriptsize}
+%% $$
+%% \begin{array}{|cc|cccccccccccccccc|}
+%% \hline
+%% x &=&1&0&1&1&1&0&1&0&1&0&0&1&0&0&1&0\\
+%% \hline
+%% S^i &=&0&1&1&0&0&1&1&0&1&1&1&0&0&1&1&1\\
+%% \hline
+%% x \oplus S^i&=&1&1&0&1&1&1&0&0&0&1&1&1&0&1&0&1\\
+%% \hline
+
+%% \hline
+%% \end{array}
+%% $$
+%% \end{scriptsize}
+%% \caption{Example of an arbitrary round of the proposed generator}
+%% \label{TableExemple}
+%% \end{table}
+
+
+
+
+\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iterations},label=algo:seqCIPRNG}
+\begin{small}
\begin{lstlisting}
+
unsigned int CIPRNG() {
static unsigned int x = 123123123;
unsigned long t1 = xorshift();
return x;
}
\end{lstlisting}
-
+\end{small}
implementation of the xor128, the xorshift, and the xorwow respectively require
4, 5, and 6 unsigned long as internal variables.
-\begin{algorithm}
+\begin{algorithm}
+\begin{small}
\KwIn{InternalVarXorLikeArray: array with internal variables of the 3 xor-like
PRNGs in global memory\;
NumThreads: number of threads\;}
}
store internal variables in InternalVarXorLikeArray[threadIdx]\;
}
-
+\end{small}
\caption{Main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations}
\label{algo:gpu_kernel}
\end{algorithm}
+
+
Algorithm~\ref{algo:gpu_kernel} presents a naive implementation of the proposed PRNG on
GPU. Due to the available memory in the GPU and the number of threads
-used simultenaously, the number of random numbers that a thread can generate
+used simultaneously, the number of random numbers that a thread can generate
inside a kernel is limited (\emph{i.e.}, the variable \texttt{n} in
algorithm~\ref{algo:gpu_kernel}). For instance, if $100,000$ threads are used and
if $n=100$\footnote{in fact, we need to add the initial seed (a 32-bits number)},
This version can also pass the whole {\it BigCrush} battery of tests.
\begin{algorithm}
-
+\begin{small}
\KwIn{InternalVarXorLikeArray: array with internal variables of 1 xor-like PRNGs
in global memory\;
NumThreads: Number of threads\;
}
store internal variables in InternalVarXorLikeArray[threadId]\;
}
-
+\end{small}
\caption{Main kernel for the chaotic iterations based PRNG GPU efficient
version\label{IR}}
\label{algo:gpu_kernel2}
\begin{figure}[htbp]
\begin{center}
- \includegraphics[scale=.7]{curve_time_xorlike_gpu.pdf}
+ \includegraphics[width=\columnwidth]{curve_time_xorlike_gpu.pdf}
\end{center}
\caption{Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG}
\label{fig:time_xorlike_gpu}
\begin{figure}[htbp]
\begin{center}
- \includegraphics[scale=.7]{curve_time_bbs_gpu.pdf}
+ \includegraphics[width=\columnwidth]{curve_time_bbs_gpu.pdf}
\end{center}
\caption{Quantity of pseudorandom numbers generated per second using the BBS-based PRNG}
\label{fig:time_bbs_gpu}
denoted by $uv$.
In a cryptographic context, a pseudorandom generator is a deterministic
algorithm $G$ transforming strings into strings and such that, for any
-seed $k$ of length $k$, $G(k)$ (the output of $G$ on the input $k$) has size
-$\ell_G(k)$ with $\ell_G(k)>k$.
+seed $s$ of length $m$, $G(s)$ (the output of $G$ on the input $s$) has size
+$\ell_G(m)$ with $\ell_G(m)>m$.
The notion of {\it secure} PRNGs can now be defined as follows.
\begin{definition}
A cryptographic PRNG $G$ is secure if for any probabilistic polynomial time
algorithm $D$, for any positive polynomial $p$, and for all sufficiently
-large $k$'s,
-$$| \mathrm{Pr}[D(G(U_k))=1]-Pr[D(U_{\ell_G(k)})=1]|< \frac{1}{p(k)},$$
+large $m$'s,
+$$| \mathrm{Pr}[D(G(U_m))=1]-Pr[D(U_{\ell_G(m)})=1]|< \frac{1}{p(m)},$$
where $U_r$ is the uniform distribution over $\{0,1\}^r$ and the
-probabilities are taken over $U_N$, $U_{\ell_G(N)}$ as well as over the
+probabilities are taken over $U_m$, $U_{\ell_G(m)}$ as well as over the
internal coin tosses of $D$.
\end{definition}
negligible probability. The interested reader is referred
to~\cite[chapter~3]{Goldreich} for more information. Note that it is
quite easily possible to change the function $\ell$ into any polynomial
-function $\ell^\prime$ satisfying $\ell^\prime(N)>N)$~\cite[Chapter 3.3]{Goldreich}.
+function $\ell^\prime$ satisfying $\ell^\prime(m)>m)$~\cite[Chapter 3.3]{Goldreich}.
The generation schema developed in (\ref{equation Oplus}) is based on a
pseudorandom generator. Let $H$ be a cryptographic PRNG. We may assume,
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$,
\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.
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.
indistinguishable bits is lesser than or equals to
$log_2(log_2(M))$). In other words, to generate a 32-bits number, we need to use
8 times the BBS algorithm with possibly different combinations of $M$. This
-approach is not sufficient to be able to pass all the TestU01,
+approach is not sufficient to be able to pass all the tests of TestU01,
as small values of $M$ for the BBS lead to
small periods. So, in order to add randomness we have proceeded with
the followings modifications.
\end{itemize}
\begin{algorithm}
-
+\begin{small}
\KwIn{InternalVarBBSArray: array with internal variables of the 8 BBS
in global memory\;
NumThreads: Number of threads\;
}
store internal variables in InternalVarXorLikeArray[threadId] using a rotation\;
}
-
+\end{small}
\caption{main kernel for the BBS based PRNG GPU}
\label{algo:bbs_gpu}
\end{algorithm}
most} 3 bits, represented by \texttt{shift} in the algorithm, and we put
\emph{exactly} the \texttt{shift} last bits from a BBS into the \texttt{shift}
last bits of $t$. For this, an array named \texttt{array\_shift}, containing the
-correspondance between the shift and the number obtained with \texttt{shift} 1
+correspondence between the shift and the number obtained with \texttt{shift} 1
to make the \texttt{and} operation is used. For example, with a left shift of 0,
we make an and operation with 0, with a left shift of 3, we make an and
operation with 7 (represented by 111 in binary mode).
+\begin{color}{red}
+\subsection{Practical Security Evaluation}
+
+Suppose now that the PRNG will work during
+$M=100$ time units, and that during this period,
+an attacker can realize $10^{12}$ clock cycles.
+We thus wonder whether, during the PRNG's
+lifetime, the attacker can distinguish this
+sequence from truly random one, with a probability
+greater than $\varepsilon = 0.2$.
+We consider that $N$ has 900 bits.
+
+The random process is the BBS generator, which
+is cryptographically secure. More precisely, it
+is $(T,\varepsilon)-$secure: no
+$(T,\varepsilon)-$distinguishing attack can be
+successfully realized on this PRNG, if~\cite{Fischlin}
+$$
+T \leqslant \dfrac{L(N)}{6 N (log_2(N))\varepsilon^{-2}M^2}-2^7 N \varepsilon^{-2} M^2 log_2 (8 N \varepsilon^{-1}M)
+$$
+where $M$ is the length of the output ($M=100$ in
+our example), and $L(N)$ is equal to
+$$
+2.8\times 10^{-3} exp \left(1.9229 \times (N ~ln(2)^\frac{1}{3}) \times ln(N~ln 2)^\frac{2}{3}\right)
+$$
+is the number of clock cycles to factor a $N-$bit
+integer.
+
+A direct numerical application shows that this attacker
+cannot achieve its $(10^{12},0.2)$ distinguishing
+attack in that context.
+
+\end{color}
+
\subsection{Toward a Cryptographically Secure and Chaotic Asymmetric Cryptosystem}
\label{Blum-Goldwasser}
We finish this research work by giving some thoughts about the use of
her new public key will be $(S^0, N)$.
To encrypt his message, Bob will compute
-\begin{equation}
-c = \left(m_0 \oplus (b_0 \oplus S^0), m_1 \oplus (b_0 \oplus b_1 \oplus S^0), \hdots, m_{L-1} \oplus (b_0 \oplus b_1 \hdots \oplus b_{L-1} \oplus S^0) \right)
-\end{equation}
+%%RAPH : ici, j'ai mis un simple $
+%\begin{equation}
+$c = \left(m_0 \oplus (b_0 \oplus S^0), m_1 \oplus (b_0 \oplus b_1 \oplus S^0), \hdots, \right.$
+$ \left. m_{L-1} \oplus (b_0 \oplus b_1 \hdots \oplus b_{L-1} \oplus S^0) \right)$
+%%\end{equation}
instead of $\left(m_0 \oplus b_0, m_1 \oplus b_1, \hdots, m_{L-1} \oplus b_{L-1} \right)$.
The same decryption stage as in Blum-Goldwasser leads to the sequence
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.
+\begin{color}{red} An improvement of the Blum-Goldwasser cryptosystem, making it
+behaves chaotically, has finally been proposed. \end{color}
-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
