Cryptography From a Complexity-theoretical Point of View

Abstract

Cryptography plays a more and more significant role in the internet age, as the issue of privacy and security becomes more and more important. In this talk, we will discuss cryptography from the perspective of computational complexity. First, we will see how the theory of computational complexity helps lay the foundation of modern cryptography. Then we will see how a central complexity question in cryptography is related to fundamental questions in several areas in computer science as well as other disciplines. Next, some basic cryptographic primitives will be introduced and we will discuss how these simple primitives can be used to accomplish almost all conceivable cryptographical tasks. Finally, we will discuss some recent results on quantum information processing and their effect on cryptography.