X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/7c9a1a3c4f4b214a0b8075ed65fa73f25512eddb..11f1ec59d1b84c34db2d61d773d6fe2c9a480938:/reponse.tex?ds=sidebyside

diff --git a/reponse.tex b/reponse.tex
index 3ec5213..0ffb36a 100644
--- a/reponse.tex
+++ b/reponse.tex
@@ -1,25 +1,33 @@
 \documentclass{article}
-
+\usepackage{color}
 
 \begin{document}
 \section{Editor}
 
-As the reviewers point out, the paper is well written, is interesting, but there are some major concerns about both the practical aspects of the paper, as well as more theoretical aspects.  While the paper has only been reviewed by two reviewers, their concerns are enough to recommend that the author consider them carefully and then resubmit this paper as a new paper.
+\bigskip
+\textit{As the reviewers point out, the paper is well written, is interesting, but there are some major concerns about both the practical aspects of the paper, as well as more theoretical aspects.  While the paper has only been reviewed by two reviewers, their concerns are enough to recommend that the author consider them carefully and then resubmit this paper as a new paper.}
 
-Most of the issues raised are related to cryptography, and not to the acceleration work on a GPU.  The issue may be that during their preparation of this paper the authors were too focused on the acceleration work, and did not spend enough time being precise about the cryptography discussion.  The two reviewers are experts on cryptography, as well as acceleration techniques, and the review indicate that the analysis needs to be strengthened.
+\bigskip
+\textit{Most of the issues raised are related to cryptography, and not to the acceleration work on a GPU.  The issue may be that during their preparation of this paper the authors were too focused on the acceleration work, and did not spend enough time being precise about the cryptography discussion.  The two reviewers are experts on cryptography, as well as acceleration techniques, and the review indicate that the analysis needs to be strengthened.}
 
 
 
 \section{Reviewer: 1}
 
 
-Comments:
-The authors should include a summary of  test measurements showing their method passes the test sets mentioned (NIST, Diehard, TestU01) instead of the one sentence saying it passed that is in section 1.
+\bigskip
+\textit{The authors should include a summary of  test measurements showing their method passes the test sets mentioned (NIST, Diehard, TestU01) instead of the one sentence saying it passed that is in section 1.}
+
+\begin{color}{red} Raph, c'est pour toi ça.\end{color}
 
 
-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. 
+\bigskip
+\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.
+
+\bigskip
 \textit{In the conclusion:
 Reword last sentence of 1st paragraph
 In the 2nd paragraph, change "these researches" to "this research" in  "we plan to extend ..."}
@@ -30,19 +38,59 @@ Done.
 \section{Reviewer: 2}
 
 
-Comments:
-The paper is, overall, well written and clear, with appropriate references to the relevant concepts and prior work. The motivation of the work, however, is not quite clear: the authors present (provable) chaotic properties of a PRNG as a security improvement, but provide no convincing argument beyond opinion (or hope). 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.
+\bigskip
+\textit{The paper is, overall, well written and clear, with appropriate references to the relevant concepts and prior work. The motivation of the work, however, is not quite clear: the authors present (provable) chaotic properties of a PRNG as a security improvement, but provide no convincing argument beyond opinion (or hope).}
+
+
+\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.}
+
+\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]).}
+
+\bigskip
+\textit{Secondly, the periods of the 3 xorshift generators are not coprime --- this reduces the useful period of combining the sequences.}
+
+\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.}
+
+\bigskip
+\textit{The BBS-based generator of section 9 is anything but cryptographically secure.} 
+
+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
+secure. Indeed, there is probably a misunderstanding of this notion, which does
+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
+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.} 
 
-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]). Secondly, the periods of the 3 xorshift generators are not coprime --- this reduces the useful period of combining the sequences. 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.
 
-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).
+\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.}
 
-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. 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}.
 
-Typos and other nitpicks:
- - Blub Blum Shub is misspelled in a few places as "Blum Blum Shum";
- - Page 12, right column, line 54: In "t<<=4", the << operation is using the « character instead.
+\bigskip
+\textit{Typos and other nitpicks:\\
+ - Blub Blum Shub is misspelled in a few places as "Blum Blum Shum";}
+ 
+These misspells have been corrected (sorry for that).
+ 
+\bigskip
+\textit{ - Page 12, right column, line 54: In "$t<<=4$", the $<<$ operation is using the `` character instead.}
 
- [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. }
 
 \end{document}