Cryptography and Kolmogorov Complexity

Rafael Pass (Cornell Tech and Tel Aviv University) gave a two-part tutorial presentation on Cryptography and Kolmogorov Complexity, at the Simons Institute's Meta-Complexity Boot Camp on January 19. Here we present Part 1 of the tutorial, which includes a brief review of the history of cryptography, as well as a discussion of more recent results and the connections between cryptography and Kolmogorov complexity.