Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with zero knowledge:
TR04-083 | 8th September 2004
Boaz Barak, Yehuda Lindell, Salil Vadhan

Lower Bounds for Non-Black-Box Zero Knowledge

We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:
<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ... more >>>

TR06-095 | 25th July 2006
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

Concurrent Non-Malleable Witness Indistinguishability and its Applications

Revisions: 1

One of the central questions in Cryptography today is proving security of the protocols ``on the Internet'', i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called ``man-in-the-middle'' attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, ... more >>>

TR07-031 | 26th March 2007
Yael Tauman Kalai, Ran Raz

Interactive PCP

An interactive-PCP (say, for the membership $x \in L$) is a
proof that can be verified by reading only one of its bits, with the
help of a very short interactive-proof.
We show that for membership in some languages $L$, there are
interactive-PCPs that are significantly shorter than the known
more >>>

TR07-065 | 13th July 2007
Jonathan Katz

Which Languages Have 4-Round Zero-Knowledge Proofs?

We show that if a language $L$ has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then $\bar L \in MA$. Assuming the polynomial hierarchy does not collapse, this means, in particular, that $NP$-complete languages do not have 4-round zero-knowledge proofs (at least with respect to black-box ... more >>>

TR09-006 | 19th January 2009
David Xiao

On basing ZK != BPP on the hardness of PAC learning

Learning is a central task in computer science, and there are various
formalisms for capturing the notion. One important model studied in
computational learning theory is the PAC model of Valiant (CACM 1984).
On the other hand, in cryptography the notion of ``learning nothing''
is often modelled by the simulation ... more >>>

TR09-045 | 20th May 2009
Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

Inaccessible Entropy

We put forth a new computational notion of entropy, which measures the
(in)feasibility of sampling high entropy strings that are consistent
with a given protocol. Specifically, we say that the i'th round of a
protocol (A, B) has _accessible entropy_ at most k, if no
polynomial-time strategy A^* can generate ... more >>>

TR10-020 | 19th February 2010
Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai

Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by ... more >>>

TR15-186 | 24th November 2015
Benny Applebaum, Pavel Raykov

On the Relationship between Statistical Zero-Knowledge and Statistical Randomized Encodings

\emph{Statistical Zero-knowledge proofs} (Goldwasser, Micali and Rackoff, SICOMP 1989) allow a computationally-unbounded server to convince a computationally-limited client that an input $x$ is in a language $\Pi$ without revealing any additional information about $x$ that the client cannot compute by herself. \emph{Randomized encoding} (RE) of functions (Ishai and Kushilevitz, FOCS ... more >>>

TR16-001 | 9th January 2016
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

Revisions: 1

The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs.

Ben-Or et ... more >>>

TR16-199 | 15th December 2016
Pavel Hubacek, Moni Naor, Eylon Yogev

The Journey from NP to TFNP Hardness

The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one ... more >>>

TR17-057 | 7th April 2017
Alessandro Chiesa, Michael Forbes, Nicholas Spooner

A Zero Knowledge Sumcheck and its Applications

Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure.

In this work, we develop algebraic techniques for ... more >>>

TR17-099 | 5th June 2017
Nir Bitansky, Omer Paneth, Yael Tauman Kalai

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions

Revisions: 1

We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. ... more >>>

ISSN 1433-8092 | Imprint