Student Seminar in Computational Complexity and Theoretical Cryptography

Zero Knowledge

Note: Presentations related to "Zero Knowledge" are being organized by Yevgeniy Vahlis and Periklis Papakonstantinou.

Speaker: Yevgeniy Vahlis

Topic: Head start: Graph non-Isomorphism

Date: September 24, 2007

ABSTRACT
I will review the notions of interactive proofs, and interactive turing machines. I will then present the basic definitions of Zero-Knowledge, and a Zero Knowledge proof system for Graph non-Isomorphism. Finally, we will discuss the notion of expected polynomial time simulatability and some issues related to its definition.