×

zbMATH — the first resource for mathematics

Feistel-inspired scrambling improves the quality of linear congruential generators. (English) Zbl 1364.65008
Summary: Generating pseudorandom numbers is a prerequisite for many areas including Monte Carlo simulation and randomized algorithms. The performance of pseudorandom number generators (PRNGs) depends on the quality of the generated random sequences. They must be generated quickly and have good statistical properties. Several statistical test suites have been developed to evaluate a single stream of random numbers such as those from the TestU01 library, the DIEHARD test suite, the tests from the SPRNG package, and a set of tests designed to evaluate bit sequences developed at NIST. This paper presents a new pseudorandom number generation scheme that produces pseudorandom sequences with good statistical properties via a scrambling procedure motivated by cryptographic transformations. We will specifically apply this to a popular set of PRNGs called the Linear Congruential generators (LGCs). The scrambling technique is based on a simplified version of a Feistel network. The proposed method seeks to improve the quality of the LCGs output stream. We show that this Feistel-inspired scrambling technique breaks up the regularities that are known to exist in LCGs. The Feistel-inspired scrambling technique is modular, and can be applied to any 64-bit PRNG, and so we believe that it can serve as an inexpensive model for a scrambler that can be used with most PRNGs via post-processing.
MSC:
65C10 Random number generation in numerical analysis
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. Banks, J. S. Carson II and L. Barry, Discrete-Event System Simulation, Prentice Hall, Upper Saddle River, 2001.
[2] C. Bays and S. Durham, Improving a poor random number generator, ACM Trans. Math. Software (TOMS) 2 (1976), no. 1, 59-64. · Zbl 0317.65001
[3] J. Beizer, Speeding up TestU01 with the use of HTCondor, preprint (2017), .
[4] J. Daemen and V. Rijmen, The design of Rijndael: AES - The advanced encryption standard, J. Cryptology 4 (1991), no. 1, 3-72.
[5] K. Donald, The Art of Computer Programming. Volume 2: Semi-Numerical Algorithms, Addison-Wesley, Boston, 1998.
[6] N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas and J. Walker, The skein hash function family, Submission to NIST (round 3) (2010), .
[7] N. Fips, 46-3: The official document describing the DES standard, Technical Report, 1999.
[8] G. S. Fishman and I. L. R. Moore, An exhaustive analysis of multiplicative congruential random number generators with modulus 2^31-1, SIAM J. Sci. Stat. Comput. 7 (1986), no. 1, 24-45. · Zbl 0603.65003
[9] J. E. Gentle, Random Number Generation and Monte Carlo Methods, Springer, New York, 2003. · Zbl 1028.65004
[10] P. Hellekalek, Good random number generators are (not so) easy to find, Math. Comput. Simulation 46 (1998), no. 5, 485-505. · Zbl 0931.65001
[11] J. Katz and Y. Lindell, Introduction to Modern Cryptography: Principles and Protocols, Chapman Hall/CRC, London, 2008.
[12] L. Keliher, Substitution-permutation network cryptosystems using key-dependent S-boxes, preprint (1998), .
[13] P. L’Ecuyer, Tables of linear congruential generators of different sizes and good lattice structure, Math. Comp. 68 (1999), no. 225, 249-260. · Zbl 0917.65002
[14] P. L’Ecuyer and R. Simard, On the performance of birthday spacings tests with certain families of random number generators, Math. Comput. Simulation 55 (2001), no. 1, 131-137. · Zbl 0981.65008
[15] P. L’Ecuyer and R. Simard, TestU01: A C library for empirical testing of random number generators, ACM Trans. Math. Software (TOMS) 33 (2007), no. 4, Article No. 22. · Zbl 1365.65008
[16] G. Marsaglia, Random numbers fall mainly in the planes, Proc. Natl. Acad. Sci. USA 61 (1968), no. 1, 25-28. · Zbl 0172.21002
[17] G. Marsaglia, A current view of random number generators, Computer Science and Statistics. Sixteenth Symposium on the Interface, North-Holland, Amsterdam (1985), 3-10.
[18] G. Marsaglia, Random number generation, Encyclopedia of Computer Science, John Wiley & Sons, Chichester (2003), 1499-1503.
[19] M. Mascagni and A. Srinivasan, Algorithm 806: Sprng: A scalable library for pseudorandom number generation, ACM Trans. Math. Software (TOMS) 26 (2000), no. 3, 436-461.
[20] A. J. Menezes, P. C. Van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1996. · Zbl 0868.94001
[21] J. K. Salmon, M. A. Moraes, R. O. Dror and D. E. Shaw, Parallel random numbers: As easy as 1, 2, 3, 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE Press, Piscataway (2011), 1-12.
[22] C. E. Shannon, Communication theory of secrecy systems, Bell Labs Tech. J. 28 (1949), no. 4, 656-715. · Zbl 1200.94005
[23] J. Soto, Statistical testing of random number generators, Proceedings of the 22nd National Information Systems Security Conference, National Institute of Standards and Technology, Gaithersburgh (1999), 1-12.
[24] S. Tzeng and L.-Y. Wei, Parallel white noise generation on a GPU via cryptographic hash, Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, ACM, New York (2008), 79-87.
[25] F. Zafar, M. Olano and A. Curtis, Gpu random numbers via the tiny encryption algorithm, Proceedings of the Conference on High Performance Graphics, Eurographics Association, Aire-la-Ville (2010), 133-141.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.