ECCC-Report TR01-096https://eccc.weizmann.ac.il/report/2001/096Comments and Revisions published for TR01-096en-usFri, 20 Dec 2002 00:00:00 +0200
Revision 1
| Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial |
Jörg Rothe
https://eccc.weizmann.ac.il/report/2001/096#revision1In 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.
Fri, 20 Dec 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2001/096#revision1
Paper TR01-096
| Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial |
Jörg Rothe
https://eccc.weizmann.ac.il/report/2001/096In 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.
Wed, 05 Dec 2001 09:32:20 +0200https://eccc.weizmann.ac.il/report/2001/096