Zero knowledge and circuit minimization

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 RP MCSP. 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.

Authors

• Eric Allender
• Bireswar Das

Keywords

• Graph Isomorphism
• Minimum Circuit Size Problem
• NP-intermediate problem
• Statistical Zero Knowledge