We address the problem of designing optimal schemes for the generation of secure cryptographic keys from continuous noisy data. We argue that, contrary to the discrete case, a universal fuzzy extractor does not exist. This implies that in the continuous case, key extraction schemes have to be designed for particular probability distributions. We extend the known definitions of the correctness and security properties of fuzzy extractors. Our definitions apply to continuous as well as discrete variables. We propose a generic construction for fuzzy extractors from noisy continuous sources, using independent partitions. The extra freedom in the choice of discretization, which does not exist in the discrete case, is advantageously used to give the extracted key a uniform distribution. We analyze the privacy properties of the scheme and the error probabilities in a one-dimensional toy model with simplified noise. Finally, we study the security implications of incomplete knowledge of the source's probability distribution${\BBP }$. We derive a bound on the min-entropy of the extracted key under the worst-case assumption, where the attacker knows${\BBP }$exactly.
We address the problem of designing optimal schemes for the generation of secure crypto-\ngraphic keys from continuous noisy data. We argue that, contrary to the discrete case, a\nuniversal fuzzy extractor does not exist. This implies that in the continuous case, key ex-\ntraction schemes have to be designed for particular probability distributions. We extend the\nknown definitions of the correctness and security properties of fuzzy extractors. Our defini-\ntions apply to continuous as well as discrete variables.\nWe propose a generic construction for fuzzy extractors from noisy continuous sources, using independent partitions. The extra freedom in the choice of discretisation, which does not exist in the discrete case, is advantageously used to give the extracted key a uniform distribution. We analyze the privacy properties of the scheme and the error probabilities in a one-dimensional toy model with simplified noise.\nFinally, we study the security implications of incomplete knowledge of the source's probability distribution P. We derive a bound on the min-entropy of the extracted key under the worst case assumption, where the attacker knows P exactly.
The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories:
(1) Constructions where one source has min-entropy rate about
1/2, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability.
(2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered.
(3) Constructions where both sources have entropy rate very close to
1 and the extractor guarantees non-malleability against the tampering of both sources.
We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have
0.8 entropy rate and the other source can have min-entropy polylogarithmic in the length of the source.
We show how the above extractor can be applied to obtain a non-malleable extractor with output rate
21, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.
The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy rate about
1/2, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability. (2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered. (3) Constructions where both sources have entropy rate very close to
1 and the extractor guarantees non-malleability against the tampering of both sources. We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have
0.8 entropy rate and the other source can have min-entropy polylogarithmic in the length of the source. We show how the above extractor can be applied to obtain a non-malleable extractor with output rate
21, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.
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.
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.