All reports by Author Harsha Tirumala:

__
TR22-138
| 5th October 2022
__

Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang#### Robustness for Space-Bounded Statistical Zero Knowledge

Revisions: 2

__
TR22-127
| 12th September 2022
__

Eric Allender, Shuichi Hirahara, Harsha Tirumala#### Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Revisions: 2

Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang

We show that the space-bounded Statistical Zero Knowledge classes SZK_L and NISZK_L are surprisingly robust, in that the power of the verifier and simulator can be strengthened or weakened without affecting the resulting class. Coupled with other recent characterizations of these classes, this can be viewed as lending support to ... more >>>

Eric Allender, Shuichi Hirahara, Harsha Tirumala

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