]> AND Private Git Repository - prng_gpu.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Fin de la retouche de la réponse
authorcguyeux <cguyeux@iut-bm.univ-fcomte.fr>
Wed, 12 Sep 2012 14:47:00 +0000 (16:47 +0200)
committercguyeux <cguyeux@iut-bm.univ-fcomte.fr>
Wed, 12 Sep 2012 14:47:00 +0000 (16:47 +0200)
reponse.tex

index 8d1a2ab2b22b0a4afe614a048b20e842756303dc..5a762c2000ab3b9d77fee4ad51a92069f1d0551c 100644 (file)
@@ -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.}
 
-A new section (namely, the Section 9.2) has been added to measure practically the security of the generator.
+A new section (namely, the Section 8.2) and a discussion at the end of Section 9.1 have been added to measure practically the security of the generator.
 
 \bigskip
 \textit{In the conclusion:
@@ -47,7 +47,7 @@ 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 
+A large section (Section 5) has been added, using and extending some previous works. It explains with more detail why topological chaos 
 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.
@@ -72,9 +72,10 @@ due to the very reduced number of efficient elementary operations offered to def
 \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}
+We agree with the reviewer in the fact that using coprimes here will improve
+the period of the resulted PRNG. Nevertheless the goal of this section was to
+pass the Big Crush battery, and we achieve that with proposed combination of
+the three XORshifts. 
 
 \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.}
@@ -105,7 +106,7 @@ not deal with the practical aspects of security. For instance, BBS is
 cryptographically secure, but whatever the size of the keys, a brute force attack always
 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
+impracticable: being cryptographically secure is not a
 question of key size.
 
 \begin{color}{green}
@@ -129,11 +130,24 @@ ideas are the same: a cryptographically secured PRNG can be broken
  keys/seeds are large enough.
 \end{color}
 
+Nevertheless, new arguments have been added in several places of the revision of our paper, 
+concerning more concrete and practical aspects of security, like the 
+$(T,\varepsilon)-$security notion of Section 8.2. Such a practical evaluation
+has not yet been performed for the GPU version of our PRNG, and the reviewer
+has true when thinking that these aspects are fundamentals to determine whether
+the proposed PRNG can face or not attacks in practice. A formula similar to what
+has been computed for the BBS (as in Section 8.2) must be found in future work,
+to measure how much time an attacker must have to break the proposed generator
+when considering the parameters we have chosen (this computation is a difficult
+task). 
+Sentenses have been added in several places (like at the end of Section 9.1)
+summarizing this.
+
 \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 
+We hope now that, with the new sections added to the document (like the Section 5), we have convinced the reviewers that to add chaotic properties in 
 existing generators can be of interest.
 
 \bigskip