Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with sumcheck protocol:
TR18-044 | 5th March 2018
Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

Revisions: 1

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>>

TR21-180 | 21st December 2021
Noga Ron-Zewi, Ron Rothblum

Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input $x$ belongs to a language $L \in NP$, with communication that is much shorter than the $NP$ witness. Such arguments, which grew out of the theory literature, are now drawing ... more >>>

ISSN 1433-8092 | Imprint