In this tutorial, selected topics of cryptology and of
computational complexity theory are presented. We give a brief overview
of the history and the foundations of classical cryptography, and then
move on to modern public-key cryptography. Particular attention is
paid to cryptographic protocols and the problem of constructing key
components of protocols such as one-way functions. A function is
one-way if it is easy to compute, but hard to invert. We discuss
the notion of one-way functions both in a cryptographic and in a
complexity-theoretic setting. We also consider interactive proof systems
and present some interesting zero-knowledge protocols. In a
zero-knowledge protocol one party can convince the other party of
knowing some secret information without disclosing any bit of this
information. Motivated by these protocols, we survey some
complexity-theoretic results on interactive proof systems and related
complexity classes.

In this tutorial, selected topics of cryptology and of
computational complexity theory are presented. We give a brief overview
of the history and the foundations of classical cryptography, and then
move on to modern public-key cryptography. Particular attention is
paid to cryptographic protocols and the problem of constructing the key
components of such protocols such as one-way functions. A function is
one-way if it is easy to compute, but hard to invert. We discuss
the notion of one-way functions both in a cryptographic and in a
complexity-theoretic setting. We also consider interactive proof systems
and present some interesting zero-knowledge protocols. In a
zero-knowledge protocol one party can convince the other party of
knowing some secret information without disclosing any bit of this
information. Motivated by these protocols, we survey some
complexity-theoretic results on interactive proof systems and related
complexity classes.