Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with constant-round:
TR08-068 | 3rd July 2008
Lior Malka

Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs

We study the question whether the number of rounds in public-coin perfect zero-knowledge (PZK) proofs can be collapsed to a constant. Despite extensive research into the round complexity of interactive
and zero-knowledge protocols, there is no indication how to address this question. Furthermore, the main tool to tackle this question ... more >>>

TR23-081 | 1st June 2023
Noga Amit, Guy Rothblum

Constant-Round Arguments from One-Way Functions

We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of $\mathbf{P}$, such as depth-bounded computations.
Kilian's celebrated work [STOC 1992] provides such 4-message arguments for $\mathbf{P}$ (actually, for $\mathbf{NP}$) using collision-resistant hash ... more >>>

ISSN 1433-8092 | Imprint