Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR22-138 | 8th July 2023 22:08

Robustness for Space-Bounded Statistical Zero Knowledge

RSS-Feed




Revision #2
Authors: Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang
Accepted on: 8th July 2023 22:08
Downloads: 117
Keywords: 


Abstract:

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 the conjecture that these classes may coincide with the non-space-bounded classes SZK and NISZK, respectively.



Changes to previous version:

Some minor clarifications added, and minor errors corrected.


Revision #1 to TR22-138 | 14th February 2023 23:05

Robustness for Space-Bounded Statistical Zero Knowledge





Revision #1
Authors: Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang
Accepted on: 14th February 2023 23:05
Downloads: 146
Keywords: 


Abstract:

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 the conjecture that these classes may coincide with the non-space-bounded classes SZK and NISZK, respectively.



Changes to previous version:

Significant simplification of the presentation of results in Section 3, and explicit presentation of a restricted complete problem for NISZK_L; other minor changes.


Paper:

TR22-138 | 5th October 2022 21:44

Robustness for Space-Bounded Statistical Zero Knowledge





TR22-138
Authors: Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang
Publication: 5th October 2022 21:48
Downloads: 342
Keywords: 


Abstract:

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 the conjecture that these classes may coincide with the non-space-bounded classes SZK and NISZK, respectively.



ISSN 1433-8092 | Imprint