| Course Code: CS510 Course Name: Information And Randomness Prerequisites: NIL Syllabus: 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. References: 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. |