AbstractWe 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
RightsThis work has been licensed by the rightsholder under a Creative Commons Attribution-NonCommercial-NoDerivs (CC BY-NC-ND) 4.0 International License (https://creativecommons.org/licenses/by-nc-nd/4.0/).