Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
<|reference_start|>Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial: 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.<|reference_end|>
@article{rothe2001some,
    title={Some Facets of Complexity Theory and Cryptography: A Five-Lectures
  Tutorial},
    author={J"org Rothe},
    journal={ACM Computing Surveys, volume 34, issue 4, pp. 504--549, December
  2002},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0111056},
    primaryClass={cs.CC cs.CR}
}