Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with statistical zero knowledge:
TR01-046 | 2nd July 2001
Oded Goldreich, Salil Vadhan, Avi Wigderson

On Interactive Proofs with a Laconic Prover

We continue the investigation of interactive proofs with bounded
communication, as initiated by Goldreich and Hastad (IPL 1998).
Let $L$ be a language that has an interactive proof in which the prover
sends few (say $b$) bits to the verifier.
We prove that the complement $\bar L$ has ... more >>>

TR01-057 | 15th August 2001
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

On the (Im)possibility of Obfuscating Programs

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)
"compiler" that takes as input a program (or circuit) <b>P</b> and
produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>
yet is "unintelligible" in some sense. Obfuscators, if they exist,
would have a wide variety of cryptographic ... more >>>

TR06-139 | 14th November 2006
Shien Jin Ong, Salil Vadhan

Zero Knowledge and Soundness are Symmetric

Revisions: 1

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems that is symmetric in its treatment of the zero knowledge and the soundness conditions. From this, we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. ... more >>>

TR14-068 | 5th May 2014
Eric Allender, Bireswar Das

Zero Knowledge and Circuit Minimization

Revisions: 1

We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is
efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP^MCSP.

This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these ... more >>>

TR18-193 | 14th November 2018
Nicollas Sdroievski, Murilo Silva, André Vignatti

The Hidden Subgroup Problem and MKTP

We show that the Hidden Subgroup Problem for black-box groups is in $\mathrm{BPP}^\mathrm{MKTP}$ (where $\mathrm{MKTP}$ is the Minimum $\mathrm{KT}$ Problem) using the techniques of Allender et al (2018). We also show that the problem is in $\mathrm{ZPP}^\mathrm{MKTP}$ provided that there is a \emph{pac overestimator} computable in $\mathrm{ZPP}^\mathrm{MKTP}$ for the logarithm ... more >>>

TR22-011 | 25th January 2022
Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen

Public-Key Encryption from Continuous LWE

The continuous learning with errors (CLWE) problem was recently introduced by Bruna
et al. (STOC 2021). They showed that its hardness implies infeasibility of learning Gaussian
mixture models, while its tractability implies efficient Discrete Gaussian Sampling and thus
asymptotic improvements in worst-case lattice algorithms. No reduction between CLWE and
LWE ... more >>>

ISSN 1433-8092 | Imprint