Speeding Up Minimum Distance Randomness Tests
DOI:
https://doi.org/10.26636/jtit.2022.159222Keywords:
Bickel-Breiman test, minimum distance test, m nearest pairs test, randomness testAbstract
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.
Downloads
References
[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: https://doi.org/10.1109/SFCS.1975.8
View in Google Scholar
[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: https://doi.org/10.1145/800113.803652
View in Google Scholar
[3] J. L. Bentley, „Multidimensional divide-and-conquer", Comm. of the Assoc. for Comput. Machinery, vol. 23, no. 4, pp. 214-229, 1980. DOI: https://doi.org/10.1145/358841.358850
View in Google Scholar
[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: https://doi.org/10.1016/0020-0190(88)90150-0
View in Google Scholar
[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: https://doi.org/10.1006/inco.1995.1049
View in Google Scholar
[6] A. Andoni, P. Indyk, and I. Razenshteyn, „Approximate nearest neighbor search in high dimensions", 2018. [Online]. Available: https://arxiv.org/pdf/1806.09823
View in Google Scholar
[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: https://doi.org/10.2172/794005
View in Google Scholar
[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
View in Google Scholar
[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: https://doi.org/10.1145/3447773
View in Google Scholar
[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: https://doi.org/10.1287/opre.48.2.308.12385
View in Google Scholar
[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: https://doi.org/10.1214/aop/1176993668
View in Google Scholar
[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: https://doi.org/10.1145/1268776.1268777
View in Google Scholar
[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
View in Google Scholar
[14] AMD Ryzen Threadripper 3990X Processor [Online]. Available: https://www.amd.com/en/products/cpu/amd-ryzen-threadripper-3990x
View in Google Scholar
[15] AMD Ryzen Threadripper PRO 3995WX GFLOPS performance [Online]. Available: https://gadgetversus.com/processor/amd-ryzenthreadripper-pro-3995wx-gops-performance/
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2022 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
