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 NISZKL and SZKL.

Theorem 42 in this revision is a significant improvement over Theorem 43 in the previous version. There are other minor changes.

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to give new characterizations of Statistical Zero Knowledge (SZK), as well as the related classes NISZK_L and SZK_L.

Section 7 is new (removing the "honesty" assumption). Additional material in Section 8. Other minor changes.

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 recent work by Saks and Santhanam (CCC 2022). We build on this to give new characterizations of Statistical Zero Knowledge (SZK), as well as the related classes NISZK_L and SZK_L.

The main theorems are now stated in terms of "honest" reductions. Some minor typos were fixed, a new theorem was added, etc.

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to give new characterizations of Statistical Zero Knowledge (SZK), as well as the related classes NISZK_L and SZK_L.