The National Institute of Standards and Technology (NIST) document is a list of fifteen tests for estimating the probability of signal randomness degree. Test number six in the NIST document is the Discrete Fourier Transform (DFT) test suitable for stationary incoming sequences. But, for cases where the input sequence is not stationary, the DFT test provides inaccurate results. For these cases, test number seven and eight (the Non-overlapping Template Matching Test and the Overlapping Template Matching Test) of the NIST document were designed to classify those non-stationary sequences. But, even with test number seven and eight of the NIST document, the results are not always accurate. Thus, the NIST test does not give a proper answer for the non-stationary input sequence case. In this paper, we offer a new algorithm or test, which may replace the NIST tests number six, seven and eight. The proposed test is applicable also for non-stationary sequences and supplies more accurate results than the existing tests (NIST tests number six, seven and eight), for non-stationary sequences. The new proposed test is based on the Wigner function and on the Generalized Gaussian Distribution (GGD). In addition, this new proposed algorithm alarms and indicates on suspicious places of cyclic sections in the tested sequence. Thus, it gives us the option to repair or to remove the suspicious places of cyclic sections (this part is beyond the scope of this paper), so that after that, the repaired or the shortened sequence (origi nal sequence with removed sections) will result as a sequence with high probability of random degree.
KeywordsWigner DistributionShape ParameterGeneralized Gaussian DistributionRandom Number GeneratorTrue Random Number GeneratorPseudo Random Number Generator
Martin, H., Peris-Lopez, P., Tapiador, J. E. and San Millan, E. (2016) A New TRNG Based on Coherent Sampling with Self-Timed Rings. Transactions on Industrial Informatics, 12, 91-100. https://doi.org/10.1109/TII.2015.2502183
Inayah, K., Sukmono, B. E., Purwoko, R. and Indarjani, S. (2013) Insertion Attack Effects on Standard PRNGs ANSI X9.17 and ANSI X9.31 Based on Statistical Distance Tests and Entropy Difference Tests. 2013 International Conference on Computer, Control, Informatics and Its Applications, Jakarta, 19-21 November 2013, 219-224. https://doi.org/10.1109/IC3INA.2013.6819177
Soorat, R., Madhuri, K. and Vudayagiri, A. (2017) Hardware Random Number Generator for Cryptography. NANOSYSTEMS: Physics, Chemistry, Mathematics, 8, 600-605. https://doi.org/10.17586/2220-8054-2017-8-5-600-605 https://www.researchgate.net/publication/282639432_Hardware_Random_ number_Generator_for_cryptography#fullTextFileContent
Mathew, S.K., Srinivasan, S., Anders, M.A., Kaul, H., Hsu, S.K., Sheikh, F., Agarwal, A., Satpathy, S. and Krishnamurthy, R.K. (2012) 2.4 Gbps, 7 mW All-Digital PVT-Variation Tolerant True Random Number Generator for 45 nm CMOS High-Performance Microprocessors. IEEE Journal of Solid-State Circuits, 47, 2807-2821. https://doi.org/10.1109/JSSC.2012.2217631
Goll, M. and Gueron, S. (2018) Randomness Tests in Hostile Environments. IEEE Transactions on Dependable and Secure Computing, 15, 289-294. https://doi.org/10.1109/TDSC.2016.2537799
Petrie, C.S. and Alvin Connelly, J. (1999) The Sampling of Noise for Random Number Generation. IEEE International Symposium on Circuits and Systems, Orlando, 30 May-2 June 1999, 26-29. https://doi.org/10.1109/ISCAS.1999.780085
Soucarros, M., Canovas-Dumas, C., Cldire, J., Elbaz-Vincent, P. and Ral, D. (2011) Influence of the Temperature on True Random Number Generators. 2011 IEEE International Symposium on Hardware-Oriented Security and Trust, San Diego, 5-6 June 2011, 24-27. https://doi.org/10.1109/HST.2011.5954990
Bahadur, V., Selvakumar Vijendran, D. and Sobha, P.M. (2016) Reconfigurable Side Channel Attack Resistant True Random Number Generator. International Conference on VLSI Systems, Architectures, Technology and Applications, Bengaluru, 10-12 January 2016, 1-6. https://doi.org/10.1109/VLSI-SATA.2016.7593048
Prokofiev, A.O., Chirkin A.V. and Bukharov V.A. (2018) Methodology for Quality Evaluation of PRNG, by Investigating Distribution in a Multidimensional Space. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, Moscow, 29 January-1 February 2018, 355-357. https://doi.org/10.1109/EIConRus.2018.8317105
Prokofiev, A.O. (2019) Development Principles and Classification of PRNG Graphical Tests. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, Saint Petersburg and Moscow, 28-31 January 2019, 295-300. https://doi.org/10.1109/EIConRus.2019.8657165
Pareschi, F., Rovatti, R. and Setti, G. (2007) Second-Level NIST Randomness Tests for Improving Test Reliability. IEEE International Symposium on Circuits and Systems, New Orleans, 27-30 May 2007, 1437-1440. https://doi.org/10.1109/ISCAS.2007.378572
Márton, K., Homan, M., Suciu, A. and Rasa, I. (2013) The Histogram Test for Randomness Assessment. 2013 RoEduNet International Conference 12th Edition: Networking in Education and Research, Iasi, 26-28 September 2013, 1-5. https://doi.org/10.1109/RoEduNet.2013.6714183
Zhu, S. (2015) A Randomness Test Based on the Distribution of Position for Pre-Specified Pattern. 2015 International Conference on Computer Science and Mechanical Automation, Hangzhou, 23-25 October 2015, 166-169. https://doi.org/10.1109/CSMA.2015.40
Fan, Y.T. and Su, G.P. (2014) A New Testing Method of Randomness for True Random Sequences. 2014 IEEE 5th International Conference on Software Engineering and Service Science, Beijing, 27-29 June 2014, 537-540. https://doi.org/10.1109/ICSESS.2014.6933624
Fischer, T. (2018) Testing Cryptographically Secure Pseudo Random Number Generators with Artificial Neural Networks. IEEE International Conference on Trust, Security and Privacy in Computing and Communications/12th IEEE International Conference on Big Data Science and Engineering, New York, 1-3 August 2018, 1214-1223. https://doi.org/10.1109/TrustCom/BigDataSE.2018.00168
Qi, M. and Dong, J. (2009) Research and Application of Entropy in the Sequence Randomness Test. 2009 Asia-Pacific Conference on Computational Intelligence and Industrial Applications, Wuhan, 28-29 November 2009, 224-227. https://doi.org/10.1109/PACIIA.2009.5406638
Mrton, K., Bja, V. and Suciu, A. (2014) Parallel Implementation of the Matrix Rank Test for Randomness Assessment. IEEE 10th International Conference on Intelligent Computer Communication and Processing, Cluj-Napoca, 4-6 September 2014, 317-321. https://doi.org/10.1109/ICCP.2014.6937015
Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel M., Banks, D., Heckert, A., Dray, J. and San, V. (2010) A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. National Institute of Standards and Technology, Gaithersburg, 2.1-2.40. https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf
Georgescu, C., Simion, E., Nita, A.P. and Toma, A. (2017) A View on NIST Randomness Tests (In)Dependence. International Conference on Electronics, Computers and Artificial Intelligence, Targoviste, 29 June-1 July 2017, 1-4. https://doi.org/10.1109/ECAI.2017.8166460
Hoţoleanu, D., Creţ, O., Suciu, A., Gyorfi, T. and Văcariu, L. (2010) Real-Time Testing of True Random Number Generators through Dynamic Reconfiguration. 2010 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, Lille, 1-3 September 2010, 247-250. https://doi.org/10.1109/DSD.2010.56
Okada, H. and Umeno, K. (2017) Randomness Evaluation with the Discrete Fourier Transform Test Based on Exact Analysis of the Reference Distribution. IEEE Transactions on Information Forensics and Security, 12, 1218-1226. https://doi.org/10.1109/TIFS.2017.2656473
Iwasaki, A. (2020) Deriving the Variance of the Discrete Fourier Transform Test Using Parseval’s Theorem. IEEE Transactions on Information Theory, 66, 1164-1170. https://doi.org/10.1109/TIT.2019.2947045
Pareschi, F., Rovatti R. and Setti, G. (2012) On Statistical Tests for Randomness Included in the NIST SP800-22 Test Suite and Based on the Binomial Distribution. IEEE Transactions on Information Forensics and Security, 7, 491-505. https://doi.org/10.1109/TIFS.2012.2185227
Hamano, K. (2005) The Distribution of the Spectrum for the Discrete Fourier Transform Test Included in SP800-22. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E88-A, 67-73. https://doi.org/10.1093/ietfec/E88-A.1.67
Zhu, S., Ma, Y., Li, X., Yang, J. and Lin, J. (2020) On the Analysis and Improvement of Min-Entropy Estimation on Time-Varying Data. IEEE Transactions on Information Forensics and Security, 15, 1696-1708. https://doi.org/10.1109/TIFS.2019.2947871
Claasen, T.A.C.M. and Mecklenbrauker, W.F.G. (1980) The Wigner Distribution— A Tool for Time-Frequency Signal Analysis—PART I: Continuous-Time Signals. Phillips Journal or Research, 35, 217-250.
Claasen, T.A.C.M. and Mecklenbrauker, W.F.G. (1980) The Wigner Distribution— A Tool for Time-Frequency Signal Analysis—PART II: Discrete-Time Signals. Phillips Journal or Research, 35, 276-300.
Domínguez-Molina, J.A., González-Farías, G. and Rodríguez-Dagnino, R.M. (2003) A Practical Procedure to Estimate the Shape Parameter in the Generalized Gaussian Distribution. Universidad de Guanajuato, ITESM Campus Monterrey, Guanajuato, 1-27.
González-Farías, G., Domínguez-Molina, J.A. and Rodríguez-Dagnino, R.M. (2009) Efficiency of the Approximated Shape Parameter Estimator in the Generalized Gaussian Distribution. IEEE Transactions on Vehicular Technology, 58, 4214-4223. https://doi.org/10.1109/TVT.2009.2021270
Marple, L. (1999) Computing the Discrete-Time “Analytic” Signal via FFT. IEEE Transactions on Signal Processing, 47, 2600-2603. https://doi.org/10.1109/78.782222