Sign in
Back
Zero Knowledge and Circuit Minimization
Book chapter   Peer reviewed

Zero Knowledge and Circuit Minimization

Eric Allender and Bireswar Das
Mathematical Foundations of Computer Science 2014, pp.25-32
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2014
DOI: https://doi.org/10.1007/978-3-662-44465-8_3

Abstract

Graph Isomorphism Promise Problem Graph Isomorphism Problem Kolmogorov Complexity Zero Knowledge
We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RPMCSP. This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these problems share, as candidate NP-intermediate problems.

Metrics

12 Record Views

Details