### Revision(s):

__
Revision #2 to TR22-127 | 13th September 2023 19:20
__
#### 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 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.

**Changes to previous version:**
Section 7 is new (removing the "honesty" assumption). Additional material in Section 8. Other minor changes.

__
Revision #1 to TR22-127 | 22nd November 2022 21:52
__
#### 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 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.

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

### Paper:

__
TR22-127 | 12th September 2022 19:01
__

#### 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 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.