On testing pseudorandom generators via statistical tests based on the arcsine law
This addresses the need for reliable statistical tests in cryptography to ensure security, but it is incremental as it builds on existing arcsine law methods.
The paper tackles the problem of testing pseudorandom number generators by proposing a second-level statistical test based on the arcsine law for random walks, and it provides a Berry-Essen type inequality to enable detailed error analysis for this test.
Testing the quality of pseudorandom number generators is an important issue. Security requirements become more and more demanding, weaknesses in this matter are simply not acceptable. There is a need for an in-depth analysis of statistical tests -- one has to be sure that rejecting/accepting a generator as good is not a result of errors in computations or approximations. In this paper we propose a second level statistical test based on the arcsine law for random walks. We provide a Berry-Essen type inequality for approximating the arcsine distribution, what allows us to perform a detailed error analysis of the proposed test.