CS Events
PhD DefenseMeta Complexity - Connections to One-way functions and Zero Knowledge protocols |
|
||
Thursday, August 31, 2023, 01:00pm - 03:00pm |
|||
Abstract : The main theme of this thesis is the study of some connections between Meta Complexity problems and important complexity/ cryptographic objects such as One way functions (OWFs) and Zero knowledge protocols.
1. Meta-complexity and OWFs - We present an NP-complete problem called Minimum Conditional Kolmogorov Time problem (McKTP) and provide an almost equivalence between the average case hardness of McKTP and the existence of OWFs. 2. Characterizations for SZK and NISZK - We present characterizations for Statistical Zero Knowledge (SZK) and its non-interactive variant (NISZK). We show that these classes correspond precisely to the set of promise problems that are randomly reducible to the set of Kolmogorov random strings. 3. Robustness for space bounded Zero knowledge protocols - We show that the space bounded zero knowledge classes (SZK, NISZK) are surprisingly robust to changing the power of the verifier and the simulator.
Speaker: Harsha Srimath Tirumala
Location : CoRE 305 and Zoom
Committee:
Professor Eric Allender (Chair)
Professor Mike Saks
Professor Sepehr Assadi
Professor Valentine Kabinets (Simon Fraser University)
Event Type: PhD Defense
Abstract: See above
Organization:
Rutgers University
School of Arts & Sciences
Department of Computer Science
Contact Professor Eric Allender