TCS-TR-B-08-4

Date: Wed Apr 16 17:59:45 2008

Title: Course Notes on Complexity and Cryptography

Authors: Thomas Zeugmann

Contact:

First name: Thomas
Last name: Zeugmann
Address: Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan
Email: thomas@ist.hokudai.ac.jp

Abstract. The main purpose of this course is an introductory study of computational complexity and cryptography.

The first part introduces the concept of computational complexity by looking at the basic arithmetic operations, i.e., addition, subtraction, multiplication and division. Then matrix multiplication is touched.

In order to prepare everything we need later for public-key cryptography, we continue with number theoretic problems and study several algorithms including modular exponentiation, primality testing and taking discrete roots.

In the following, we introduce well-known complexity classes, look at complete problems and finish with probabilistic complexity classes. There is also an appendix comprising additional material that had to be omitted due to the introductory character of this course, but may be worth to be known.

The second part is devoted to cryptography. After a short historical sketch we deal with public-key cryptography in some more detail, look at authentication and cryptographic protocols, and finish with a more detailed study of digital signatures. Again, there is an appendix containing material for further reading.