CS510INFORMATION AND RANDOMNESS3-0-0-6

Pre-requisites : 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.

Texts :

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.