Fin

[prng_gpu.git] / reponse.tex

diff --git a/reponse.tex b/reponse.tex
index f72067080bc3c91db06b05a96ff5ef8ed0b1e24e..e8a1acf9e75f27480b8870ddb4e1e1650ba95097 100644 (file)
--- a/reponse.tex
+++ b/reponse.tex
@@ -27,7 +27,7 @@ As other tests (NIST, Diehard, SmallCrush and Crush of TestU01 ) are deemed less
 \textit{Section 9:
 The authors say they replace the xor-like PRNG with a cryptographically secure one, BBS, but then proceed to use extremely small values, as far as a cryptographer is concerned (modulus of $2^{16}$), in the computation  due  to the need to use 32 bit integers in the GPU and combine bits from multiple BBS generated values, but they never prove (or even discuss) how this  can be considered cryptographically secure due to the small  individual values. At the end of 9.1, the authors say $S^n$ is secure because it is formed from bits from the BBS generator, but do not consider if the use of such small values will lead to exhaust searches to determine individual bits. The authors either need to remove all of section 9 and or prove the resulting PRNG is cryptographically secure.}
 
 \textit{Section 9:
 The authors say they replace the xor-like PRNG with a cryptographically secure one, BBS, but then proceed to use extremely small values, as far as a cryptographer is concerned (modulus of $2^{16}$), in the computation  due  to the need to use 32 bit integers in the GPU and combine bits from multiple BBS generated values, but they never prove (or even discuss) how this  can be considered cryptographically secure due to the small  individual values. At the end of 9.1, the authors say $S^n$ is secure because it is formed from bits from the BBS generator, but do not consider if the use of such small values will lead to exhaust searches to determine individual bits. The authors either need to remove all of section 9 and or prove the resulting PRNG is cryptographically secure.}
 

-A new section has been added to measure practically the security of the generator.
+A new section (namely, the Section 9.2) has been added to measure practically the security of the generator.

 
 \bigskip
 \textit{In the conclusion:
 
 \bigskip
 \textit{In the conclusion:


@@ -48,13 +48,21 @@ Done.
 \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 
 \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
+is useful to pass statistical tests. This new section contains both qualitative explanations and quantitative (experimental) evaluations.
+ 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 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:
+The novelty of the approach is not in the discovery of a new kind of operator, but on the way to combine existing PRNGs. We propose
+to realize a post-treatment based on chaotic iterations on these generators, in order to add topological properties that improve
+their statistics while preserving their cryptographical security. In this document, generators that use XOR or BBS are only 
+illustrative examples using the vectorial negation as iterative function in the chaotic iterations. Theorems 1 and 2 explain how to
+replace this negation function, that leads to well known forms of generators, by more exotic ones. However, the choice of the vectorial
+negation for illustrations has been motivated for speed.
+
+Indeed, 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, 
 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, 


@@ -66,24 +74,29 @@ due to the very reduced number of efficient elementary operations offered to def
 
 \begin{color}{green}
 Raph, c'est pour toi ça : soit tu changes tes xorshits, soit tu justifies ton choix ;)
 
 \begin{color}{green}
 Raph, c'est pour toi ça : soit tu changes tes xorshits, soit tu justifies ton choix ;)

-\end{color}{green}
+\end{color}

 
 \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
 
 \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
+TestU01, and linear 
+operations are a necessity when speed with pseudorandomness are desired. 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
 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}
+claimed nor proved that this generator is secure. Indeed, we have only shown that some
+chaotic iteration based post-treatment, like the one that use the vectorial negation,
+can preserve the cryptographically secure property (while adding chaos), if this property has been established
+for the inputted generator. As the inputted generator is not
+cryptographically secure in the example disputed by the reviewer, we cannot apply this 
+result. Indeed the first part of the document does not deal with security,
+but it investigates the speed, chaos, and statistical quality of PRNGs.
+A sentence has been added to clarify this point at the end of Section 5.4. 
+

 
 \bigskip
 
 \bigskip

-\textit{The BBS-based generator of section 9 is anything but cryptographically secure.} 
+\textit{The BBS-based generator of section 9 is anything but cryptographically secure. 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).}
+

 
 This claim is surprising, as this result is mathematically proven in the article: 
 either there is something wrong in the proof, or the generator is cryptographically
 
 This claim is surprising, as this result is mathematically proven in the article: 
 either there is something wrong in the proof, or the generator is cryptographically


@@ -93,23 +106,23 @@ cryptographically secure, but whatever the size of the keys, a brute force attac
 achieve to break it. It is only a question of time: with sufficiently large primes,
 the time required to break it is astronomically large, making this attack completely
 impracticable in practice. To sum up, being cryptographically secure is not a
 achieve to break it. It is only a question of time: with sufficiently large primes,
 the time required to break it is astronomically large, making this attack completely
 impracticable in practice. To sum up, being cryptographically secure is not a

-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).}
-
+question of key size.

 
 

+\begin{color}{green}
+PCH, tu peux broder là-dessus?
+\end{color}

 
 \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.} 
 
 
 
 \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.} 
 
 

+We hope now that, with the new sections added to the document, we have convinced the reviewers that to add chaotic properties in 
+existing generators can be of interest.
+

 \bigskip
 \textit{On the theoretical side, you may be interested in Vladimir Anashin's work on ergodic theory on p-adic (specifically, 2-adic) numbers to prove uniform distribution and maximal period of generators. The $d_s(S, \check{S})$ distance loosely resembles the p-adic norm.}
 
 \bigskip
 \textit{On the theoretical side, you may be interested in Vladimir Anashin's work on ergodic theory on p-adic (specifically, 2-adic) numbers to prove uniform distribution and maximal period of generators. The $d_s(S, \check{S})$ distance loosely resembles the p-adic norm.}
 

-We have already established the uniform distribution in \cite{FCt}.
+Thank you for this information. However, we have already established the uniform distribution in \cite{bcgr11:ip} (recalled in Theorem 2).

 
 \bigskip
 \textit{Typos and other nitpicks:\\
 
 \bigskip
 \textit{Typos and other nitpicks:\\


@@ -123,4 +136,8 @@ These misspells have been corrected (sorry for that).
 \bigskip
 \textit{ [1] Howes, L., and Thomas, D. "Efficient random number generation and application using CUDA." In GPU Gems 3, H. Nguyen, Ed. NVIDIA, 2007, Ch. 37. }
 
 \bigskip
 \textit{ [1] Howes, L., and Thomas, D. "Efficient random number generation and application using CUDA." In GPU Gems 3, H. Nguyen, Ed. NVIDIA, 2007, Ch. 37. }
 

+
+\bibliographystyle{plain} 
+\bibliography{mabase}
+

 \end{document}
 \end{document}