Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-127 | 12th September 2022 19:01

Kolmogorov Complexity Characterizes Statistical Zero Knowledge

RSS-Feed




TR22-127
Authors: Eric Allender, Shuichi Hirahara, Harsha Tirumala
Publication: 13th September 2022 20:21
Downloads: 120
Keywords: 


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.



ISSN 1433-8092 | Imprint