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

Xin Li

Abstract

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 \emph{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. In an alternative approach, Li \cite{Li12} 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=\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}.

Note: This is the full version of the same paper published in TCC 2015.

Metadata
Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2015
Keywords
privacy amplificationnon-malleableextractorcondenser
Contact author(s)
lixints @ cs jhu edu
History
2015-01-12: received
Short URL
https://ia.cr/2015/021
License

CC BY

BibTeX

@misc{cryptoeprint:2015/021,
author = {Xin Li},
title = {Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification},
howpublished = {Cryptology ePrint Archive, Paper 2015/021},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/021}},
url = {https://eprint.iacr.org/2015/021}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.