Power of the test based on joint application of >, within a Block>> and >

M. P. Savelov

Diskretnaya Matematika, Tome 35 (2023) no. 4, pp. 79-114.

Résumé

We consider the problem of testing the hypothesis $H_0$: «tested sequence is a sequence of independent random variables having a Bernoulli distribution with parameter $\frac12$, in the scheme of series» against alternative $H_1$, which approaches $H_0$ as the sample size increases. In particular, an alternative is considered in which the tested sequence is a high-order Markov chain. In case when $H_1$ is true the limiting joint distribution of statistics $T_1, T_2, T_3$ of the following tests of the NIST package was found: «Monobit Test», «Frequency Test within a Block» and «Serial Test». The limiting value of the power of the test based on the simultaneous use of these three statistics was obtained. In the case when the alternative hypothesis does not approach $H_0$, the limiting behavior of the vector $(T_1, T_2, T_3)$ is described.

Détail

Keywords: joint distribution of statistics, NIST package, power, Markov chains, «Monobit Test», «Frequency Test within a Block», «Serial Test», asymptotically independent statistics.

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, ed. L. E. Bassham III, NIST, April 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] Zaman J. K. M. S. , Ghosh R., “Review on fifteen statistical tests proposed by NIST”, J. Theor. Phys. Cryptography, 1 (2012), 18–31

[7] 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”, Discrete Appl. Math., 271 (2019), 191–204 | DOI | MR | Zbl

[8] Soto J., Bassham L., Randomness testing of the Advanced Encryption Standard finalist candidates, NIST IR 6483, Nat. Inst. Stand. Technol., 2000

[9] Sulak F., Uǧuz M., Koçak O., Doǧanaksoy A., “On the independence of statistical randomness tests included in the NIST test suite”, Turkish J. Electr. Eng. $\$ Comput. Sci., T., 25:5 (2017), 3673–3683 | DOI | MR

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

[11] Iwasaki A., Umeno K., “Randomness test to solve Discrete Fourier Transform Test problems”, IEICE Trans. Fundam. Electronics, Commun. Comput. Sci., E101.A:8 (2018), 1204–1214 | DOI

[12] 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

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

[14] 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

[15] 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

[16] 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

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

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

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

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

[21] 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

[22] 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

[23] 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

[24] Good I. J., “The serial test for sampling numbers and other tests for randomness”, Proc. Camb. Phil. Soc., 49:2 (1953), 276–284 | DOI | MR | Zbl

[25] Good I. J., Gover T. N., “The generalized serial test and the binary expansion of $\sqrt{2}$”, J. Roy. Statist. Soc. Ser. A, 130:1 (1967), 102–107 | DOI

[26] 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

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

[28] Tikhomirova M. I., Chistyakov V. P., “O nekotorykh statistikakh tipa khi-kvadrat, funktsionalno zavisyaschikh ot otsenok neizvestnykh parametrov”, Diskretnaya matematika, 17:1 (2005), 22—34 | DOI | MR

[29] Tikhomirova M. I., Chistyakov V. P., “O dvukh statistikakh tipa khi-kvadrat, postroennykh po chastotam tsepochek sostoyanii slozhnoi tsepi Markova”, Diskretnaya matematika, 15:2 (2003), 149–159 | DOI | MR | Zbl

[30] Borovkov A. A., Teoriya veroyatnostei — 5-e izd., Knizhnyi dom «Librokom», M., 2009, 656 pp.

[31] Billingsli P., Skhodimost veroyatnostnykh mer, perev. s angl., Nauka, M., 1977, 352 pp.

[32] Dub Dzh. L., Veroyatnostnye protsessy, Izd-vo in. lit., M., 1956, 605 pp.

[33] Stepanov V. E., “Nekotorye statisticheskie kriterii dlya tsepei Markova”, Teoriya veroyatn. i ee primen., 2:1 (1957), 143–144 | Zbl

[34] Rudin W., Real and Complex Analysis, McGraw-Hill, NY, 1987, 416 pp. | MR | Zbl

[35] Bogachev V. I., Smolyanov O. G., Deistvitelnyi i funktsionalnyi analiz: universitetskii kurs, NITs «Regulyarnaya i khaoticheskaya dinamika», M.-Izhevsk, 2009, 724 pp.

[36] Kudryavtsev L. D., Kratkii kurs matematicheskogo analiza, v. 2, Fizmatlit, M., 2005, 424 pp.

[37] Ponomarev S. P., “$N^{-1}$-svoistvo otobrazhenii i uslovie $(N)$ Luzina”, Matem. zametki, 58:3 (1995), 411–418 | MR | Zbl