Non-malleable condensers for arbitrary min-entropy, and almost optimal protocols for privacy amplification
From MaRDI portal
Publication:5261642
DOI10.1007/978-3-662-46494-6_21zbMATH Open1359.94653arXiv1211.0651OpenAlexW1487376352MaRDI QIDQ5261642FDOQ5261642
Authors: Xin Li 
Publication date: 6 July 2015
Published in: Theory of Cryptography (Search for Journal in Brave)
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 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}.
Full work available at URL: https://arxiv.org/abs/1211.0651
Recommendations
- Design extractors, non-malleable condensers and privacy amplification
- Nonmalleable extractors with short seeds and applications to privacy amplification
- Privacy Amplification and Nonmalleable Extractors Via Character Sums
- Privacy Amplification and Nonmalleable Extractors Via Character Sums
- Privacy amplification from non-malleable codes
Cited In (7)
- An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
- Title not available (Why is that?)
- An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
- Nonmalleable Extractors and Codes, with Their Many Tampered Extensions
- Privacy Amplification and Nonmalleable Extractors Via Character Sums
- Privacy amplification from non-malleable codes
- Local Correlation Breakers and Applications to Three-Source Extractors and Mergers
This page was built for publication: Non-malleable condensers for arbitrary min-entropy, and almost optimal protocols for privacy amplification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5261642)
