Using Chernoff bound to statistical tests independence checking

Abstract

In our work, we proposed, a strictly justified, method for testing independence verification and created a corresponding algorithm. We applied this algorithm to different test suits and obtained rather expected results, which indirectly confirms the correctness of our method. As we mentioned above, the proposed methods have several advantages: require fewer sequences, than the method based on approximation with normal distribution, may verify not only pairwise independence, in the most important cases, gives a more precise critical region, than the method based on Chebyshev inequality. Using this method, we show that statistical tests from the widely used suits are independent. In this connection, it is interesting to note that the older version of NIST tests (published in 1999), which consists of more tests than the recent version, turned out to be dependent. There are no explanations from the authors of the updated version, to why they removed some tests, but our very method explained this fairly.

Keywords

• eol>pseudorandom number generators
• statistical tests
• NIST STS
• cryptology1

1. Introduction

that are currently used for the analysis of crypto primitives and the generation of key data, performs a comparative analysis of them, and provides recommendations for their application. From this work, as well as similar works [ 3-6 ] we can draw the following conclusions. 1.

Currently, for various tasks in the field of cryptology, only three main sets of statistical tests are used in the world, which have practically not changed over the past 10-20 years: NIST STS SP 800-22 (developed in the 2000s, the latest modification [ 7 ]); Diehard test set [ 8 ] and its minor and few modifications (e.g., [ 9 ]); a set of 5 easy-to-implement entropy tests ENT [ 10 ] and its modern modification ENT-string [ 11 ].

One of the main issues on the way to optimizing the process of verifying the cryptographic qualities of a crypto primitive is the optimization of the set of statistical tests itself, in particular, increasing its speed [ 4,5 ]. As shown by the work [ 5 ], the most effective way to optimize an arbitrary set is to eliminate the so-called "redundant" tests from it (this was the modification [ 7 ], where the redundant test was removed). The best way to solve such questions is to use the previously introduced notion of independence of statistical tests [ 12,13 ], which has proven itself well in practical applications. The approach proposed in our works to the issue of independence of tests is significantly more general than in the work [ 5 ], because, unlike this work, analyses the independence of tests in the aggregate, and not pairwise, as in [ 5 ].

Another important issue is the choice of a set of tests that is best suited for a specific task. So, for the testing of RNG/PRNG during admission to operation and first implementation, the largest and most "demanding" set is required; for quality control of key data smaller, but one that prevents directed sorting of keys; for constant control of the allowed RNG/PRNG significantly smaller than during admission. These questions are raised in [56] with an indication of their importance, but a concrete answer to them is not provided. An important direction, which is not sufficiently covered in the scientific literature, is the use of statistical tests to check the independence of the sequence of internal states of a crypto primitive and its output sequences. Such a correlation significantly reduces the property of unpredictability of the original sequence and makes the algorithm vulnerable to statistical attacks. The method of conducting such a correlation analysis was proposed by us for the first time in [ 14 ], it can be expanded and generalized for wider use.

From all of the above, it is clear that, on the one hand, the issue of creating an effective (from the point of view of quality and speed) set of statistical tests for evaluating the cryptographic qualities of RNG/PRNG and their individual sequences is very relevant and is widely studied in modern scientific publications of a high scientific level; on the other hand, there are still many unanswered questions; one of these issues is the verification of the independence of statistical tests and the recognition of "redundant" tests that increase the time of testing but practically do not affect its results.

Intuition. For a better understanding of the problem statement, consider the following example. Let a certain package of statistical tests be used to check the cryptographic qualities of RNG/PRNG, well, for example, the NIST package consisting of 15 tests (not including subtests). consuming. Suppose that, while studying the results of testing a large set of sequences, we notice that one of the tests never makes independent decisions. Formally, this means the following: if we remove this test from the set, the set of sequences that passed all tests will not change. That is, if we create a new package, P2, by removing such a redundant test, then the set of sequences that pass all tests from set P1 coincides with the set of sequences that pass all tests from set P2. That is, by removing the test, we did not deteriorate the quality of testing, but significantly reduced its time.

Generalizing this example, we can consider a situation where the test "almost" does not make independent decisions. Or if some subset of tests from that set has tests that are redundant to that subset.

It is impossible to "manually" go through all possible subsets and try to remove unnecessary tests from them. And here the methods of statistical analysis come to the rescue. Because all the situations described above are partial cases of what can be called the dependence of tests in the aggregate, and the tools of mathematical statistics can be used to detect such dependence.

Our impact. The results obtained in this work improve the methods proposed in the works [ 12,13 ]. For example, in the work [ 12 ], a method for checking the independence of statistical tests was proposed, which uses the asymptotic approximation of the probability distribution of a certain sum of random variables by the standard normal distribution. The disadvantage of this method is that there is no estimate of the rate of convergence of the distribution to normal, except for the Barry-Essen formula [ 15 ], which is considered a rather rough estimate. Therefore, to guarantee the use of such an approximation, it is necessary to take a very large number of sequences

about 100,000, which requires a very long testing time and a large computing resource. And if, instead of approximation, Chebyshev's inequality is used, as done in the work [ 13 ], then the critical area is significantly narrowed, since this inequality is a rather rough estimate. Moreover, in some cases this method can even give trivial estimates and become unusable. In this paper, we propose another method using Chernov's inequality. It does not require as many sequences as the first named, and in some cases gives a more accurate critical region than the second. By comparing these two methods (based on the Chebyshev and Chernov inequalities), we will analyse in which cases which method gives more accurate estimates.

2. Materials and Methods

In what follows, we will use the terms Random Number Generator (RNG) and Pseudorandom Number Generator (PRNG) for such types of number generators, which use some physical source during their work (for RNG) and use only random seed and then works deterministically. Often, we will formulate statements of definitions, which may be applied to both these types. In such cases, { ( )} =1

, where ( ) = { 1( ), … , test suit, obtained from some (P)RNG G.

Let us have some set T of statistical tests, = { 1, … , }, and some set of sequences, = ( )} , = ̅1̅̅,̅̅, is a binary sequence with the lengths l fit for this

For a test and some sequence ( ), taken from the corresponding suits, we define the event ( ) = { ( ) ℎ }. For some fixed , we can consider the sequences ( ) as the realization of some random variable (RV) , which describes the behavior of the test on the sequence obtained from the generator G.

Definition 1.

are statistically independent.

In other words, the independence of the test means that the result of the application of the test Note that, according to Definition 1, the conclusion of tests independence may be different for different generators. In what follows, we also assume that the (P)RNG that we use is perfect, i.e. indistinguishable from the true random generator. There exists a lot of such generators, for example, BBS [ 16 ], or standardized generators, described in [ 17 ] and [ 18 ]. The case of the creation of tests suit, which are independent w.r.t. perfect generators, is of the most interest because only perfect generators are used in

cryptographic applications. Two perfect generators are undistinguished, so the tests which are independent w.r.t one of such generators are independent w.r.t. to any other.

G), if ,

Chernoff inequality [19].

Let 1, … , be independent random variables, which take binary values. Define Then for arbitrary ∈ (0,1) the next inequality holds:

= ∑ =1 and set

P ( X −      )  2  e 3 The proof of the next Proposition is based on Chernoff inequality.

Proposition 1.

Let statistical tests 1, … ,

sequences from the set { ( )}

=1 (the same for all tests). Then, for arbitrary ∈ (0,1), the next equality holds:

are independent. Define the RV, equal to the number of , which passed all the tests, for some preset significance level

P(  −    )   Similarly, we can define a mutual tests independence.

Definition 2. Tests from suite = { 1, … , } are called independent (w.r.t. some fixed generator G) if the corresponding RVs are mutually independent.

Let m be the number of tests in a suite, , = ̅1̅̅,̅̅̅ be the significance levels of the relevant test; n 0 be a hypothesis that all tests from the suit are mutually independent; be the probability to reject 0 under the condition that it is correct. The alternative hypothesis is complicated and may be formulated as

In what follows, we will use Chernoff bound to find the edges of critical region. There exist a lot of different versions of Chernoff inequality, among which we choose the one in the form given in

Introduce RVs Next, define RV Finally, define the RV 2 and = ∙ (1 − ) .

( ) = {

1, ℎ − ℎ ( ) = {

1, ℎ − ℎ Note that ( ) ∈ {0,1}. Using this fact and independence of RVs ( ), we get

E ( j) =  Ei( j) = (1 − )m Var ( j) = (1 − )m  (1 − (1 − )m ) ,  =  ( j)

j=1 equal to the number of sequences passed all tests. Note that = = ∙ (1 − ) and

= ∙ (1 − ) ∙ (1 − ∙ (1 − ) ).

Then apply Chernoff inequality to RV and define in a such way that the right part of the equality be equal to A; obtain the inequality for = √3 ∙

P (   −    ;  +     )  

Based on Proposal 1, we can create the next algorithm for tests mutually independence.

Chernoff inequality.

Input: number of tests m; number of tests n; set of tests = { 1, … , }; set of sequences { ( )} =1

; significance level α for testing sequences; significance level β for verifying hypothesis 0.

Step 1. Calculate and = ∙ (1 − ) and = √3 ∙ 2 .

Step 2. Calculate = ∙ .

Step 3. Applying tests from the suit to input sequences, find the number k of sequences, which passed all tests.

Step 4. Calculate credential interval as

( I1, I2 ) = ( − C,  + C ) .

Step 5. If ∈ ( 1, 2), then 0 is accepted, otherwise it is rejected.

Output:

Example 1. Verification tests independence for NIST using PRNG defined in [ 20 ] and in Appendix A in DSTU 9041:2020 [ 18 ].

The input data were chosen as: • • • • the number of the sequences is n = 300; the significance level (for each test) is α = 0.01; the number of tests in the suit is m = 41 (counting all subtests); the significance level for hypothesis 0 verification is β = 0.0001.

For this data, according to the Algorithm 1, we calculate the credential interval: suit are mutually independent. considered mutually independent.

Example 2.

( I1, I2 ) = (121.9, 275.5) It is essentially smaller than the previous one, but even for such a significance level tests may be Verification tests independence for the set of 6 simple tests described in [ 13 ]. These tests are: - frequency monobit text; - frequency bigram test; - number of series test; - the maximal series length test; - the sum of places of symbols test; - inverse test. the number of the sequences is n = 300; the significance levels (the same level for all tests) are: α = 0.001; α = 0.005; α = 0.01; α = 0.05; the number of tests in the suit is m = 6 (counting all subtests); the significance level for hypothesis 0 verification is β = 0.01.

For this data, according to the Algorithm 1, we obtained the next results. 1. For α = 0.001.

In this case  = 298.2 and     = 68.9 , so the credential interval is

( I1, I2 ) = (229.3, 300) .

The number of sequences, which passed all tests, is 300. We can conclude that the tests from the suit are mutually independent.

2. For α = 0.005.

In this case  = 291.1 and     = 68 , so the credential interval is

( I1, I2 ) = (223.1, 300) .

The number of sequences, which passed all tests, is 298. We can conclude that the tests from the suit are mutually independent.

3. For α = 0.01.

In this case  = 282.4 and     = 67 , so the credential interval is

( I1, I2 ) = (215.4, 300) .

The number of sequences, which passed all tests, is 295. We can conclude that the tests from the suit are mutually independent.

4. For α = 0.05.

In this case  = 221 and     = 59.3 , so the credential interval is

( I1, I2 ) = (161.7, 280) .

The number of sequences, which passed all tests, is 249. We can conclude that the tests from the suit are mutually independent.

As we see, tests may be considered as independent even for relatively large value of . Indeed, the number of tests is relatively small, and in such cases tests usually are independent. So in these examples we obtained expected results, which indirectly confirms the correctness of the method and corresponding algorithm.

Now we are going to show that the proposed method of test independence verification may give tighter credential intervals, than a similar method based on Chebyshev inequality [ 13 ].

In our designations, if ≤ 0.05 and the values α and m are such that (1 − ) < 0.442, then the critical region, obtained using Chernoff inequality, is larger, than using Chebyshev one.

Proposition 2.

According to Proposition 1, the hypothesis 0 is accepted if where 1 = ∙ , = ∙ (1 − ) , and = √3 ∙ 2 .

We may rewrite 1 as

If we use Chebyshev inequality instead of Chernoff inequality, we get the other credential k ( − С1,  + С )

1 , С = 1 3  ln  2 

  = 3   ln k  ( − С2,  + С ) 2 , 2  .

 (1 − (1 − )m )  . interval: where (using (1))

C = 2

Var =    1 −    

 n  = n  (1 − )m  (1 − (1 − )m ) .

In these designations to prove that critical region with 1 is larger than with 2 is the same as to prove that 1 < 2, or that the next inequality holds: 3  ln

 2  2 ln 2  2    ln 40 40

First, note that for ≥ the function ln decreases if x increases. Then, for ≤ ≤ (for some ∈ ) we have ln ≤

ln .

In our conditions, ≤ 0.05, then for = 2 ≥ 40 we have: and

On the other hand, (1 − (1 − )m )   1 − (1 − )  =    0.558   according to the proposition assumption, and the Proposition is proved.

Example 3: the conditions of the Proposition 2 hold in such cases: the value of preferable.

Conclusions

As common recommendations, we may say that the method based on Chernoff inequality works better for the cases when we have a small value of and/or relatively large (w.r.t. ) and/or large number m of tests. Note that in the overwhelming majority of applications, the value of is chosen as 0.001 or even smaller, which is just the case for applying the proposed method. But in case when the number of tests is relatively small (less than 10, for example), and at the same time is not large than 0.01, the method which uses Chebyshev inequality is more Tests independence is a very important and useful property. First, by avoiding using redundant tests, we may significantly reduce testing time, so may create key data for users more efficiently. Secondly, if the tests being applied are independent, we may, with some insignificant error, predict, what proportion of sequences will be rejected, and, therefore, understand how many sequences we need to generate to have the required volume of key data. For example, if we need to have 1000 key sequences, and know that the tests which are used are independent, then, if the significance level is , the proportion of rejected sequences is, on average, = 1 − (1 − ) , where m is the number of tests. Then to get k sequences for key data, we need to generate about (1− ) sequences.

Note that in the NIST document [ 7 ] one can find some considerations about the importance of considered as sounded: it consists of calculating P-values for each pair test/sequence, then creating a matrix of these P-values (one row corresponds to one test) and checking the linear independence of the rows. This approach has no justification, and it seems very unlikely that for dependent tests such rows will be linearly dependent.

In our work, we proposed, a strictly justified, method for testing independence verification and created a corresponding algorithm. We applied this algorithm to different test suits and obtained rather expected results, which indirectly confirms the correctness of our method. As we mentioned above, the proposed methods have several advantages: • • • require fewer sequences, than the method based on approximation with normal distribution [ 12 ]; some ideas from [ 22 ]; may verify not only pairwise independence, as methods, proposed in [ 21 ] and based on in the most important cases, gives a more precise critical region, than the method based on Chebyshev inequality [ 13 ].

Using this method, we show that statistical tests from the widely used suits are independent. In this connection, it is interesting to note that the older version of NIST tests (published in 1999), which consists of more tests than the recent version, turned out to be dependent. There are no explanations from the authors of the updated version, to why they removed some tests, but our very method explained this fairly.

Also note that we could not obtain the corresponding numerical examples for DIEHARD suit [ 9 ]. The matter is that the tests in this suit are created in other way, which gives no opportunity to get one result for one sequence. For such suit the method of results processing should be completely different.

As we mentioned in Definition 1, the notion of test independence may depend on the type of generator, more precisely on the type and properties of probability distribution on its outputs. Though we develop the methodic for most common use case, such as perfect generator testing, the similar approaches may be developed for other cases of output distribution. Generally speaking, for different types of output distributions we may obtain different sets of independent tests. But our experimental results, which we provided for generators with different types of output distributions (we did not include extend version of such investigation because of volume restriction) shows that two test suits, described above, turned out to be independent for several non-perfect types of generators, which output distribution was artificially biased from equiprobable. Of course, such independence, but show that the test suit may be the same for different cases of generators.

The other interesting question, directly connected with the topic of presented research, is the next: when the test suit turned out to contain dependent tests, what tests should be considered as redundant and removed from the suit? Informally speaking, our answer is: such tests, that make passing all tests will not change essentially, so the mutual first type error will remain the same too. Usually, the number of the tests in suit allows to check all tests decisions and to remove redundant

Acknowledgements

The results of this work were obtained within the project 2023.04/0020 Development of methods and layout of the "DEMETRA" ARM for constant and periodic control of the functioning of cryptographic applications using statistical methods.

Declaration on Generative AI

The author(s) have not employed any Generative AI tools.

References

[1] Cabinet of Ministers of Ukraine. ( 2021 ). Cybersecurity Strategy of Ukraine. Secure Cyberspace is the Key to the Successful Development of the Country . [Online]. Retrieved from https://zakon.rada.gov.ua/laws/show/447/2021#n12

[2] E. Almaraz Luengo , Statistical tests suites analysis methods . Cryptographic recommendations, Cryptologia 48 ( 3 ) ( 2023 ) 219 251. doi: 10 .1080/01611194. 2022 . 2155093 .

[3] E. Almaraz Luengo , J. Román Villaizán , Cryptographically Secured Pseudo-Random Number Generators: Analysis and Testing with NIST Statistical Test Suite , Mathematics 11 ( 23 ): 4812 ( 2023 ). doi: 10 .3390/math11234812 Chakraborty, V. Matyas , P. Schaumont, (Eds.), Security, Privacy, and Applied Cryptography Engineering. SPACE 2014 , volume 8804 of Lecture Notes in Computer Science, Springer, Cham, 2014 , pp. 272 284 . doi: 10 .1007/978-3- 319 -12060-7_ 18 .

[5] E. A. Luengo , B.A. Olivares , L. J. G. Villalba , J. Hernandez-Castro , Further analysis of the statistical independence of the NIST SP 800-22 randomness tests , Applied Mathematics and Computation 459 128222 ( 2023 ). doi: 10 .1016/J.AMC. 2023 .128222

[6] E.A. Luengo , L.J.G. Villalba, Recommendations on Statistical Randomness Test Batteries for Cryptographic Purposes , ACM Comput. Surv . 54 , 4 , Article 80 ( 2021 ). pp. 1 - 34 . doi: 10 .1145/3447773

[7] L.E. Bassham III , A.L. Rukhin , J. Soto , J.R. Nechvatal , M.E. Smid , E.B. Barker and others, A statistical test suite for random and pseudorandom number generators for cryptographic applications , NIST Special Publication 800 -22, Revision 1a , ( 2010 ). URL: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800- 22r1a .pdf

[8] G. Marsaglia , The Marsaglia random number CDROM including the diehard battery of tests of randomness , ( 2008 ). http://www. stat. fsu. edu/pub/diehard/.

[9] R.G. Brown , D. Eddelbuettel , D. Bauer , Dieharder. Duke University Physics Department Durham NC 27708- 0305 ( 2018 ).

[10] J. Walker , A pseudorandom number sequence test program , ( 2008 ). https://www.fourmilab.ch/random/

[11] E. Almaraz Luengo , B. Alaña Olivares , L.J. García Villalba , J. Hernandez-Castro , D. HurleySmith, StringENT test suite: ENT battery revisited for efficient P value computation , Journal of Cryptographic Engineering 13 ( 2 ) ( 2023 ) 235 - 249 . doi: 10 .1007/s13389-023-00313-5

[12] L. Kovalchuk , V. Bezditnyi , A statistical tests independence checking intended for cryptographic properties of RNG estimation , Ukrainian Information Security Research Journal 2 ( 29 ) ( 2006 ) 18 - 23 .

[13] R. Kochana , L. Kovalchuk , O. Korchenko , N. Kuchynska , Statistical Tests Independence Verification Methods, Procedia Computer Science Volume 192 ( 2021 ). 2678 - 2688 . doi: 10 .1016/j.procs. 2021 . 09 .038.

[14] L.V. Kovalchuk , I.V. Koriakov , A.N. Alekseychuk , Krip: High-Speed Hardware-Oriented Stream Cipher Based on a Non-Autonomous Nonlinear Shift Register , Cybernetics and Systems Analysis 59 ( 1 ) ( 2023 ). 16 - 26 . doi: 10 .1007/s10559-023-00538-6

[15] W. Feller . An introduction to probability theory and its applications , Vol. 2 (Vol. 81 ). John Wiley & Sons. ( 1991 ).

[16] V. Pareek , An overview of cryptographically secure pseudorandom number generators and BBS." International Journal of Computer Applications (IJCA)(0975 8887) ( 2014 ).

[17] Information technologies . Cryptographic protection of information. A digital signature based on elliptic curves. Formation and verification , DSTU 4145- 2002 .

[18] Information technologies . Cryptographic protection information. Short message encryption algorithm based on Edwards twisted elliptic curves , DSTU 9041 : 2020 .

[19] M. Goemans , Chernoff bounds, and some applications, 18.310 lecture notes February 21 , 2015 . URL: https://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf

[20] Information technologies . Cryptographic protection of information. Algorithm of symmetric block transformation , DSTU 7624 : 2014 .

[21] Kovalchuk L. , Davydenko A. , Bespalov O . New statistical criteria for checking independence of bit random variables and sequences . In Advances in Information-Control Systems and Technologies, ODESA , 2024 , p. 344 - 362 . ISBN 978-617-7857-33-3.

[22] T.W. Anderson , An Introduction to Multivariate Statistical Analysis , 3rd Edition , Wiley, ( 2003 ) 380 - 410 .