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=\Omega(\sqrt{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/\sqrt{k})$ rounds with optimal entropy loss, for security parameter up to $s=\Omega(k)$. This significantly improves the protocol in \cite{ckor}. 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=\Omega(k)$, which improves the entropy loss and communication complexity of the protocol in \cite{Li12b}.
Category / Keywords: cryptographic protocols / privacy amplification, non-malleable, extractor, condenser Original Publication (with major differences): IACR-TCC-2015 Date: received 11 Jan 2015 Contact author: lixints at cs jhu edu Available format(s): PDF | BibTeX Citation Note: This is the full version of the same paper published in TCC 2015. Version: 20150112:072615 (All versions of this report) Discussion forum: Show discussion | Start new discussion