Pre-requisites : NIL
Definitions of randomness: statistical (Martin-Loef, Solovay), based on program size complexity (Chaitin). Equivalence of the definitions. Random numbers: Properties of random and pseudo-random sequences. Provably secure pseudo-random generators. Examples of pseudo-random generators: Fake One-Time Pads, Period of a pRNG, Congruential Generators, Feedback Shift Generators, Blum-Blum-Shub Generator, Naor-Reingold Generator. Statistical tests for random numbers: Chi-square test, Kolmogorov-Smirnov test, empirical / theoretical / spectral tests. Non-uniform random sequences. Randomized algorithms. Derandomization techniques. Pseudo-random functions and permutations. Sequences of families of PSFs and PSPs. Applications: cryptographically strong hashing, prediction, learning, identify friend or foe, private-key encryption.
1. G. J. Chaitin, Algorithmic Information Theory, Cambridge University Press, 2004.
2. G. J. Chaitin, Information, Randomness and Incompleteness, 2nd edition, World Scientific, 1990.
3. G. J. Chaitin, Exploring Randomness, Springer-Verlag, 2001.
4. S. Goldwasser and M. Bellare, Lecture Notes in Cryptography, http://www-cse.ucsd.edu/~mihir/papers/gb.pdf, 2001.
5. P. Garrett, Making and Breaking Codes: Introduction to Cryptology, Prentice-Hall, 2000.
6. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
7. D. E. Knuth, The Art of Computer Programming, 3rd Ed, Vol 2, Seminumerical Algorithms, Addison-Wesley, 1998.
8. W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, Wiley Eastern, 1968.