Random Numbers in Monte Carlo and Cryptology

Uniform random number generators (RNGs) play a key role in two fields of applied mathematics and computer science, Monte Carlo simulation and cryptography. RNGs are small programs that produce numbers which perform like "true" random numbers. This procedure seems to be contradictory because we are generating randomness on deterministic machines. Nevertheless, it works very well in practice. The Monte Carlo method as well as cryptographic Algorithms are applied to many scientific and technical tasks. For example, at the Technical University of Darmstadt (Germany) one tries to find out by Monte Carlo simulation if German standards for waste water processing follow the EC guidelines. This question is of great economical importance: If the answer is no, then German water processing plants will have to be adapted to the EC standard. This effort will cost billions of Deutsche Mark. Other applications of the Monte Carlo Method concern nuclear physics and the simulation of atomic bomb explosions, as they are carried out in a large scale in the United States. The quality of the RNGs may be of crucial importance for the reliability of the results of these simulations. Quite regularly, wrong results can only be detected by a close analysis of the involved RNGs. In cryptography, the importance of RNGs is of similar importance. The safety of computer networks - from Bankomat (automatic teller machines) up to whole company networks - often depends heavily on the quality of the cryptographic RNGs that are used in the implementation of the security protocols. In this project, we will use synergies that result from the application of Monte Carlo techniques to cryptographic problems and vice versa, in close co-operation with research groups in Austria and abroad. Our research will result in better Algorithms to assess the quality of RNGs. This project`s goals are: (i) extension of the current arsenal of empirical and theoretical tests for RNGs, (ii) application of these tests to study the statistical properties of cryptographic Algorithms, (iii) application of particular "bit-scrambling" techniques of cryptography to improve the properties of Monte Carlo RNGs, and (iv) application of (de-)randomization techniques to construct fast-converging Monte Carlo methods. Our results will be accessible world-wide for other researchers and practitioners. A preliminary version of our server is available at http://random.mat.sbg.ac.at