Login
Computer Science @ Rochester
Monday, September 13, 2004
11:00 AM
CSB 209
Joerg Rothe
U. Duesseldorf
Complexity Theory and Cryptography, or the Power of Zero-Knowledge
In this talk, some results from complexity theory and cryptography are presented. The talk consists of the following three parts:

Part I shows that for various voting systems such as Carroll elections, Young elections, and Kemeny elections, the winner problem is complete for parallel access to NP.

Part II presents some cryptographic protocols that are based on one-way functions with certain algebraic properties. It is shown that such one-way functions exist if and only if P differs from NP.

Part III introduces the notion of zero-knowledge protocols, which are interesting both in cryptographic applications and in complexity theory. All three parts will be presented on a non-technical level, preferring illustrating pictures and examples over formal proofs.