add format parallel comp

[prng_gpu.git] / reponse.tex

diff --git a/reponse.tex b/reponse.tex
index e8a1acf9e75f27480b8870ddb4e1e1650ba95097..dbe927ad7a6689b8467ea72fa6f093e775d3dbbb 100644 (file)
--- a/reponse.tex
+++ b/reponse.tex
@@ -18,16 +18,16 @@
 \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.}
 
 \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} In section 1, we have added a small summary of test measurements performed with BigCrush of TestU01.
-As other tests (NIST, Diehard, SmallCrush and Crush of TestU01 ) are deemed less selective, in this paper we did not use them.
-\end{color}
+In section 1, we have added a small summary of test measurements performed with BigCrush of TestU01.
+
+

 
 
 \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.}
 
 
 
 \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 (namely, the Section 9.2) has been added to measure practically the security of the generator.
+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.

 
 \bigskip
 \textit{In the conclusion:
 
 \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.}
 
 \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 details 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.
 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.


@@ -55,43 +55,54 @@ 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]).}
 
 \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]).}
 

-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, 
-due to the very reduced number of efficient elementary operations offered to define them.
+The novelty of the  approach is not in the discovery of  a new kind of operator,
+but  consists in  the combination  of 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  to illustration our work has been
+motivated by 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  necessarily very  low. Thus
+almost all up-to-date fast or secure generators are very simple, like the BBS or
+all the  XORshift-like ones. To 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.}
 
 
 
 \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 achieved that with the 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.}
 
 
 \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, 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
-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. 
+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,  and linear  operations  are  a  necessity when  speed  with
+pseudorandomness  is  desired.  If  what  is   needed  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, we have only shown that some chaotic iteration
+based  post-treatment,  like the  one  that  uses  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


@@ -105,18 +116,47 @@ 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
 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.
 
 question of key size.
 

-\begin{color}{green}
-PCH, tu peux broder là-dessus?
-\end{color}
+
+Most theoretical cryptographic definitions are somehow an extension of the
+notion of one-way function. Intuitively a one way function is a function
+ easy to compute but  which is practically impossible to
+inverse (i.e. from $f(x)$ it is not possible to compute $x$). 
+Since the size of $x$ is known, it is always possible to use a brute force
+attack, that is computing $f(y)$ for all $y$'s of the good size until
+$f(y)\neq f(x)$. Informally, if a function is one-way, it means that every
+algorithm that can compute $x$ from $f(x)$ with a good probability requires
+a similar amount of time to the brute force attack. It is important to
+note that if the size of $x$ is small, then the brute force attack works in
+practice. The theoretical security properties do not guarantee that the system
+cannot be broken, it guarantees  that if the keys are large enough, then the
+system still works (computing $f(x)$ can be done, even if $x$ is large), and
+cannot be broken in a reasonable time. The theoretical definition of a
+secure PRNG is more technical than the one on one-way function but the
+ideas are the same: a cryptographically secured PRNG can be broken 
+ by a brute force prediction, but not in a reasonable time if the
+ keys/seeds are large enough.
+
+
+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 is
+right  to think  that these  aspects are  fundamental to  determine  whether the
+proposed PRNG can or cannot face the attacks. A similar formula to what has been
+computed  for the  BBS (as  in Section  8.2) must  be found  in future  work, to
+measure the amount of time need by an attacker to break the proposed generator when
+considering  the parameters  we have  chosen  (this computation  is a  difficult
+task).  Sentences 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.} 
 
 
 
 \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 Section 5), we have convinced the reviewers that adding chaotic properties in 

 existing generators can be of interest.
 
 \bigskip
 existing generators can be of interest.
 
 \bigskip


@@ -128,7 +168,7 @@ Thank you for this information. However, we have already established the uniform
 \textit{Typos and other nitpicks:\\
  - Blub Blum Shub is misspelled in a few places as "Blum Blum Shum";}
  
 \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).
+These mistakes have been corrected (sorry for that).

  
 \bigskip
 \textit{ - Page 12, right column, line 54: In "$t<<=4$", the $<<$ operation is using the `` character instead.}
  
 \bigskip
 \textit{ - Page 12, right column, line 54: In "$t<<=4$", the $<<$ operation is using the `` character instead.}