Speeding Up Minimum Distance Randomness Tests

• Autorzy: Mańk Krzysztof

Identyfikatory

DOI

10.26636/jtit.2022.159222

• Języki publikacji: EN

Abstrakty

EN

Randomness testing is one of the essential and easiest tools for the evaluation of the features and quality of cryptographic primitives. The faster we can test, the greater volumes of data can be checked and evaluated and, hence, more detailed analyses may be conducted. This paper presents a method that significantly reduces the number of distances calculated in the minimum distance, Bickel-Breiman, and m nearest points tests. By introducing a probabilistic approach with an arbitrarily low probability of failure, the number of calculated distances proportional to the number of required distances and independent of the number of points was achieved. In the well-known Diehard’s minimum distance and 3D spheres tests, the quantity of computations achieved is reduced by the factors of 394 and 771, respectively.

Słowa kluczowe

EN

Bickel-Breiman test; minimum distance test; m nearest pairs test; randomness test

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2022
• Tom: nr 2
• Strony: 99--109
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Mańk Krzysztof

• Institute of Mathematics and Cryptology, Faculty of Cybernetics, Military University of Technology, Warsaw, Poland

• https://orcid.org/0000-0002-5048-9049

Bibliografia

• [1] M. I. Shamos and D. Hoey, „Closest-point problems", in Proc. Of the 16th Ann. Symp. on Found. of Comp. Sci., Berkeley, CA, USA, 1975 pp. 151-162 (DOI: 10.1109/SFCS.1975.8).
• [2] J. L. Bentley and M. I. Shamos, „Divide and conquer in multidimensional space", in Proc. of 8th Ann. ACM Symp. on the Theory of Comput., Hershey, PA, USA, 1976. pp. 220-230 (DOI: 10.1145/800113.803652).
• [3] J. L. Bentley, „Multidimensional divide-and-conquer", Comm. of the Assoc. for Comput. Machinery, vol. 23, no. 4, pp. 214-229, 1980 (DOI: 10.1145/358841.358850).
• [4] K. Hinrichs, J. Nievergelt, and P. Schorn, „Plane-sweep solves the closest pair problem elegantly", Inform. Process. Lett., vol. 26, no. 5, pp. 255-261, 1988 (DOI: 10.1016/0020-0190(88)90150-0).
• [5] S. Khuller and Y. Matias, „A simple randomized sieve algorithm for the closest-pair problem", Inform. and Comput., vol. 118, no. 1, pp. 34-37, 1995 (DOI: 10.1006/inco.1995.1049).
• [6] A. Andoni, P. Indyk, and I. Razenshteyn, „Approximate nearest neighbor search in high dimensions", 2018. [Online]. Available: https://arxiv.org/pdf/1806.09823
• [7] M. Fischler, „Distribution of minimum distance among N random points in d dimensions", Technical Rep. no. FERMILAB-TM-2170, Fermi National Accelerator Lab., Batavia, IL, USA, 2002 (DOI: 10.2172/794005).
• [8] M. Rűtti, „A random number generator test suite for the C++ standard", Diploma Thesis, Institute for Theoretical Physics, ETH Zűrich, 2004 [Online]. Available: http://comp-phys.org/software/rngts/doc/main.pdf
• [9] E. Luengo and L. García Villalba, „Recommendations on statistical randomness test batteries for cryptographic purposes", ACM Comput. Surv., vol. 54, no. 4, pp. 1-34, Article no. 80, 2021 (DOI: 10.1145/3447773).
• [10] P. L'Ecuyer, J. F. Cordeau, and R. Simard, „Close-point spatial tests and their application to random number generators", Operations Res., vol. 48, no. 2, pp. 189-350, 2000 (DOI: 10.1287/opre.48.2.308.12385).
• [11] P. J. Bickel and L. Breiman, „Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test", Ann. of Probab., vol. 11, no. 1, pp. 185-214, 1983 (DOI: 10.1214/aop/1176993668).
• [12] P. L'Ecuyer and R. Simard, „TestU01: A C library for empirical testing of random number generators", ACM Trans. on Math. Softw., vol. 33, no. 4, Article no. 33, pp. 1-44, 2007 (DOI: 10.1145/1268776.1268777). 33.
• [13] Nvidia V100 Tensor Core GPU, Nvidia Corporation V100 Datasheet, 2020 [Online]. Available: https://images.nvidia.com/content/technologies/volta/pdf/volta-v100-datasheet-update-us-1165301-r5.pdf
• [14] AMD Ryzen Threadripper 3990X Processor [Online]. Available: https://www.amd.com/en/products/cpu/amd-ryzen-threadripper-3990x
• [15] AMD Ryzen Threadripper PRO 3995WX GFLOPS performance [Online]. Available: https://gadgetversus.com/processor/amd-ryzenthreadripper-pro-3995wx-gops-performance/