1 \documentclass{article}
8 \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.}
11 \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.}
19 \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.}
21 In section 1, we have added a small summary of test measurements performed with BigCrush of TestU01.
28 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.}
30 A new section (namely, Section 8.2) and a discussion at the end of Section 9.1 have been added to measure practically the security of the generator.
33 \textit{In the conclusion:
34 Reword last sentence of 1st paragraph
35 In the 2nd paragraph, change "these researches" to "this research" in "we plan to extend ..."}
44 \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).}
48 \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.}
50 A large section (Section 2 of the Annex document) has been provided, using and extending some previous works. It explains with more details why topological chaos
51 is useful to pass statistical tests. This new section contains both qualitative explanations and quantitative (experimental) evaluations.
52 Using several examples, this section illustrates that defective PRNGs are always improved, according
53 to the NIST, DieHARD, and TestU01 batteries.
56 \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]).}
58 The novelty of the approach is not in the discovery of a new kind of operator,
59 but consists in the combination of existing PRNGs. We propose to realize a
60 post-treatment based on chaotic iterations on these generators, in order to add
61 topological properties that improve their statistics while preserving their
62 cryptographical security. In this document, generators that use XOR or BBS are
63 only illustrative examples using the vectorial negation as iterative function in
64 the chaotic iterations. Theorems 1 and 2 explain how to replace this negation
65 function, that leads to well known forms of generators, by more exotic
66 ones. However, the choice of the vectorial negation to illustration our work has been
69 Indeed, to the best of our knowledge, all the generators proposed in the
70 literature mix only a few operations on previously obtained states: arithmetic
71 operations, exponentiation, shift, exclusive or. It is impossible to define a
72 fast PRNG or to prove its security when using more complicated operations, and
73 the number of such operations that are mixed is necessarily very low. Thus
74 almost all up-to-date fast or secure generators are very simple, like the BBS or
75 all the XORshift-like ones. To a certain extend, they are all similar, due to
76 the very reduced number of efficient elementary operations offered to define
81 \textit{Secondly, the periods of the 3 xorshift generators are not coprime --- this reduces the useful period of combining the sequences.}
83 We agree with the reviewer in the fact that using coprimes here will improve
84 the period of the resulted PRNG. Nevertheless the goal of this section was to
85 pass the Big Crush battery, and we achieved that with the proposed combination of
89 \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.}
91 This first generator has not been designed for security reasons, but for speed:
92 the idea was to provide a very efficient version of our former generator that
93 can pass TestU01, and linear operations are a necessity when speed with
94 pseudorandomness is desired. If what is needed is to use a fast and
95 statistically perfect PRNG, then simulations proposed in this document show that
96 this first PRNG is suitable. However, we have neither claimed nor proved that
97 this generator is secure. Indeed, we have only shown that some chaotic iteration
98 based post-treatment, like the one that uses the vectorial negation, can
99 preserve the cryptographically secure property (while adding chaos), if this
100 property has been established for the inputted generator. As the inputted
101 generator is not cryptographically secure in the example disputed by the
102 reviewer, we cannot apply this result. Indeed the first part of the document
103 does not deal with security, but it investigates the speed, chaos, and
104 statistical quality of PRNGs. A sentence has been added to clarify this point
105 at the end of Section 5.4.
109 \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).}
112 This claim is surprising, as this result is mathematically proven in the article:
113 either there is something wrong in the proof, or the generator is cryptographically
114 secure. Indeed, there is probably a misunderstanding of this notion, which does
115 not deal with the practical aspects of security. For instance, BBS is
116 cryptographically secure, but whatever the size of the keys, a brute force attack always
117 achieve to break it. It is only a question of time: with sufficiently large primes,
118 the time required to break it is astronomically large, making this attack completely
119 impracticable: being cryptographically secure is not a
120 question of key size.
123 Most theoretical cryptographic definitions are somehow an extension of the
124 notion of one-way function. Intuitively a one way function is a function
125 easy to compute but which is practically impossible to
126 inverse (i.e. from $f(x)$ it is not possible to compute $x$).
127 Since the size of $x$ is known, it is always possible to use a brute force
128 attack, that is computing $f(y)$ for all $y$'s of the good size until
129 $f(y)\neq f(x)$. Informally, if a function is one-way, it means that every
130 algorithm that can compute $x$ from $f(x)$ with a good probability requires
131 a similar amount of time to the brute force attack. It is important to
132 note that if the size of $x$ is small, then the brute force attack works in
133 practice. The theoretical security properties do not guarantee that the system
134 cannot be broken, it guarantees that if the keys are large enough, then the
135 system still works (computing $f(x)$ can be done, even if $x$ is large), and
136 cannot be broken in a reasonable time. The theoretical definition of a
137 secure PRNG is more technical than the one on one-way function but the
138 ideas are the same: a cryptographically secured PRNG can be broken
139 by a brute force prediction, but not in a reasonable time if the
140 keys/seeds are large enough.
143 Nevertheless, new arguments have been added in several places of the revision of
144 our paper, concerning more concrete and practical aspects of security, like the
145 $(T,\varepsilon)-$security notion of Section 8.2. Such a practical evaluation
146 has not yet been performed for the GPU version of our PRNG, and the reviewer is
147 right to think that these aspects are fundamental to determine whether the
148 proposed PRNG can or cannot face the attacks. A similar formula to what has been
149 computed for the BBS (as in Section 8.2) must be found in future work, to
150 measure the amount of time need by an attacker to break the proposed generator when
151 considering the parameters we have chosen (this computation is a difficult
152 task). Sentences have been added in several places (like at the end of Section
153 9.1) summarizing this.
156 \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.}
159 We hope now that, with the new sections added to the document (like Section 5), we have convinced the reviewers that adding chaotic properties in
160 existing generators can be of interest.
163 \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.}
165 Thank you for this information. However, we have already established the uniform distribution in \cite{bcgr11:ip} (recalled in Theorem 2).
168 \textit{Typos and other nitpicks:\\
169 - Blub Blum Shub is misspelled in a few places as "Blum Blum Shum";}
171 These mistakes have been corrected (sorry for that).
174 \textit{ - Page 12, right column, line 54: In "$t<<=4$", the $<<$ operation is using the `` character instead.}
177 \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. }
180 \bibliographystyle{plain}
181 \bibliography{mabase}
