From 4797365cf4607caea2473f7ce2f4fe6c3bbf9c51 Mon Sep 17 00:00:00 2001 From: cguyeux Date: Mon, 3 Sep 2012 22:04:37 +0200 Subject: [PATCH] fdsfs --- prng_gpu.tex | 10 ++++++++-- reponse.tex | 28 ++++++++++++++++++++++++++++ 2 files changed, 36 insertions(+), 2 deletions(-) diff --git a/prng_gpu.tex b/prng_gpu.tex index 39cee40..f985e03 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -1279,7 +1279,7 @@ this generator will be simply referred as CIPRNG, or ``the proposed PRNG'', if t 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 @@ -1358,7 +1358,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 -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} diff --git a/reponse.tex b/reponse.tex index 865604e..f720670 100644 --- a/reponse.tex +++ b/reponse.tex @@ -47,15 +47,41 @@ Done. \bigskip \textit{There seems to have been no effort in showing how the new PRNG improves on a single (say) xorshift generator, considering the slowdown of calling 3 of them per iteration (cf. Listing 1). This could be done, if not with the mathematical rigor of chaos theory, then with simpler bit diffusion metrics, often used in cryptography to evaluate building blocks of ciphers.} +A large section (Section 5) has been added, using and extending some previous works, explains with more detail why topological chaos +is useful to pass statistical tests. Using several examples, this section illustrates that defective PRNGs are always improved, according +to the NIST, DieHARD, and TestU01 batteries. + \bigskip \textit{The generator of Listing 1, despite being proved chaotic, has several problems. First, it doesn't seem to be new; using xor to mix the states of several independent generators is standard procedure (e.g., [1]).} +To the best of our knowledge, all the generators proposed in the literature mix only a few operations on previously obtained states: +arithmetic operations, exponentiation, shift, exclusive or. It is impossible to define a fast PRNG or to prove its security when +using more complicated operations, and the number of such operations that are mixed is necessary very low. Thus almost all + up-to-date fast or secure generators are very simple, like the BBS or all the XORshift-like ones. In a certain extend, they are all similar, +due to the very reduced number of efficient elementary operations offered to define them. + + \bigskip \textit{Secondly, the periods of the 3 xorshift generators are not coprime --- this reduces the useful period of combining the sequences.} +\begin{color}{green} +Raph, c'est pour toi ça : soit tu changes tes xorshits, soit tu justifies ton choix ;) +\end{color}{green} + \bigskip \textit{Thirdly, by combining 3 linear generators with xor, another linear operation, you still get a linear generator, potentially vulnerable to stringent high-dimensional spectral tests.} +This first generator has not been designed for security reasons, but for speed: the +idea was to provide a very efficient version of our former generator that can pass +TestU01. If the desire is to use a fast and statistically perfect PRNG, then simulations +proposed in this document show that this first PRNG is suitable. However, we have neither +claimed nor proved that this generator is secure. Indeed, to the authors opinion, +linear operations are a necessity when speed with pseudorandomness are only desired. +A sentence has been added to clarify this point \begin{color}{green} Il faudrait ajouter +cette phrase fin de la section 6 (je l'ai fait pour la fin de la section 5.4). +Dire que pour l'instant, on veut juste avoir de la rapidité sans biais +statistique, que la sécurité viendra après.\end{color} + \bigskip \textit{The BBS-based generator of section 9 is anything but cryptographically secure.} @@ -74,6 +100,8 @@ question of key size, \bigskip \textit{A 16-bit modulus (trivially factorable) gives out a period of at most $2^{16}$, which is neither useful nor secure. Its speed is irrelevant, as this generator as no practical applications whatsoever (a larger modulus, at least 1024-bit long, might be useful in some situations, but it will be a terrible GPU performer, of course).} + + \bigskip \textit{To sum it up, while the theoretical part of the paper is interesting, the practical results leave much to be desired, and do not back the thesis that chaos improves some quality metric of the generators.} -- 2.39.5