Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR11-068 | 27th April 2011
L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder

Balls and Bins: Smaller Hash Families and Faster Evaluation

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

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

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

ISSN 1433-8092 | Imprint