Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > STATISTICAL ZERO-KNOWLEDGE PROOFS:
Reports tagged with Statistical Zero-Knowledge Proofs:
TR99-013 | 28th May 1999
Oded Goldreich, Amit Sahai, Salil Vadhan

#### Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK

We extend the study of non-interactive statistical zero-knowledge
proofs. Our main focus is to compare the class NISZK of problems
possessing such non-interactive proofs to the class SZK of problems
possessing interactive statistical zero-knowledge proofs. Along these
lines, we first show that if statistical zero knowledge is non-trivial
then so ... more >>>

TR00-084 | 6th November 2000

#### A Complete Problem for Statistical Zero Knowledge

We present the first complete problem for SZK, the class of (promise)
problems possessing statistical zero-knowledge proofs (against an
honest verifier). The problem, called STATISTICAL DIFFERENCE, is to
decide whether two efficiently samplable distributions are either
statistically close or far apart. This gives a new characterization
of SZK that makes ... more >>>

TR16-140 | 9th September 2016
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

#### On SZK and PP

Revisions: 3

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

TR21-029 | 1st March 2021
Inbar Kaslasi, Ron Rothblum, Prashant Nalini Vasudevan

#### Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers

Suppose that a problem $\Pi$ has a statistical zero-knowledge (SZK) proof with communication complexity $m$. The question of batch verification for SZK asks whether one can prove that $k$ instances $x_1,\ldots,x_k$ all belong to $\Pi$ with a statistical zero-knowledge proof whose communication complexity is better than $k \cdot m$ (which ... more >>>

ISSN 1433-8092 | Imprint