We explicitly construct random hash functions for privacy amplification (extractors) that require smaller random seed lengths than the previous literature, and still allow efficient implementations with complexity O(n log n) for input length n. Firstly, we construct two types of hash functions by using the finite-filed. Then, concatenating them, we construct other two types of hash functions. We compare our hash functions with existing hash function in an asymptotic setting under a fixed key generation rate.
Motivated by the classical problem of privacy amplification, Dodis and Wichs [in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 601--610] introduced the notion of a nonmalleable extractor, significantly strengthening the notion of a strong extractor. A nonmalleable extractor is a function
nmExt:{0,1}n×{0,1}d→{0,1}m that takes two inputs---a weak source
W and a uniform (independent) seed
S---and outputs a string
nmExt(W,S) that is nearly uniform given the seed
S as well as the value
nmExt(W,S′) for any seed
S′=S that may be determined as an arbitrary function of
S. The first explicit construction of a nonmalleable extractor was recently provided by Dodis et al. [Privacy Amplification and Non-malleable Extractors via Character Sums, preprint, arXiv:1102.5415 [cs.CR], 2011]. Their extractor works for any weak source with min-entropy rate
1/2+δ, where
δ>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 unconditional construction of a nonmalleable extractor with short seeds. For any integers
n and
d such that
2.01⋅logn≤d≤n, we present an explicit construction of a nonmalleable extractor
nmExt:{0,1}n×{0,1}d→{0,1}m, with
m=Ω(d) and error exponentially small in
m. The extractor works for any weak source with min-entropy rate
1/2+δ, where
δ>0 is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of nonmalleability: its output
nmExt(W,S) is nearly uniform given the seed
S as well as the values
nmExt(W,S1),…,nmExt(W,St) for several seeds
S1,…,St that may be determined as an arbitrary function of
S, as long as
S∈/{S1,…,St}. By instantiating the framework of Dodis and Wichs with our nonmalleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate
1/2+δ with asymptotically optimal entropy loss and polylogarithmic 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 et al., whose communication complexity is linear.
Dodis and Wichs [DW09] 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. Given a weakly-random string x and a uniformly random seed y as the inputs, the non-malleable extractor nmExt has the property that nmExt(x, y) appears uniform even given y as well as nmExt(x,A(y)), for an arbitrary function A with A(y) 6= y. Dodis and Wichs showed that such an object can be used to give optimal privacy amplification protocols with an active adversary. Previously, there are only two known explicit constructions of non-malleable extractors [DLWZ11, CRS11]. Both constructions only work for (n, k)-sources with k > n/2 and thus they also only achieve optimal privacy amplification protocols for k > n/2. In this paper, we give the first construction of non-malleable extractors for k 0, and a conditional construction that can potentially achieve k = αn for any constant α > 0. Using our non-malleable extractor, we also obtain the first optimal privacy amplification protocol for min-entropy k = (1/2 − δ)n, with an active adversary. Our constructions mainly use the bilinear property of the inner product function, and involve appropriate encodings of the seed y as well as ideas from additive combinatorics. ∗Partially supported by NSF Grants CCF-0634811, CCF-0916160, THECB ARP Grant 003658-0113-2007, and a Simons postdoctoral fellowship. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 166 (2011)
We introduce a new combinatorial object, called a design extractor, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications. Improving the output length of known non-malleable extractors. Non-malleable extractors were introduced in [DW09] to study the problem of privacy amplification with an active adversary. Currently, only two explicit constructions are known [DLWZ11, CRS11]. Both constructions work for n bit sources with min-entropy k > n/2. However, in both constructions the output length is smaller than the seed length, while the probabilistic method shows that to achieve error e, one can use O(log n+log (1/e)) bits to extract up to k/2 output bits. In this paper, we use our design extractor to give an explicit non-malleable extractor for min-entropy k > n/2, that has seed length O(log n+log (1/e)) and output length Ω(k). Non-malleable condensers. We introduce and define the notion of a non-malleable condenser. A non-malleable condenser is a generalization and relaxation of a non-malleable extractor. We show that similar as extractors and condensers, non-malleable condensers can be used to construct non-malleable extractors. We then show that our design extractor already gives a non-malleable condenser for min-entropy k > n/2, with error e and seed length O(log (1/e)). A new optimal protocol for privacy amplification. More surprisingly, we show that non-malleable condensers themselves give optimal privacy amplification protocols with an active adversary. In fact, the non-malleable condensers used in these protocols are much weaker compared to non-malleable extractors, in the sense that the entropy rate of the condenser's output does not need to increase at all. This suggests that one promising next step to achieve better privacy amplification protocols may be to construct non-malleable condensers for smaller min-entropy. As a by-product, we also obtain a new explicit 2-round privacy amplification protocol with optimal entropy loss and optimal communication complexity for min-entropy k>n/2, without using non-malleable extractors.
We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors, 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter, 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic). For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li, and by Cohen all require seed length and min-entropy with quadratic loss in parameters. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve two rounds of communication and optimal entropy loss was sub-optimal in the min-entropy of the source. In this paper we give an explicit non-malleable extractor that works for nearly optimal seed length and min-entropy, and yields a two-round privacy amplification protocol with optimal entropy loss for almost all ranges of the security parameter. For the third problem, we improve upon a very recent result by Cohen and Schulman and give an explicit extractor that uses an absolute constant number of sources, each with almost logarithmic min-entropy. The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced by Cohen, which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of Cohen and Schulman, and may be of independent interest.
A fuzzy extractor is a security primitive that allows for reproducible extraction of an almost uniform key from a non-uniform noisy source. We analyze a fuzzy extractor scheme that uses universal hash functions for both information reconciliation and privacy amplification. This is a useful scheme when the number of error patterns likely to occur is limited, regardless of the error probabilities. We derive a sharp bound on the uniformity of the extracted key, making use of the concatenation property of universal hash functions and a recent tight formulation of the leftover hash lemma.