Oded Goldreich, Rafail Ostrovsky, Erez Petrank

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 >>>

Oded Goldreich

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 >>>

Oded Goldreich, Salil Vadhan

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 >>>

Oded Goldreich, Silvio Micali.

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 >>>

Ran Canetti, Oded Goldreich, Silvio Micali.

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 >>>

Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

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 >>>

Oded Goldreich

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 >>>

Cynthia Dwork, Moni Naor

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 >>>

Boaz Barak, Yehuda Lindell

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 >>>

Oded Goldreich

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 >>>

Iftach Haitner, Omer Reingold

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 >>>

Oded Goldreich

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 >>>