Using information theory approach to randomness testing

DOI10.1016/J.JSPI.2004.02.010MaRDI QIDQ110728zbMATHOpenAlexFDO

Authors B.Ya. Ryabko, V.A. Monarev, V. A. Monarev, B. Ya. Ryabko

Publication date July 2005

Published in Journal of Statistical Planning and Inference (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0504006

zbMATH Keywords

Information TheoryRandom number generatorRandom number testingRandomness testingShannon entropyUniversal code

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Nonparametric hypothesis testing (62G10) Random number generation in numerical analysis (65C10) Source coding (94A29)

Abstract: We address the problem of detecting deviations of binary sequence from randomness,which is very important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we consider a null hypothesis $H_0$ that a given bit sequence is generated by Bernoulli source with equal probabilities of 0 and 1 and the alternative hypothesis $H_1$ that the sequence is generated by a stationary and ergodic source which differs from the source under $H_0$. We show that data compression methods can be used as a basis for such testing and describe two new tests for randomness, which are based on ideas of universal coding. Known statistical tests and suggested ones are applied for testing PRNGs. Those experiments show that the power of the new tests is greater than of many known algorithms.

Recommendations

• scientific article; zbMATH DE number 503266
• A new randomness test for bit sequences
• Asymptotically most powerful tests for random number generators
• A universal statistical test for random bit generators
• Application of data compression methods to hypothesis testing for ergodic and stationary processes

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3700709 (Why is no real title available?)
• scientific article; zbMATH DE number 3727273 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3752089 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 3227613 (Why is no real title available?)
• scientific article; zbMATH DE number 3316587 (Why is no real title available?)
• A locally adaptive data compression scheme
• A new test for randomness and its application to some cryptographic problems
• A universal statistical test for random bit generators
• Interval and recency rank source coding: Two on-line adaptive variable-length schemes
• On the minimax estimator of an unknown mean value
• Twice-universal coding

Cited in

(18)

• On an approach to the detection of multiple change-points in Bernoulli trials using the CTW predictor
• Asymptotically most powerful tests for random number generators
• A new type of attacks on block ciphers
• R-2 composition tests: a family of statistical randomness tests for a collection of binary sequences
• ``Book stack as a new statistical test for random numbers
• Application of data compression methods to hypothesis testing for ergodic and stationary processes
• scientific article; zbMATH DE number 4132084 (Why is no real title available?)
• scientific article; zbMATH DE number 1526592 (Why is no real title available?)
• Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series
• A new randomness test for bit sequences
• Application of data compression methods to nonparametric estimation of characteristics of discrete-time stochastic processes
• Universal codes as a basis for nonparametric testing of serial independence for time series
• On some statistical properties of the ``Book Stack transformation
• Using data compressors to construct order tests for homogeneity and component independence
• An approximate entropy test for randomness
• CryptRndTest
• Universal codes as a basis for time series testing
• Statistical testing of randomness: new and old procedures

Describes a project that uses

Uses Software

• NIST Statistical Test Suite

This page was built for publication: Using information theory approach to randomness testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q110728)