Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification

Understand

Recently, the problem of privacy amplification with an active adversary has received a lot of attention.

• Given a shared n-bit weak random source X with min-entropy k and a security parameter s, the main goal is to construct an explicit 2-round privacy amplification protocol that achieves entropy loss O(s).
• Dodis and Wichs \cite{DW09} showed that optimal protocols can be achieved by constructing explicit non-malleable extractors.
• However, the best known explicit non-malleable extractor only achieves k=0.49n \cite{Li12b} and evidence in \cite{Li12b} suggests that constructing explicit non-malleable extractors for smaller min-entropy may be hard.