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. Theproposed 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 (original
sequence with removed sections) will result as a sequence with high probability of random
References
[1]
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
[2]
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
[3]
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
[4]
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
[5]
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
[6]
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
[7]
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
[8]
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
[9]
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
[10]
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
[11]
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
[12]
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
[13]
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
[14]
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
[15]
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
[16]
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
[17]
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
[18]
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
[19]
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
[20]
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
[21]
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
[22]
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
[23]
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
[24]
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
[25]
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
[26]
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.
[27]
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.
[28]
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.
[29]
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
[30]
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
