Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ZERO-KNOWLEDGE:
Reports tagged with zero-knowledge:
TR94-007 | 12th December 1994
Oded Goldreich, Rafail Ostrovsky, Erez Petrank

#### Computational Complexity and Knowledge Complexity

We study the computational complexity of languages which have
interactive proofs of logarithmic knowledge complexity. We show that
all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior
to this work, for languages with greater-than-zero knowledge
complexity (and specifically, even for knowledge complexity 1) only
trivial computational complexity bounds ... more >>>

TR94-008 | 12th December 1994
Oded Goldreich

#### Probabilistic Proof Systems (A Survey)

Various types of probabilistic proof systems have played
a central role in the development of computer science in the last decade.
In this exposition, we concentrate on three such proof systems ---
interactive proofs, zero-knowledge proofs,
and probabilistic checkable proofs --- stressing the essential
role of randomness in each ... more >>>

TR98-063 | 4th November 1998

#### Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

We consider the following (promise) problem, denoted ED (for Entropy
Difference): The input is a pairs of circuits, and YES instances (resp.,
NO instances) are such pairs in which the first (resp., second) circuit
generates a distribution with noticeably higher entropy.

On one hand we show that any language ... more >>>

TR99-024 | 25th June 1999
Oded Goldreich, Silvio Micali.

#### Interleaved Zero-Knowledge in the Public-Key Model.

We introduce the notion of Interleaved Zero-Knowledge (iZK),
a new security measure for cryptographic protocols which strengthens
the classical notion of zero-knowledge, in a way suitable for multiple
concurrent executions in an asynchronous environment like the internet.
We prove that iZK protocols are robust: they are parallelizable'',
and ... more >>>

TR99-042 | 24th October 1999
Ran Canetti, Oded Goldreich, Silvio Micali.

#### Resettable Zero-Knowledge.

Revisions: 1

We introduce the notion of Resettable Zero-Knowledge (rZK),
a new security measure for cryptographic protocols
which strengthens the classical notion of zero-knowledge.
In essence, an rZK protocol is one that remains zero knowledge
even if an adeversary can interact with the prover many times, each
time ... more >>>

TR01-050 | 24th June 2001
Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

#### Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

We show that any concurrent zero-knowledge protocol for a non-trivial
language (i.e., for a language outside $\BPP$), whose security is proven
via black-box simulation, must use at least $\tilde\Omega(\log n)$
rounds of interaction. This result achieves a substantial improvement
over previous lower bounds, and is the first bound to rule ... more >>>

TR01-091 | 27th November 2001
Oded Goldreich

#### Concurrent Zero-Knowledge With Timing, Revisited

Following Dwork, Naor, and Sahai (30th STOC, 1998),
we consider concurrent execution of protocols in a
semi-synchronized network. Specifically, we assume that each party
holds a local clock such that a constant bound on the relative rates
of these clocks is a-priori known, and consider protocols that
employ ... more >>>

TR02-001 | 8th January 2002
Cynthia Dwork, Moni Naor

#### Zaps and Their Applications

A zap is a two-round, witness-indistinguishable protocol in which
the first round, consisting of a message from the verifier to the
prover, can be fixed once-and-for-all" and applied to any instance,
and where the verifier does not use any private coins.
We present a zap for every language in NP, ... more >>>

TR02-026 | 7th April 2002
Boaz Barak, Yehuda Lindell

#### Strict Polynomial-time in Simulation and Extraction

Revisions: 2

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time which is only polynomial {\em on the average} (i.e., ... more >>>

TR02-063 | 3rd December 2002
Oded Goldreich

#### Zero-Knowledge twenty years after its invention

Zero-knowledge proofs are proofs that are both convincing and yet
yield nothing beyond the validity of the assertion being proven.
Since their introduction about twenty years ago,
zero-knowledge proofs have attracted a lot of attention
and have, in turn, contributed to the development of other
areas of cryptography and complexity ... more >>>

TR06-096 | 10th August 2006
Iftach Haitner, Omer Reingold

#### A New Interactive Hashing Theorem

Interactive hashing, introduced by Naor et al. [NOVY98], plays
an important role in many cryptographic protocols. In particular, it
is a major component in all known constructions of
statistically-hiding commitment schemes and of zero-knowledge
arguments based on general one-way permutations and on one-way
functions. Interactive hashing with respect to a ... more >>>

TR06-099 | 17th August 2006
Oded Goldreich

#### On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits

Revisions: 1

This paper concerns the possibility of developing a coherent
theory of security when feasibility is associated
with expected probabilistic polynomial-time (expected PPT).
The source of difficulty is that
the known definitions of expected PPT strategies
(i.e., expected PPT interactive machines)
do not support natural results of the ... more >>>

ISSN 1433-8092 | Imprint