Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
| dc.creator | Rothe, Jörg | |
| dc.date | 2001-11-21 | |
| dc.date | 2002-12-20 | |
| dc.date.accessioned | 2026-07-07T03:17:58Z | |
| dc.date.available | 2026-07-07T03:17:58Z | |
| dc.description | 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. | |
| dc.description | 57 pages, 17 figures, Lecture Notes for the 11th Jyvaskyla Summer School | |
| dc.identifier | https://arxiv.org/abs/cs/0111056 | |
| dc.identifier | http://arxiv.org/abs/cs/0111056 | |
| dc.identifier | ACM Computing Surveys, volume 34, issue 4, pp. 504--549, December 2002 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30931 | |
| dc.subject | Computational Complexity | |
| dc.subject | Cryptography and Security | |
| dc.subject | E.3; F.1.3; F.2.2 | |
| dc.title | Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial | |
| dc.type | text |