Abstract
Given a binary sequence, one may inquire whether it is produced by a true random source. There are several tests designed to answer this question, such as the statistical test suite of the National Institute of Standard and Technology (NIST) and the Diehard tests.
The problem is that, given deterministic tests of randomization, an adversary may know/learn, the adversary may tailor a non-random (deterministic) sequence, guided by the deterministic tests, that passes the tests.
We suggest to use a true random source for randomness tests and thus make the tests significantly harder to being misled. We design tests that use true random sources and demonstrate their ability to detect non-random sequences that NIST classifies as random.
D. Berend—Research supported in part by the Milken Families Foundation Chair in Mathematics and the Cyber Security Research Center at Ben-Gurion University.
S. Dolev—This research was (partially) funded by a grant from the Ministry of Science and Technology, Israel & the Japan Science and Technology Agency (JST), the German Research Funding (DFG, Grant #8767581199), Genesis Consortium, the Rita Altura trust chair in computer science, and by the Lynne and William Frankel Center for Computer Science.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing that distributions are close. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12–14 November 2000, Redondo Beach, California, USA, pp. 259–269 (2000)
Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing closeness of discrete distributions. J. ACM 60(1), 4:1–4:25 (2013)
Chan, S., Diakonikolas, I., Valiant, P., Valiant, G.: Optimal algorithms for testing closeness of discrete distributions. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, 5–7 January 2014, pp. 1193–1203 (2014)
Diakonikolas, I., Gouleakis, T., Peebles, J., Price, E.: Collision-based testers are optimal for uniformity and closeness. Chic. J. Theor. Comput. Sci. 2019, 1–21 (2019). http://cjtcs.cs.uchicago.edu/articles/2019/1/contents.html
Dolev, S., Gilboa, N., Li, X.: Accumulating automata and cascaded equations automata for communicationless information theoretically secure multi-party computation. Theor. Comput. Sci. 795, 81–99 (2019)
Fredricksen, H., Maiorana, J.: Necklaces of beads in \(k\) colors and \(k\)-ary de Bruijn sequences. Discret. Math. 23(3), 207–210 (1978)
Goldreich, O.: Introduction to Property Testing. Cambridge University Press, Cambridge (2017)
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653–750 (1998)
Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. In: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pp. 68–75 (2011)
jmviz: random-debruijn (2020). https://github.com/jmviz/random-debruijn/blob/master/debruijn.py
Kendall, M.G., Smith, B.B.: Randomness and random sampling numbers. J. R. Stat. Soc. 101(1), 147–166 (1938). http://www.jstor.org/stable/2980655
Knuth, D.E.: The Art of Computer Programming, Seminumerical Algorithms, vol. 2, 3rd edn. Addison-Wesley Longman Publishing Co., Inc., Boston (1997)
Kumar, M.: Randomness test of sequences (2022). https://github.com/manishkk/Randomness-Test-of-Sequences
Lehmann, E.L., Romano, J.P.: Testing Statistical Hypotheses. STS, Springer, New York (2005). https://doi.org/10.1007/0-387-27605-X
Neyman, J., Pearson, E.S.: On the problem of the most efficient tests of statistical hypotheses. Philos. Trans. R. Soc. London Ser. A 231, 289–337 (1933). http://www.jstor.org/stable/91247
Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252–271 (1996)
Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E.: A statistical test suite for random and pseudorandom number generators for cryptographic applications. Technical report, Booz-Allen and Hamilton Inc. McLean VA (2001)
Sawada, J., Williams, A., Wong, D.: A surprisingly simple de Bruijn sequence construction. Discret. Math. 339(1), 127–131 (2016)
Siu, M., Tong, P.: Generation of some de Bruijn sequences. Discret. Math. 31(1), 97–100 (1980)
Soto, J., Bassham, L.: Randomness testing of the advanced encryption standard finalist candidates, 1 April 2000
Sýs, M., Říha, Z.: Faster randomness testing with the NIST statistical test suite. In: Chakraborty, R.S., Matyas, V., Schaumont, P. (eds.) SPACE 2014. LNCS, vol. 8804, pp. 272–284. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-12060-7_18
Turan, M.S., Barker, E., Kelsey, J., McKay, K.A., Baish, M.L., Boyle, M., et al.: Recommendation for the entropy sources used for random bit generation. NIST Special Publication 800(90B), 102 (2018)
Acknowledgment
We thank Dean Doron for many interesting discussion related to this research.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Berend, D., Dolev, S., Kumar, M. (2022). Randomness for Randomness Testing. In: Dolev, S., Katz, J., Meisels, A. (eds) Cyber Security, Cryptology, and Machine Learning. CSCML 2022. Lecture Notes in Computer Science, vol 13301. Springer, Cham. https://doi.org/10.1007/978-3-031-07689-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-07689-3_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-07688-6
Online ISBN: 978-3-031-07689-3
eBook Packages: Computer ScienceComputer Science (R0)