You are looking at a specific version 20150505:060726 of this paper. See the latest version.

Paper 2014/156

Non-Malleable Extractors with Shorter Seeds and Their Applications

Yanqing Yao and Zhoujun Li

Abstract

Motivated by the problem of how to communicate over a public channel with an active adversary, Dodis and Wichs (STOC’09) introduced the notion of a non-malleable extractor. A non-malleable extractor nmExt : {0, 1}^n × {0, 1}^d \rightarrow {0, 1}^m takes two inputs, a weakly random W and a uniformly random seed S, and outputs a string which is nearly uniform, given S as well as nmExt(W,A(S)), for an arbitrary function A with A(S) \neq S. In this paper, by developing the combination and permutation techniques, we improve the error estimation of the extractor of Raz (STOC'05), which plays an extremely important role in the constraints of the non-malleable extractor parameters including seed length. Then we present an improved explicit construction of non-malleable extractors. Though our construction is the same as that given by Cohen, Raz and Segev (CCC’12), the parameters are improved. More precisely, we construct an explicit (1016, 1/2)-non-malleable extractor nmExt:{0, 1}^n × {0, 1}^d \rightarrow {0, 1} with n = 1024 and seed length d = 19, while Cohen et al. showed that the seed length should be no less than 46/63 +66. Therefore, our method beats the condition “2.01 · log n \leq d \leq n” proposed by Cohen et al., since d is just 1.9 · log n in our construction. We also improve the parameters of the general explicit construction given by Cohen et al. and simplify the constraints on the parameters. Finally, we give their applications to non-malleable codes and privacy amplification.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
extractorsnon-malleable extractorsseed lengthnon-malleable codesprivacy amplification protocol
Contact author(s)
yaoyanqing1984 @ gmail com
yaoyanqing1984 @ buaa edu cn
lizj @ buaa edu cn
History
2015-09-22: last of 9 revisions
2014-03-01: received
See all versions
Short URL
https://ia.cr/2014/156
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.