November 2, Wednesday 14:15, Room 303, Jacobs Building
Title: Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification
Lecturer: Gil Cohen
Lecturer homepage
: http://www.wisdom.weizmann.ac.il/~gilc/
Affiliation : Department of Computer Science and Applied Mathematics, Weizmann Institute of Science
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 a uniform (independent) seed $S$, and outputs a string $\nmExt(W,S)$
that is nearly uniform given the seed $S$ as well as the value $\nmExt(W,
S')$ for any seed $S' \neq S$ that may be determined as an arbitrary
function of $S$.