Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Abstract

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible via an honest polynomial-time reduction to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends work by Saks and Santhanam (CCC 2022). (Saks and Santhanam showed that promise problems that can be reduced in this way to such an approximation of the Kolmogorov-random strings have (possibly interactive) zero-knowledge proof systems, and they did not address the converse implication.) We build on this to give new characterizations of Statistical Zero Knowledge SZK , as well as the related classes NISZK L and SZK L .