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

摘要: In this tutorial, selected topics of cryptology and computational complexity theory are presented. We give a brief overview the history foundations classical cryptography, then move on to modern public-key cryptography. Particular attention is paid cryptographic protocols problem constructing key components such as one-way functions. A function if it easy compute, but hard invert. discuss notion functions both in complexity-theoretic setting. also consider interactive proof systems present some interesting zero-knowledge protocols. protocol one party can convince other knowing secret information without disclosing any bit information. Motivated by these protocols, we survey results related classes.