Robustness for space-bounded statistical zero knowledge

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

doi:10.1145/3708508

Back

Robustness for space-bounded statistical zero knowledge

Journal article

Open access

Peer reviewed

Robustness for space-bounded statistical zero knowledge

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

ACM transactions on computation theory, Vol.17(1)

02/14/2025

DOI: https://doi.org/10.1145/3708508

Abstract

Computational Complexity Theory

Computer Theory

We show that the space-bounded statistical zero knowledge classes SZKL and NISZKL 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 [5], 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.

Files and links (3)

pdf

agmtw767.69 kBDownload View

Accepted Manuscript (AM) ACM Transactions on Computation Theory Open Access CC BY V4.0

url

https://doi.org/10.1145/3708508View

Version of Record (VoR) ACM Transactions on Computation Theory Open CC BY V4.0

url

Report an accessibility issueView

Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

1 File downloads

16 Record Views

Details

Title: Subtitle: Robustness for space-bounded statistical zero knowledge
Creators: Eric Allender (Author)
Jacob Gray (Author) - University of Toronto
Saachi Mutreja (Author) - University of California, Berkeley
Harsha Tirumala (Author) - Rutgers, The State University of New Jersey
Pengxiang Wang (Author) - École Polytechnique Fédérale de Lausanne
Publication Details: ACM transactions on computation theory, Vol.17(1)
Publisher: Association for Computing Machinery (ACM)
Number of pages: 25
Grants: CCF-1909216, National Science Foundation (United States, Arlington) - NSF
AF: Small: Algebraic Methods in Codes and Computation, CCF-1909683, National Science Foundation (United States, Arlington) - NSF
CCF-1852215, National Science Foundation (United States, Arlington) - NSF
REU Site: DIMACS REU in Algorithms from Foundations to Applications, CNS-2150186, U.S. National Science Foundation (United States, Alexandria) - NSF
Grant note: National Science Foundation: CCF-1909216, CCF-1909683, CNS-2150186, CCF-1852215
This work was done in part while E. Allender and H. Tirumala were visiting the Simons Institute for the Theory of Com- puting, and J. Gray, S. Mutreja, and P. Wang were participants in the 2022 DIMACS REU program at Rutgers University. E. Allender and H. Tirumala were supported in part by the National Science Foundation under grants CCF-1909216 (https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909216) and CCF-1909683 (https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909683). J. Gray, S. Mutreja, and P. Wang were supported by the National Science Foundation under grants CNS-2150186 (https://www.nsf.gov/awardsearch/showAward?AWD_ID=2150186) and CCF-1852215 (https://www.nsf.gov/awardsearch/showAward?AWD_ID=1852215).
Academic Unit: Rutgers University
Language: English
Resource Type: Journal article
Identifiers: 991032103635804646