2012/11/03 by Li, Xin
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1211.0651
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 \citeDW09 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 \citeLi12b and evidence in \citeLi12b suggests that constructing explicit non-malleable extractors for smaller min-entropy may be hard. In an alternative approach, Li \citeLi12 introduced the notion of a non-malleable condenser and showed that explicit non-malleable condensers also give optimal privacy amplification protocols. In this paper, we give the first construction of non-malleable condensers for arbitrary min-entropy. Using our construction, we obtain a 2-round privacy amplification protocol with optimal entropy loss for security parameter up to s=Ω(√(k)). This is the first protocol that simultaneously achieves optimal round complexity and optimal entropy loss for arbitrary min-entropy k. We also generalize this result to obtain a protocol that runs in O(s/√(k)) rounds with optimal entropy loss, for security parameter up to s=Ω(k). This significantly improves the protocol in \citeckor. Finally, we give a better non-malleable condenser for linear min-entropy, and in this case obtain a 2-round protocol with optimal entropy loss for security parameter up to s=Ω(k), which improves the entropy loss and communication complexity of the protocol in \citeLi12b.