Speeding Up Minimum Distance Randomness Tests

Abstract

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.