Computer Science – Computational Complexity
Scientific paper
2001-11-21
ACM Computing Surveys, volume 34, issue 4, pp. 504--549, December 2002
Computer Science
Computational Complexity
57 pages, 17 figures, Lecture Notes for the 11th Jyvaskyla Summer School
Scientific paper
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.
No associations
LandOfFree
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-341372