2011/12/05 by Xin Li, Li, Xin · 2 citations
Computer Science · #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #Privacy-Preserving Technologies in Data #cs.CC #cs.CR
paper · pdf · doi:10.48550/arxiv.1112.1045
openalex publication_date 2011/12/05 · arxiv created 2012/04/09 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Dodis and Wichs introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Previously, there are only two known constructions of non-malleable extractors. Both constructions only work for (n, k)-sources with k>n/2. Interestingly, both constructions are also two-source extractors. In this paper, we present a strong connection between non-malleable extractors and two-source extractors. The first part of the connection shows that non-malleable extractors can be used to construct two-source extractors. With appropriate parameters the resulted two-source extractor beats the best known construction of two-source extractors. This partially explains why previous constructions of non-malleable extractors only work for sources with entropy rate >1/2, and why explicit non-malleable extractors for small min-entropy may be hard to get. The second part of the connection shows that certain two-source extractors can be used to construct non-malleable extractors. Using this connection, we obtain the first construction of non-malleable extractors for k < n/2. Specifically, we give an unconditional construction for min-entropy k=(1/2-δ)n for some constant δ>0, and a conditional (semi-explicit) construction that can potentially achieve k=αn for any constant α>0. Finally, despite the lack of explicit non-malleable extractors for arbitrarily linear entropy, we give the first 2-round privacy amplification protocol with asymptotically optimal entropy loss and communication complexity for (n, k) sources with k=αn for any constant α>0. This dramatically improves previous results and answers an open problem in \citeDLWZ11.