All reports by Author Erez Petrank:

__
TR04-085
| 3rd October 2004
__

Erez Petrank, Guy Rothblum#### Selection from Structured Data Sets

__
TR02-045
| 8th July 2002
__

Daniele Micciancio, Erez Petrank#### Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol

__
TR01-050
| 24th June 2001
__

Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen#### Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

__
TR98-032
| 10th June 1998
__

Mihir Bellare, Oded Goldreich, Erez Petrank#### Uniform Generation of NP-witnesses using an NP-oracle.

__
TR95-038
| 2nd July 1995
__

Joe Kilian, Erez Petrank#### An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions

__
TR94-007
| 12th December 1994
__

Oded Goldreich, Rafail Ostrovsky, Erez Petrank#### Computational Complexity and Knowledge Complexity

Erez Petrank, Guy Rothblum

A large body of work studies the complexity of selecting the

$j$-th largest element in an arbitrary set of $n$ elements (a.k.a.

the select$(j)$ operation). In this work, we study the

complexity of select in data that is partially structured by

an initial preprocessing stage and in a data structure ...
more >>>

Daniele Micciancio, Erez Petrank

We show how to efficiently transform any public coin honest verifier

zero knowledge proof system into a proof system that is concurrent

zero-knowledge with respect to any (possibly cheating) verifier via

black box simulation. By efficient we mean that our transformation

incurs only an additive overhead, ...
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 >>>

Mihir Bellare, Oded Goldreich, Erez Petrank

A Uniform Generation procedure for $NP$ is an

algorithm which given any input in a fixed NP-language, outputs a uniformly

distributed NP-witness for membership of the input in the language.

We present a Uniform Generation procedure for $NP$ that runs in probabilistic

polynomial-time with an NP-oracle. This improves upon ...
more >>>

Joe Kilian, Erez Petrank

We consider noninteractive zero-knowledge proofs in the shared random

string model proposed by Blum, Feldman and Micali \cite{bfm}. Until

recently there was a sizable polynomial gap between the most

efficient noninteractive proofs for {\sf NP} based on general

complexity assumptions \cite{fls} versus those based on specific

algebraic assumptions \cite{Da}. ...
more >>>

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