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

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-341372

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.