X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/a12a11a39f112c043de69e8694f29b32b8c7dbc5..0be2ff183726ec026c763c2d0f9b4d3a326360fd:/prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index a32d94a..38431e5 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -172,12 +172,12 @@ 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
+is defined. From a theoretical point of view, it is proven 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
+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 based
 random generator. The generation speed is significantly weaker but, as far
@@ -207,10 +207,11 @@ 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.
+\begin{color}{red} A practical
+security evaluation is also outlined in Section~\ref{sec:Practicak evaluation}.\end{color}
 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}, \begin{color}{red} to a practical
-security evaluation in Section~\ref{sec:Practicak evaluation}, \end{color} and to an improvement of the
+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
 summarized and intended future work is presented.
@@ -672,8 +673,8 @@ N \text{ if }\sum_{i=0}^{N-1}{C^i_{32}}\leqslant{y^n}<1.\\
 
 \subsection{Improving the Speed of the Former Generator}
 
-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}
+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:
@@ -1522,7 +1523,9 @@ version\label{IR}}
 \label{algo:gpu_kernel2} 
 \end{algorithm}
 
-\subsection{Theoretical Evaluation of the Improved Version}
+\begin{color}{red}
+\subsection{Chaos Evaluation of the Improved Version}
+\end{color}
 
 A run of Algorithm~\ref{algo:gpu_kernel2} consists in an operation ($x=x\oplus t$) having 
 the form of Equation~\ref{equation Oplus}, which is equivalent to the iterative
@@ -1620,18 +1623,27 @@ as it is shown in the next sections.
 
 
 \section{Security Analysis}
+
+
+\begin{color}{red}
+This section is dedicated to the security analysis of the
+  proposed PRNGs, both from a theoretical and a practical points of view.
+
+\subsection{Theoretical Proof of Security}
 \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
+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
+  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
   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.}
+  enough, the system is secured.
+As a complement, an example of a concrete practical evaluation of security
+is outlined in the next subsection.
+\end{color}
 
 In this section the concatenation of two strings $u$ and $v$ is classically
 denoted by $uv$.
@@ -1653,7 +1665,15 @@ internal coin tosses of $D$.
 
 Intuitively, it means that there is no polynomial time algorithm that can
 distinguish a perfect uniform random generator from $G$ with a non
-negligible probability. The interested reader is referred
+negligible probability.
+\begin{color}{red}
+ An equivalent formulation of this well-known 
+security property means that it is possible 
+\emph{in practice} to predict the next bit of
+the generator, knowing all the previously 
+produced ones.
+\end{color}
+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(m)>m)$~\cite[Chapter 3.3]{Goldreich}.
@@ -1678,7 +1698,7 @@ PRNG too.
 \end{proposition}
 
 \begin{proof}
-The proposition is proved by contraposition. Assume that $X$ is not
+The proposition is proven by contraposition. Assume that $X$ is not
 secure. By Definition, there exists a polynomial time probabilistic
 algorithm $D$, a positive polynomial $p$, such that for all $k_0$ there exists
 $N\geq \frac{k_0}{2}$ satisfying 
@@ -1741,6 +1761,100 @@ proving that $H$ is not secure, which is a contradiction.
 \end{proof}
 
 
+
+\begin{color}{red}
+\subsection{Practical Security Evaluation}
+\label{sec:Practicak evaluation}
+
+Pseudorandom generators based on Eq.~\eqref{equation Oplus} are thus cryptographically secure when
+they are XORed with an already cryptographically
+secure PRNG. But, as stated previously,
+such a property does not mean that, whatever the
+key size, no attacker can predict the next bit
+knowing all the previously released ones.
+However, given a key size, it is possible to 
+measure in practice the minimum duration needed
+for an attacker to break a cryptographically
+secure PRNG, if we know the power of his/her
+machines. Such a concrete security evaluation 
+is related to the $(T,\varepsilon)-$security
+notion, which is recalled and evaluated in what 
+follows, for the sake of completeness.
+
+Let us firstly recall that,
+\begin{definition}
+Let $\mathcal{D} : \mathds{B}^M \longrightarrow \mathds{B}$ be a probabilistic algorithm that runs
+in time $T$. 
+Let $\varepsilon > 0$. 
+$\mathcal{D}$ is called a $(T,\varepsilon)-$distinguishing attack on pseudorandom
+generator $G$ if
+
+\begin{flushleft}
+$\left| Pr[\mathcal{D}(G(k)) = 1 \mid k \in_R \{0,1\}^\ell ]\right.$
+\end{flushleft}
+
+\begin{flushright}
+$ - \left. Pr[\mathcal{D}(s) = 1 \mid s \in_R \mathds{B}^M ]\right| \geqslant \varepsilon,$
+\end{flushright}
+
+\noindent where the probability is taken over the internal coin flips of $\mathcal{D}$, and the notation
+``$\in_R$'' indicates the process of selecting an element at random and uniformly over the
+corresponding set.
+\end{definition}
+
+Let us recall that the running time of a probabilistic algorithm is defined to be the
+maximum of the expected number of steps needed to produce an output, maximized
+over all inputs; the expected number is averaged over all coin flips made by the algorithm~\cite{Knuth97}.
+We are now able to define the notion of cryptographically secure PRNGs:
+
+\begin{definition}
+A pseudorandom generator is $(T,\varepsilon)-$secure if there exists no $(T,\varepsilon)-$distinguishing attack on this pseudorandom generator.
+\end{definition}
+
+
+
+
+
+
+
+Suppose now that the PRNG of Eq.~\eqref{equation Oplus} 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.
+
+Predicting the next generated bit knowing all the
+previously released ones by Eq.~\eqref{equation Oplus} is obviously equivalent to predict the
+next bit in 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}
+\begin{equation}
+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)
+\label{mesureConcrete}
+\end{equation}
+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}
+
+
 \section{Cryptographical Applications}
 
 \subsection{A Cryptographically Secure PRNG for GPU}
@@ -1864,46 +1978,41 @@ It should  be noticed that this generator has once more the form $x^{n+1} = x^n
 where $S^n$ is referred in this algorithm as $t$: each iteration of this
 PRNG ends with $x = x \wedge t$. This $S^n$ is only constituted
 by secure bits produced by the BBS generator, and thus, due to
-Proposition~\ref{cryptopreuve}, the resulted PRNG is cryptographically
-secure.
-
-
+Proposition~\ref{cryptopreuve}, the resulted PRNG is 
+cryptographically secure.
 
 \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,
-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.
-
+As stated before, even if the proposed PRNG is cryptocaphically
+secure, it does not mean that such a generator
+can be used as described here when attacks are
+awaited. The problem is to determine the minimum 
+time required for an attacker, with a given 
+computational power, to predict under a probability
+lower than 0.5 the $n+1$th bit, knowing the $n$
+previous ones. The proposed GPU generator will be
+useful in a security context, at least in some 
+situations where a secret protected by a pseudorandom
+keystream is rapidly obsolete, if this time to 
+predict the next bit is large enough when compared
+to both the generation and transmission times.
+It is true that the prime numbers used in the last
+section are very small compared to up-to-date 
+security recommends. However the attacker has not
+access to each BBS, but to the output produced 
+by Algorithm~\ref{algo:bbs_gpu}, which is quite
+more complicated than a simple BBS. Indeed, to
+determine if this cryptographically secure PRNG
+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
+a formulation similar to Eq.\eqref{mesureConcrete}
+must be established. Authors
+hope to achieve to realize this difficult task in a future
+work.
 \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
