Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR01-096 | 20th December 2002 00:00

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

RSS-Feed

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.


Paper:

TR01-096 | 21st November 2001 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 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.



ISSN 1433-8092 | Imprint