Oded Goldreich, Amit Sahai, Salil Vadhan

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

Oded Goldreich, Liav Teichner

We initiate a study of super-perfect zero-knowledge proof systems.

Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time.

In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated

by a strict probabilistic polynomial-time that ...
more >>>

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

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

Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai

The existence of "unstructured" hard languages in $\text{NP}\cap\text{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\text{P}$ is separated from $\text{NP}\cap\text{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\text{NP}\cap\text{coNP}$ can be constructed in a black-box way ... more >>>