We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Haastad, Impagliazzo, Levin and Luby [SICOMP '99]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired ... more >>>

We investigate the question of what languages can be decided efficiently with the help of a recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash functions or, more generally, statistically hiding commitments. The oracle we consider, $Sam_d$ where $d$ is the recursion depth, is based on ... more >>>

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

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, ... more >>>

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme ... more >>>

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

We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>>

A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another
polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any
additional information but the validity of the claim.

Naor ... more >>>