The limit joint distributions of statistics of tests of the NIST package and their generalizations

M. P. Savelov

Diskretnaya Matematika, Tome 36 (2024) no. 2, pp. 71-116

Résumé

The limiting joint distribution of statistics, that are generalizations of statistics of tests of the NIST package and other packages, is obtained under the following hypotheses $H_0$ and $H_1$. The hypothesis $H_0$ is that the test sequence consists of independent random variables with a given polynomial distribution, and the alternative hypothesis $H_1$ corresponds to a scheme of trials in which the distribution of the test sequence approaches its distribution at $H_0$. An example of the hypothesis $H_1$ is the Markov alternative of a special form. In the special case when $H_0$ corresponds to a sequence of independent Bernoulli trials with parameter $\frac12$ and when $H_1$ approaches $H_0$, the results obtained allow us to find the limiting joint distributions of statistics of the following nine tests of the NIST package: «Monobit Test» , «Frequency Test within a Block», «Runs Test», «Test for the Longest Run of Ones in a Block», «Binary Matrix Rank Test», «Non-overlapping Template Matching Test », «Linear Complexity Test», «Serial Test» and «Approximate Entropy Test», as well as their generalizations, under hypotheses $H_0$ and $H_1$.

Détail

Keywords: joint distribution of statistical tests, «Frequency Test within a Block», «Test for the Longest Run of Ones in a Block», asymptotically uncorrelated statistics, asymptotically independent statistics.
Mots-clés : NIST, «Monobit Test»

Bibliographie

[1] Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., Leigh S., Levenson M., Vangel M., Banks D., Heckert A., Dray J., Vo S., A statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST Special Publication 800-22 Revision 1a, 2010

[2] Serov A. A., “Formuly dlya chisel posledovatelnostei, soderzhaschikh zadannyi shablon zadannoe chislo raz”, Diskretnaya matematika, 32:4 (2020), 120–136 | DOI

[3] Zubkov A. M., Serov A. A., “A natural approach to the experimental study of dependence between statistical tests”, Matem. vopr. kriptogr., 12:1 (2021), 131–142 | DOI | MR | Zbl

[4] Zubkov A. M., Serov A. A., “Testing the NIST Statistical Test Suite on artificial pseudorandom sequences”, Matem. vopr. kriptogr., 10:2 (2019), 89–96 | DOI | MR | Zbl

[5] Zubkov A. M., Serov A. A., “Experimental study of NIST Statistical Test Suite ability to detect long repetitions in binary sequences”, Matem. vopr. kriptogr., 14:2 (2023), 137–145 | DOI | MR

[6] Sulak F., Doǧanaksoy A., Uǧuz M., Koçak O., “Periodic template tests: A family of statistical randomness tests for a collection of binary sequences”, Discr. Appl. Math., 271 (2019), 191–204 | DOI | MR | Zbl

[7] Georgescu C., Simion E., “New results concerning the power of NIST randomness tests”, Proc. Romanian acad., ser. A., 18 (2017), 381–388 | MR

[8] Burciu P., Simion E., “A systematic approach of NIST statistical tests dependencies”, J. Electr. Eng., Electronics, Control and Comput. Sci., 5:15 (2019), 1–6

[9] Ryabko B. Ya., Pestunov A. I., “«Stopka knig» kak novyi statisticheskii test dlya sluchainykh chisel”, Probl. peredachi inform., 40:1 (2004), 73–78 | MR | Zbl

[10] Rukhin A. L., “Approximate entropy for testing randomness”, J. Appl. Prob., 37:1 (2000), 88–100 | DOI | MR | Zbl

[11] Karell-Albo J. A., Legón-Pérez C. M., Madarro-Capó E. J., Rojas O., Sosa-Gómez G., “Measuring independence between statistical randomness tests by mutual information”, Entropy, 22:7 (2020), 1–18 | DOI | MR

[12] Maltsev M. V., Kharin Yu. S., “O testirovanii vykhodnykh posledovatelnostei kriptograficheskikh generatorov na osnove tsepei Markova uslovnogo poryadka”, Informatika, 4 (2013), 104–111

[13] Kievets N. G., Korzun A. I., “Sravnenie statistik testov serii i approksimirovannoi entropii”, Doklady BGUIR, 3 (2014), 12–17

[14] A. L. Rukhin, “Testing randomness: a suite of statistical procedures”, Teor. Veroyatnost. i Primenen., 45:1 (2000), 137–162 | DOI | MR | Zbl

[15] Voloshko V. A., “Ob asimptoticheskikh svoistvakh semeistva $\chi^2$-testov chistoi sluchainosti dvoichnoi posledovatelnosti”, Teoreticheskaya i prikladnaya kriptografiya: materialy II Mezhdunar. nauch. konf. (Minsk, 19–20 okt. 2023 g., Belorus. gos. un-t), eds. redkol.: Yu. S. Kharin (gl. red.) [i dr.], BGU, Minsk, 2023, 15–43

[16] Maltsev M. V., Kharin Yu. S., “O statisticheskom otsenivanii mnogomernoi entropii dlya proverki kachestva kriptograficheskikh generatorov”, Teoreticheskaya i prikladnaya kriptografiya: materialy II Mezhdunar. nauch. konf. (Minsk, 19–20 okt. 2023 g., Belorus. gos. un-t), eds. redkol.: Yu. S. Kharin (gl. red.) [i dr.], BGU, Minsk, 2023, 140–147

[17] Palukha V. Yu., Kharin Yu. S., “Statisticheskoe testirovanie kriptograficheskikh generatorov na osnove slozhnoi nulevoi gipotezy”, Teoreticheskaya i prikladnaya kriptografiya: materialy II Mezhdunar. nauch. konf. (Minsk, 19–20 okt. 2023 g., Belorus. gos. un-t), eds. redkol.: Yu. S. Kharin (gl. red.) [i dr.], BGU, Minsk, 2023, 185–193

[18] Kharin Yu. S., “Statisticheskaya proverka slozhnykh gipotez ob $s$-mernom ravnomernom raspredelenii veroyatnostei dvoichnykh posledovatelnostei”, Teoreticheskaya i prikladnaya kriptografiya: materialy II Mezhdunar. nauch. konf. (Minsk, 19–20 okt. 2023 g., Belorus. gos. un-t), eds. redkol.: Yu. S. Kharin (gl. red.) [i dr.], Minsk, BGU, 2023, 261–270

[19] Voloshko V. A., Trubei A. I., “O moschnosti testov mnogomernoi diskretnoi ravnomernosti, ispolzuemykh dlya statisticheskogo analiza generatorov sluchainykh posledovatelnostei”, Zhurn. Belorus. gos. un-ta. Matem. Inf., 1 (2022), 26–37 | MR

[20] Voloshko V. A., Kharin Yu. S., Trubey A. I., “On power comparison for some tests on pure randomness under Markov high-order dependencies”, Computer Data Analysis and Modeling: Stochastics and Data Science: Proc. of the XIII Intern. Conf., 2022, 211–217

[21] Savelov M. P., “Predelnye sovmestnye raspredeleniya statistik chetyrekh kriteriev paketa NIST”, Diskretnaya matematika, 33:2 (2021), 141–154 | DOI

[22] Savelov M. P., “Predelnye sovmestnye raspredeleniya statistik trekh kriteriev paketa NIST”, Diskretnaya matematika, 33:3 (2021), 92–106 | DOI

[23] Savelov M. P., “Predelnaya teorema dlya sglazhennogo varianta spektralnogo kriteriya ravnoveroyatnosti dvoichnoi posledovatelnosti”, Diskretnaya matematika, 33:4 (2021), 132–140 | DOI | MR

[24] Savelov M. P., “Predelnoe sovmestnoe raspredelenie statistik kriteriev «Monobit test», «Frequency Test within a Block» i «Test for the Longest Run of Ones in a Block>”, Diskretnaya matematika, 34:3 (2022), 70–84 | DOI

[25] Savelov M. P., “Predelnoe sovmestnoe raspredelenie statistik kriteriev «Monobit test», «Frequency Test within a Block» i «Binary Matrix Rank Test»”, Diskretnaya matematika, 34:4 (2022), 84–98 | DOI | MR

[26] Savelov M. P., “Predelnoe sovmestnoe raspredelenie statistik kriteriev «Monobit test», «Frequency Test within a Block» i obobscheniya kriteriya «Serial Test»”, Diskretnaya matematika, 35:1 (2023), 88–106 | DOI | MR

[27] Savelov M. P., “Predelnoe sovmestnoe raspredelenie statistik kriteriev paketa NIST «Monobit Test», «Frequency Test within a Block» i obobscheniya kriteriya «Approximate Entropy Test»”, Diskretnaya matematika, 35:2 (2023), 93–108 | DOI

[28] Savelov M. P., “Predelnoe sovmestnoe raspredelenie statistik kriteriev priblizhennoi $\phi$-entropii”, Diskretnaya matematika, 35:3 (2023), 60–70 | DOI | MR

[29] Savelov M. P., “Moschnost kriteriya, osnovannogo na odnovremennom primenenii «Monobit Test», «Frequency Test within a Block» i «Serial Test»”, Diskretnaya matematika, 35:4 (2023), 79–114 | DOI | MR

[30] Savelov M. P., “Moschnost kriteriya, osnovannogo na odnovremennom primenenii «Monobit Test», «Frequency Test within a Block» i obobscheniya kriteriya «Approximate Entropy Test»”, Diskretnaya matematika, 36:1 (2024), 67–102 | DOI | MR

[31] Selivanov B. I., Chistyakov V. P., “Posledovatelnyi $\chi^2$-kriterii, postroennyi po $s$-tsepochkam sostoyanii tsepi Markova”, Diskretnaya matematika, 9:4 (1997), 127–136 | DOI | MR | Zbl

[32] Rukhin A. L., “Korrelyatsionnye matritsy tsepochek dlya markovskikh posledovatelnostei i testirovanie sluchainosti”, Teoriya veroyatn. i ee primen., 51:4 (2006), 712–731 | DOI | MR

[33] Ivchenko G. I., Medvedev Yu. I., Matematicheskaya statistika: Ucheb. posobie dlya vtuzov., Vysshaya shkola, M., 1984, 248 pp. | MR

[34] Knut D. E., Iskusstvo programmirovaniya, Poluchislennye algoritmy, v. 2, Vilyams, M., 2018, 832 pp. | MR

[35] Gustafson H., Dawson E., Nielsen L., Caelli W., “A computer package for measuring the strength of encryption algorithms”, Comp. Security, 13 (1994), 687–697 | DOI

[36] Security Requirements for Cryptographic Modules, FIPS PUB 140-1, National Institute of Standards and Technology, 1994

[37] L'Ecuyer P., Simard R., “TestU01: A C library for empirical testing of random number generators”, ACM Trans. Math. Soft., 33:22 (2007), 1–40 | DOI | MR

[38] L'Ecuyer P., Simard R., TestU01. A Software Library in ANSI C for Empirical Testing of Random Number Generators, User's guide, compact version, 2013 | Zbl

[39] Rueppel R. A., Analysis and Design of Stream Ciphers, Springer, 1986, 244 pp. | MR | Zbl