Limit theorem for a smoothed version of the spectral test for testing the equiprobability of a binary sequence

M. P. Savelov

Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 132-140.

Résumé

We consider the problem of testing the hypothesis that the tested sequence is a sequence of independent random variables that take values $1$ and $-1$ with equal probability. To solve this problem, the Discrete Fourier Transform (spectral) test of the NIST package uses the statistic $T_{Fourier}$, the exact limiting distribution of which is unknown. In this paper a new statistic is proposed and its limiting distribution is established. This new statistic is a slight modification of $T_{Fourier}$. A hypothesis about the limit distribution of $T_{Fourier}$ is formulated, which is confirmed by numerical experiments presented by Pareschi F., Rovatti R. and Setti G.

Détail

Keywords: discrete Fourier transform test, spectral test, NIST, TestU01, Rademacher distribution } The author is grateful to A.M. Zubkov for constant attention. {\begin{thebibliography}{9.

Bibliographie

[1] Pareschi F., Rovatti R., Setti G., “On statistical tests for randomness included in the NIST SP800-22 test suite and based on the binomial distribution”, IEEE Trans. Inf. Forensics Secur., 7:2 (2012), 491–505 | DOI

[2] 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 the validation of random number generators and pseudo random number generators for cryptographic applications”, NIST Special Publication 800-22, Revision 1a, ed. L. E. Bassham III, NIST, April 2010

[3] Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., Leigh S., Levenson M., Vangel M., Banks D., Heckert N., Dray J., Vo S., “A statistical test suite for random and pseudorandom number generators for cryptographic applications”, NIST Special Publication 800-22, May 15, 2001

[4] Fay G., Soulier P., “The periodogram of an i.i.d. sequence”, Stoch. Proc. Appl., 92:2 (2001), 315—343 | DOI | Zbl

[5] Kokoszka P., Mikosch T., “The periodogram at the Fourier frequencies”, Stoch. Proc. Appl., 86:1 (2000), 49–79 | DOI | Zbl

[6] Serfling R., Approximation Theorems of Mathematical Statistics, John Wiley Sons, New York, 1980, 398 pp. | Zbl

[7] Freedman D., Lane D., “The empirical distribution of Fourier coefficients”, Ann. Statist., 8:6 (1980), 1244–1251 | DOI | Zbl

[8] Kim S., Umeno K., Hasegawa A., Corrections of the NIST Statistical Test Suite for Randomness, Cryptology ePrint Archive, Report 2004/018, 2004

[9] Shiryaev A.N., Veroyatnost, v. 1, 4-e izd., pererabot. i dop., MNTsMO, M., 2007, 552 pp.

[10] Angst J., Poly G., “A weak Cramer condition and application to Edgeworth expansions”, Electron. J. Probab., 22:59 (2017), 1–24

[11] Billingsley P., Convergence of Probability Measures, New York: John Wiley Sons, 1968, xii+253 pp. | Zbl

[12] Bhattacharya R.N., Rao R.R., Normal Approximation and Asymptotic Expansions, reprint edition (original edition 1976), J. Wiley Sons, New York, 1986

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

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

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

[16] Zaman J. K. M. , Ghosh R., “Review on fifteen statistical tests proposed by NIST”, J. Theor. Phys. Cryptography, 1 (2012), 18–31

[17] 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 Applied Mathematics, 271 (2019), 191–204 | DOI | Zbl

[18] Soto J., Bassham L., Randomness Testing of the Advanced Encryption Standard Finalist Candidates, NIST IR 6483, National Institute of Standards and Technology, 1999

[19] 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 (2017), 3673–3683 | DOI

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

[21] Iwasaki A., Umeno K., “A new randomness test solving problems of Discrete Fourier Transform Test”, IEICE Trans. Fundam. Electronics, Commun. and Comput. Sci., E101.A:8 (2018), 1204–1214 | DOI

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

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

[24] Okada H. and Umeno K., “Randomness evaluation with the discrete fourier transform test based on exact analysis of the reference distribution”, IEEE Trans. Inf. Forensics Secur., 12:5 (2017), 1218–1226 | DOI

[25] Chen, M., Chen H., Fan L., Zhu S., Xi W., Feng D., “A new discrete Fourier transform randomness test”, Science China Informtaion Sciences, 62 (2019)