__
Revision #1 to TR01-096 | 20th December 2002 00:00
__
#### Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial

**Abstract:**
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.

__
TR01-096 | 21st November 2001 00:00
__

#### Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial

TR01-096
Authors:

Jörg Rothe
Publication: 5th December 2001 09:32

Downloads: 4008

Keywords:

**Abstract:**
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.