Some improvements to statistical tests of randomness using pattern matching
DOI:
https://doi.org/10.54654/isj.v1i13.115Keywords:
randomness testing, template matching, 5-bit, 4-bitTóm tắt
Tóm tắt—Các kiểm tra liên quan đến so khớp mẫu chồng lấp đã được đề xuất trong NIST SP 800-22 [1], tuy nhiên các xác suất trong các kiểm tra này chỉ đúng cho các mẫu đặc biệt và cần được tính lại cho các mẫu khác. Trong [2], các tác giả đã đề xuất các tiêu chuẩn thống kê so khớp mẫu mới cho tất cả các mẫu 4 bit. Các kiểm tra mới này áp dụng cho chuỗi bất kỳ có độ dài tối thiểu là 5504 bit, trong khi theo NIST độ dài tối thiểu 106 bit. Trong bài báo này, chúng tôi đã cải tiến và đề xuất các kiểm tra so khớp mẫu 4 bit mới mà có thể áp dụng cho các chuỗi bất kỳ có độ dài nhỏ nhất chỉ là 3726 bit. Hơn nữa, chúng tôi đưa ra 3 kiểm tra thống kê so khớp mẫu 5 bit mới. Kết quả lý thuyết và thực hành cho thấy các đề xuất cải tiến của chúng tôi là rất hiệu quả trong việc đánh giá tính ngẫu nhiên cho các bộ tạo số giả ngẫu nhiên.
Abstract—Randomness tests related to overlapping template matching have been proposed in NIST SP 800-22 [1], however the probabilities in these tests are only valid for specific samples and should be recalculated for other samples. In [2], the authors proposed new template matching tests for all 4-bit templates. The new tests can be applied to any sequence of minimum length of 5504 bits whereas the overlapping template matching test in the NIST test suite can only be applied to sequences of minimum length of 106 bits. In this paper, we have modified and proposed new 4-bit template matching tests that can be applied to any sequence of minimum length 3726 bits. Furthermore, we proposed three new 5-bit template matching tests. Our theoretical and practical results show that our new proposed tests are very efficient in psedorandom number generator testing.
Downloads
References
Bassham III, L.E., et al., SP 800-22 Rev. 1a. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, National Institute of Standards & Technology, Gaithersburg, MD, 2010.
Sulak, F., New statistical randomness tests: 4-bit template matching tests. Turkish Journal of Mathematics, 41(1), 2017, p. 80-95.
Oorschot, P.v., Vanstone, S.A., and MENEZES, A., Handbook of applied cryptography, CRC press, 1997.
Kunuth, D., The Art of Computer Programming vol. 2 Seminumerical Algorithms, Reading, Massachusetts: Addison Wesley, 1998.
Caelli, W., Crypt x package documentation. Information Security Research Centre School of Mathematics, Queensland University of Technology, 1992.
Marsaglia, G., The marsaglia random number cdrom including the diehard battery of tests of randomness, 2008 http://www.stat.fsu.edu/pub/diehard (Accessed 19/8/2021).
L'Ecuyer, P. and Simard, R., TestU01: AC library for empirical testing of random number generators. ACM Transactions on Mathematical Software (TOMS), 33(4), 2007, p. 22.
Menezes, A.J., Van Oorschot, P., and Vanstone, S., Handbook of Applied Cryptography, CRCPress, Chapter. 5(7), 1996, p. 12.
Soto, J. and Bassham, L., Randomness testing of the advanced encryption standard finalist candidates. 2000.
Sulak, F., et al. Evaluation of randomness test results for short sequences. in International Conference on Sequences and Their Applications. Springer, 2010.
Takeda, Y., The problem of template matching test in the testing randomness by NIST. IEICE Technical Report, 2005, p. ISEC2005-110.
Doğanaksoy, A. and Göloğlu, F. On Lempel-Ziv complexity of sequences. in International Conference on Sequences and Their Applications. Springer, 2006.
Doganaksoy, A. and Tezcan, C. An alternative approach to Maurer’s universal statistical test. in Information Security and Cryptology Conference ISC Turkey 2006 3rd International Conference Proceedings. 2008.
Okutomi, H., A study on the randomness evaluation method using NIST randomness test. Proc. SCIS, Jan., 2006.
Hamano, K. and Kaneko, T., Correction of overlapping template matching test included in NIST randomness test suite. IEICE transactions on fundamentals of electronics, communications and computer sciences, 2007. 90(9): p. 1788-1792.
Rukhin, A., et al., Statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST special publication. 2010.
Charalambides, C.A., Enumerative combinatorics., Chapman and Hall/CRC, 1996.
Hoang Dinh Linh, "Some results on new statistical randomness tests based on length of runs", Journal of Science and Technology on Information security, ISSN 2615-9570, Vol. 08, No. 02, 2018, pp. 19-24.
Adrián Alfonso Peñate, Daymé Almeida Echevarria, Laura Castro Argudín, “Statistical Assessment of two Rekeying Mechanisms applied to the Generation of Random Numbers”, Journal of Science and Technology on Information Security, ISSN 2615-9570, Vol. 12, No. 02, 2020, pp. 38-44.
Downloads
Published
How to Cite
Issue
Section
License
Proposed Policy for Journals That Offer Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Proposed Policy for Journals That Offer Delayed Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication, with the work [SPECIFY PERIOD OF TIME] after publication simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
