On the Additional Chi-square Tests for the IID Assumption of NIST SP 800-90B

Recently, NIST has published the second draft of SP 800-90B used for entropy estimations of random number generators. It is conducted within the framework of a cryptographic module validation program (CMVP) for the entropy source. The official evaluation criteria such as CMVP should be supported by rigorous and theoretical foundations so as to achieve the credibility and reliability of the evaluation process. For the theoretical background of the entropy estimation, it is assumed in SP 800-90B that the distribution of the entropy source is unknown since we cannot obtain an appropriate hypothesis about the distribution of the noise source which is a component of the entropy source. In this case, the nonparametric statistical method is commonly used. The test suite of SP 800-90B is divided into two major steps. The first step is to determine the track, IID(independent and identically distributed) or Non-IID, and the second step is to estimate the entropy of the given source. The permutation tests and additional chi-square tests are used to test IID assumption for entropy source in the first step, and when all tests in the first step are passed, the given source is determined as IID. Depending on whether the given data is determined as IID or Non-IID, the entropy estimation is conducted using different estimators in the second step. In this paper, we concentrate on the additional chi-square tests and analyze them from the view point of the nonparametric statistical method. We find out several defects of the degrees of freedom in the tests of independence for binary and non-binary data. We correct the degrees of freedom based on our analysis, and it solidifies the theoretical basis of SP 800-90B. Furthermore, we provide some experimental results with the corrected degrees of freedom which show that the corrected tests are more effective.