TY - GEN
T1 - Non-malleable extractors with short seeds and applications to privacy amplification
AU - Cohen, Gil
AU - Raz, Ran
AU - Segev, Gil
PY - 2012
Y1 - 2012
N2 - Motivated by the classical problem of privacy amplification, Dodis and Wichs~\cite{DodisW09} introduced the notion of a {\em non-malleable extractor}, significantly strengthening the notion of a {\em strong extractor}. A non-malleable extractor is a function \nm Ext : \{0, 1\} n \times \{0, 1\} d \right arrow \{0, 1\} m that takes two inputs: a weak source W and a uniform (independent) seed S, and outputs a string \nm Ext(W, S) that is nearly uniform given S as well as \nm Ext(W, S') for any seed S' \neq S that is determined as an arbitrary function of S. The first explicit construction of a non-malleable extractor was recently provided by Dodis, Li, Wooley and Zuckerman~\ cite{DLWZ11a}. Their extractor works for any weak source with min-entropy rate 1/2 + \delta, where \delta > 0 is an arbitrary constant, and outputs up to a linear number of bits, but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols) its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an {\em unconditional} construction of a non-malleable extractor with {\em short seeds}. For any integers n and d such that 2.01 \cdot \log{n} \le d \le n, we present an explicit construction of a non-malleable extractor \nm Ext \colon \{0, 1\} n \times \{0, 1\} d \right arrow \{0, 1\} m, with m=\Omega(d), and error exponentially small in m. The extractor works for any weak source with min-entropy rate 1/2 + \delta, where \delta > 0 is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of non-malleability: its output \nm Ext(W, S) is nearly uniform given the seed S as well as the values \nm Ext(W, S-1), \ldots, \nm Ext(W, S-t) for several seeds S-1, \ldots, S-t that may be determined as an arbitrary function of S, as long as S \notin \{S-1, \ldots, S-t\}. By instantiating the framework of Dodis and Wichs with our non-malleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate 1/2 + \delta with asymptotically optimal entropy loss and poly-logarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs whose entropy loss is not asymptotically optimal, and the protocol of Dodis, Li, Wooley and Zuckerman whose communication complexity is linear.
AB - Motivated by the classical problem of privacy amplification, Dodis and Wichs~\cite{DodisW09} introduced the notion of a {\em non-malleable extractor}, significantly strengthening the notion of a {\em strong extractor}. A non-malleable extractor is a function \nm Ext : \{0, 1\} n \times \{0, 1\} d \right arrow \{0, 1\} m that takes two inputs: a weak source W and a uniform (independent) seed S, and outputs a string \nm Ext(W, S) that is nearly uniform given S as well as \nm Ext(W, S') for any seed S' \neq S that is determined as an arbitrary function of S. The first explicit construction of a non-malleable extractor was recently provided by Dodis, Li, Wooley and Zuckerman~\ cite{DLWZ11a}. Their extractor works for any weak source with min-entropy rate 1/2 + \delta, where \delta > 0 is an arbitrary constant, and outputs up to a linear number of bits, but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols) its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an {\em unconditional} construction of a non-malleable extractor with {\em short seeds}. For any integers n and d such that 2.01 \cdot \log{n} \le d \le n, we present an explicit construction of a non-malleable extractor \nm Ext \colon \{0, 1\} n \times \{0, 1\} d \right arrow \{0, 1\} m, with m=\Omega(d), and error exponentially small in m. The extractor works for any weak source with min-entropy rate 1/2 + \delta, where \delta > 0 is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of non-malleability: its output \nm Ext(W, S) is nearly uniform given the seed S as well as the values \nm Ext(W, S-1), \ldots, \nm Ext(W, S-t) for several seeds S-1, \ldots, S-t that may be determined as an arbitrary function of S, as long as S \notin \{S-1, \ldots, S-t\}. By instantiating the framework of Dodis and Wichs with our non-malleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate 1/2 + \delta with asymptotically optimal entropy loss and poly-logarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs whose entropy loss is not asymptotically optimal, and the protocol of Dodis, Li, Wooley and Zuckerman whose communication complexity is linear.
KW - extractors
KW - non-malleable extractors
KW - privacy amplification
UR - http://www.scopus.com/inward/record.url?scp=84866504943&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84866504943&partnerID=8YFLogxK
U2 - 10.1109/CCC.2012.21
DO - 10.1109/CCC.2012.21
M3 - Conference contribution
AN - SCOPUS:84866504943
SN - 9780769547084
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 298
EP - 308
BT - Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012
T2 - IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
Y2 - 26 June 2012 through 29 June 2012
ER -