All reports by Author Gil Segev:

__
TR11-096
| 2nd July 2011
__

Gil Cohen, Ran Raz, Gil Segev#### Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification

__
TR11-068
| 27th April 2011
__

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder#### Balls and Bins: Smaller Hash Families and Faster Evaluation

__
TR07-038
| 23rd April 2007
__

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev#### Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

Gil Cohen, Ran Raz, Gil Segev

Motivated by the classical problem of privacy amplification, Dodis and Wichs (STOC '09) introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function $nmExt : \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$ and ... more >>>

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder

A fundamental fact in the analysis of randomized algorithm is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n / \log \log n)$ balls. In various applications, however, the assumption that a truly random hash ... more >>>

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

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